Оптимизированный способ поиска похожих строк

Question

Предположим, у меня есть большой список слов. (около 4-5 тысяч и увеличение). Кто-то искал строку. К сожалению, строка не найдена в списке слов. Теперь, какой был бы лучший и оптимизированный способ найти слова, похожие на входную строку? Первое, что пришло мне в голову, - это рассчитать расстояние Левенштейна между каждой записью словарного списка и входной строкой. Но разве это оптимизированный способ сделать это?

(Обратите внимание, что это не конкретный язык вопрос)

Answer 1

EDIT: новое решение

Да, вычисления расстояния Левенштейна между входом и список слов может быть разумный подход, но занимает много времени. BK-деревья могут улучшить это, но они быстро замедляются, так как расстояние Левенштейна становится больше.Кажется, мы можем ускорить вычисления расстояния Левенштейна используя синтаксического дерева, как описано в этом отличном блоге:

Fast and Easy Levenshtein distance using a Trie

Он основан на том, что динамическое программирование таблицы поиска для расстояния Левенштейна имеет общий строки в разных вызовах т.е. levenshtein(kate,cat) и levenshtein(kate,cats).

Запуск программы Python, приведенная на этой странице с TWL06 словаря дает:

> python dict_lev.py HACKING 1 
Read 178691 words into 395185 nodes 
('BACKING', 1) 
('HACKING', 0) 
('HACKLING', 1) 
('HANKING', 1) 
('HARKING', 1) 
('HAWKING', 1) 
('HOCKING', 1) 
('JACKING', 1) 
('LACKING', 1) 
('PACKING', 1) 
('SACKING', 1) 
('SHACKING', 1) 
('RACKING', 1) 
('TACKING', 1) 
('THACKING', 1) 
('WHACKING', 1) 
('YACKING', 1) 
Search took 0.0189998 s 

Это очень быстро, и будет еще быстрее и на других языках. Большую часть времени тратится на создание три, что не имеет значения, поскольку это нужно делать только один раз и хранить в памяти.

Единственный недостаток этого заключается в том, что попытки занимают много памяти (что может быть уменьшено с помощью DAWG за счет некоторой скорости).

Другой подход: У Питера Норвига отличная статья (с полным исходным кодом) по исправлению правописания.

http://norvig.com/spell-correct.html

Идея заключается в том, чтобы построить возможные изменения из слов, а затем выбрать наиболее вероятную коррекцию орфографии этого слова.

Answer 2

Я думаю, что что-то лучше, чем это существует, но BK деревья хорошая оптимизация от грубой силы, по крайней мере.

Он использует свойство расстояния Левенштейн является метрическим пространством, и, следовательно, если вы получаете Левенштейн расстояния d между query и произвольной строкой s из Словаря, то все ваши результаты должны быть на расстоянии от (d+n) to (d-n) до s. Здесь n - максимальное расстояние Левенштейна от запроса, который вы хотите вывести.

Это объясняется здесь подробно: http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees

Answer 3

Если вы заинтересованы в самом самом коде реализован алгоритм для нахождения оптимального выравнивания между двумя строками. Он в основном показывает, как преобразовать одну строку в другую с помощью операций k (где k - это Levenstein/Edit Distance строк). Он может быть упрощен для ваших нужд (поскольку вам нужно только дистанционное расстояние). Кстати, он работает в O(mn), где m и n - это длины строк. Моя реализация основана на: this и this.

#optimalization: using int instead of strings: 
#1 ~ "left", "insertion" 
#7 ~ "up", "deletion" 
#17 ~ "up-left", "match/mismatch" 
def GetLevenshteinDistanceWithBacktracking(sequence1,sequence2): 

distances = [[0 for y in range(len(sequence2)+1)] for x in range(len(sequence1)+1)] 
backtracking = [[1 for y in range(len(sequence2)+1)] for x in range(len(sequence1)+1)] 

for i in range(1, len(sequence1)+1): 
    distances[i][0]=i 
for i in range(1, len(sequence2)+1): 
    distances[0][i]=i 

for j in range(1, len(sequence2)+1): 
    for i in range(1, len(sequence1)+1): 
     if sequence1[i-1] == sequence2[j-1]: 
      distances[i][j]=distances[i-1][j-1] 
      backtracking[i][j] = 17 
     else: 
      deletion = distances[i-1][j]+1 
      substitution = distances[i-1][j-1]+1 
      insertion = distances[i][j-1] + 1 
      distances[i][j]=min( deletion, substitution, insertion) 

      if distances[i][j] == deletion: 
       backtracking[i][j] = 7 
      elif distances[i][j] == insertion: 
       backtracking[i][j] = 1 
      else: 
       backtracking[i][j] = 17 

return (distances[len(sequence1)][len(sequence2)], backtracking) 

def Alignment(sequence1, sequence2): 

cost, backtracking = GetLevenshteinDistanceWithBacktracking(sequence1, sequence2) 

alignment1 = alignment2 = "" 

i = len(sequence1) 
j = len(sequence2) 

#from backtracking-matrix we get optimal-alignment 
while(i > 0 or j > 0): 
    if i > 0 and j > 0 and backtracking[i][j] == 17: 
     alignment1 = sequence1[i-1] + alignment1 
     alignment2 = sequence2[j-1] + alignment2 
     i -= 1 
     j -= 1 
    elif i > 0 and backtracking[i][j] == 7: 
     alignment1 = sequence1[i-1] + alignment1 
     alignment2 = "-" + alignment2 
     i -= 1 
    elif j > 0 and backtracking[i][j]==1: 
     alignment2 = sequence2[j-1] + alignment2 
     alignment1 = "-" + alignment1 
     j -= 1 
    elif i > 0: 
     alignment1 = sequence1[i-1] + alignment1 
     alignment2 = "-" + alignment2 
     i -= 1 

return (cost, (alignment1, alignment2)) 

---

Это зависит от более широкого контекста и как точно вы хотите быть. Но то, что я бы (вероятно) начинал с:

1. Учитывать только подмножество, которое начинается с того же символа, что и слово запроса. Это уменьшит объем работы на ~ 20 для одного запроса.
2. Я бы классифицировал слова в соответствии с их длиной и для каждой категории позволял бы максимальное расстояние быть другим числом. В случае 4 категорий, например: 0 - если длина находится между 0 и 2; 1 - если длина составляет от 3 до 5; 2 - если длина составляет от 6 до 8; 3 - если длина равна 9+. Затем, основываясь на длине запроса, вы можете просто проверить слова из данной категории. Кроме того, не должно быть трудно реализовать алгоритм остановки, когда max. distance был превышен.
3. При необходимости начните думать о внедрении подхода machine learning.