Оптимизация кода Python для поиска дубликатов строк

Question

У нас длинный список со строками (около 18 тыс. Записей). Цель состоит в том, чтобы найти все похожие строки и сгруппировать их по максимальному сходству. («a» - список со строками)

Я написал следующий код:

def diff(a, b):
    return difflib.SequenceMatcher(None, a, b).ratio()

dupl = {}

while len(a) > 0:
    k = a.pop()
    if k not in dupl.keys():
        dupl[k] = []
    for i,j in enumerate(a):
            dif = diff(k, j)
            if dif > 0.5:
                dupl[k].append("{0}: {1}".format(dif, j))

Этот код берет элемент из списка и ищет дубликаты в остальной части списка. Если сходство больше 0,5, аналогичная строка добавляется к dict.

Все работает хорошо, но очень, очень медленно из-за длины списка "а". Поэтому я хотел бы спросить, есть ли способ как-то оптимизировать этот код? Есть идеи?

Answer 1

Пара небольших оптимизаций:

1. Вы можете удалить дубликаты из списка перед началом поиска (например, a = list (set (a))).В настоящий момент, если a содержит 18 тыс. Копий строки 'hello', она будет вызывать diff 18 тыс. * 18 тыс. Раз.

2. В данный момент вы будете сравнивать строку номер i со строкой номер j, итакже строка номер j со строкой номер i.Я думаю, что они вернут один и тот же результат, так что вы можете вычислить только один из них и, возможно, пойти в два раза быстрее.

Конечно, основная проблема в том, что diff называется n * nвремена для списка длины n, и идеальным решением было бы уменьшить количество вызовов diff.Подход к использованию будет зависеть от содержания ваших строк.

Вот несколько примеров возможных подходов, которые могут иметь отношение к различным случаям:

1. Предположим, что строки имеют очень разную длину.diff вернет> 0.5, только если длины строк находятся в пределах коэффициента 2. В этом случае вы можете отсортировать входные строки по длине за время O (nlogn), а затем сравнивать только строки одинаковой длины.

2. Предположим, что строки состоят из последовательностей слов и должны быть либо очень разными, либо очень похожими.Вы можете создать инвертированный индекс для слов, а затем сравнить только со строками, которые содержат те же самые необычные слова

3. Предположим, вы ожидаете, что строки попадут в небольшое количество групп.Вы можете попробовать запустить алгоритм K-средних, чтобы сгруппировать их в кластеры.Для этого потребуется K * n * I, где I - количество итераций алгоритма K-средних, которые вы выбираете использовать.

Если n станет очень большим (много миллионов), то это не будет уместно, и вам, вероятно, придется использовать более приближенные методы.Один пример, который используется для кластеризации веб-страниц, называется MinHash

Answer 2

При необходимости перебрать многие элементы, itertools , на помощь!

Этот фрагмент будет переставлять все возможности вашей строки (перестановок) и возвращать их так же, как ваш оригиналкод сделал.Я чувствую, что not in - неоправданно дорогой способ проверки, а не такой питонический.Перестановки были выбраны, так как это дало бы вам максимальный доступ к проверке a-> b или b-> a для двух заданных строк.

import difflib
import itertools

def diff(a, b):
    return difflib.SequenceMatcher(None, a, b).quick_ratio()

def calculate_ratios(strings):
     dupl = dict()
     for s, t in itertools.permutations(strings, 2):
          try:
               dupl[s].append({t: diff(s,t)})
          except KeyError:
               dupl[s] = []
               dupl[s].append({t: diff(s,t)})
     return dupl

a = ['first string', 'second string', 'third string', 'fourth string']
print calculate_ratios(a)

В зависимости от ваших ограничений (поскольку перестановки являются избыточными в вычислительном и пространственном отношении), вы можете заменить перестановки комбинациями, но тогда ваш метод доступа необходимо будет скорректировать (так как ab будет указан только в списке).в a [b], но не в b [a]).

В коде я использую quick_ratio (), но он так же просто изменяется на ratio () или real_quick_ratio () в зависимости от вашего решения, если естьДостаточная точность.

И в таком случае простой IF решит эту проблему:

import difflib
import itertools

def diff(a, b):
    return difflib.SequenceMatcher(None, a, b).quick_ratio()
def diff2(a, b):
    return difflib.SequenceMatcher(None, a, b).ratio()

def calculate_ratios(strings, threshold):
     dupl = dict()
     for s, t in itertools.permutations(strings, 2):
          if diff(s,t) > threshold: #arbitrary threshhold
               try:
                    dupl[s].append({t: diff2(s,t)})
               except KeyError:
                    dupl[s] = []
                    dupl[s].append({t: diff2(s,t)})
     return dupl

a = ['first string', 'second string', 'third string', 'fourth string']
print calculate_ratios(a, 0.5)