Как найти, что два слова отличаются на сколько расстояние >> Есть ли кратчайший путь для этого

Question

Я читал о расстоянии Левенштейна о расчете расстояния между двумя разными словами.

У меня есть одна исходная строка, и я должен сопоставить ее со всеми 10000 целевых слов.Ближайшее слово должно быть возвращено.

Проблема в том, что я дал список из 10000 целевых слов, и входные исходные слова также огромны ... Так какой кратчайший и эффективный алгоритм применить здесь.Расчет расстояния Левенштейна для каждой n каждой комбинации (логика грубой силы) будет очень трудоемким.

Любые подсказки или идеи приветствуются.

Answer 1

Я думаю, это немного зависит от того, как структурированы слова.Например, этот парень улучшил реализацию , основываясь на том факте, что он обрабатывает свои слова по порядку и не повторяет вычисления для общих префиксов.Но если все ваши 10000 слов совершенно разные, это не принесет вам пользы.Он написан на python, поэтому для переноса на C. может потребоваться немало усилий.

Существуют также некие доморощенные алгоритмы .это) но это могло бы сработать.

Answer 2

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

Более сложный, но более эффективный подход - Levenshtein Automata . Это работает путем создания NFA, который распознает все слова в пределах расстояния x по левенштейну от вашей целевой строки, затем выполняет итерацию по нему и словарю в режиме lockstep, эффективно выполняя слияние с ними.