TL; DR: Как описано здесь , расстояние Левенштейна может быть не лучшим для измерения расстояния всех почтовых отправлений. Возможно, лучше использовать альтернативные расстояния или даже полностью изменить подход. Более того, эвристика может использоваться для ускорения выполнения.
Поскольку у вас есть k строк и вы хотите сравнить все пары, общая сложность будет O(k^2 L), где L это сложность вычисления levenshteinDistanceDP. Таким образом, в основном из-за фактора k^2 выполнение алгоритма в вашем случае займет не менее нескольких часов / дней.
Чтобы значительно снизить сложность вычислений, хорошим началом являются расстояние Хэмминга и сходство Жаккара.
Если использование приближения подходит, вы можете альтернативно:
- разработать функцию
f, которая преобразовывает почту в репрезентативный числовой дескриптор (ie. свойство вектор), сохраняя при этом местонахождение (насколько близки письма ); - применить функцию
f(s) к каждой почтовой строке s; - эффективно сравнить все полученные пары (например, используя разбиение двоичного пространства например kd-деревья , или статистические / классификационные методы).
Однако сложнее всего найти хорошего f кандидата (в этом могут помочь методы машинного обучения).
Обратите внимание, что вы можете использовать описанный выше метод для значительной фильтрации результатов перед применением вашего текущего точного метода. Полученный метод ( heuristi c) будет точным, если приближение никогда не переоценивает фактическое расстояние (ie. допустимое heuristi c).
ОБНОВЛЕНИЕ:
Простая допустимая эвристика c - это (скорректированное) манхэттенское расстояние векторов, содержащих частоты символов (ie. Количество вхождений каждого символа в заданный набор). Вот пример кода, использующего эту эвристию c:
# Count the number of 'a', 'b', 'c' ..., 'y', 'z' and '0', '1', ..., '9' in the string s
def freq(s):
res = np.zeros(36, dtype=int)
for c in map(ord, s.upper()):
if c >= 65 and c <= 90: # A-Z
res[c-65] += 1
elif c >= 48 and c <= 57: # 0-9
res[c-48+26] += 1
return res
# Compare the two frequency vectors fs and ft
def freqDist(fs, ft):
manDist = np.abs(fs-ft).sum()
return (manDist + 1) // 2
# Faster heuristic but not admissible (ie. approximation)
def freqDistApprox(fs, ft):
return np.abs(fs-ft).sum()
l = []
def fasterCombos(data):
maxi = len(list(makeCombos(data)))
count = 0
freqs = {s: freq(s) for s in data} # Precompute frequencies (feature vectors)
for x in makeCombos(data):
s, t = x[0], x[1]
if freqDist(freqs[s], freqs[t]) < 4: # Estimate the levenshtein distance quickly
if levenshteinDistanceDP(s, t) < 4:
l.append(x)
Эта простая эвристика c должна значительно сократить количество вычисленных расстояний Левенштейна. Однако он имеет тенденцию явно недооценивать расстояние. freqDistApprox ускорить выполнение за счет приблизительного результата.
После того, как была найдена хорошая эвристика c, можно использовать разбиение двоичного пространства, сравнивать только векторы признаков, которые находятся рядом друг с другом (с приблизительное расстояние Левенштейна). Это можно сделать довольно эффективно, перебирая все векторы признаков и проверяя их окрестности. Сложность алгоритма составляет O(k n (L + D log(k))), где n - среднее количество ближайших соседей (с 0 < n <= k) и D размерность каждого вектора признаков.
Наконец, обратите внимание, что наихудший случай сложность по-прежнему составляет O(k^2), поскольку l может содержать O(k^2) пар, если все письма равны или почти равны (с очень маленьким расстоянием Левенштейна, это тот случай, когда n ~= k). Однако, когда письма сильно отличаются друг от друга (или порог расстояния достаточно мал) и используется хорошая эвристика c, результирующий подход должен быть значительно быстрее (с n << k).