Учитывая огромную базу данных разрешенных слов (отсортированных по алфавиту) и слово, найдите слово из базы данных, которая является ближайшей к данному слову с точки зрения расстояния Левенштейна.
Наивный подход, конечно, состоит в том, чтобы просто вычислить левенштейновское расстояние между данным словом и всеми словами в словаре (мы можем выполнить бинарный поиск в базе данных, прежде чем вычислять расстояния).
Интересно, есть ли более эффективное решение этой проблемы? Может быть, какая-то эвристика, которая позволяет нам сократить количество слов для поиска или оптимизации алгоритма расстояния Левенштейна.
Ссылки на статьи по теме приветствуются.
источник
Автоматы Левенштейна: http://en.wikipedia.org/wiki/Levenshtein_automaton
BK деревья: http://en.wikipedia.org/wiki/BK-tree
источник
Если у вас есть небольшое количество неправильных правок, которые вы собираетесь терпеть, то вы можете попытаться использовать дерево суффиксов с точками . Отказ от ответственности: я написал эту статью, но она решает то, что вы хотите: у него высокая стоимость дискового пространства, но запросы действительно быстрые.
В общем, лучше взглянуть на это с другой стороны: у вас есть индекс всех слов в словаре. Теперь для входного слова w, если оно есть в словаре, остановитесь. В противном случае создайте все варианты на расстоянии 1 и найдите их. Если их там нет, поищите варианты на расстоянии 2 и так далее ...
Есть несколько улучшений этой основной идеи.
источник
Простое решение - хранить слова как три. Затем вы можете вычислить расстояние Левенштейна слова запроса по отношению к три с помощью стандартного алгоритма динамического программирования, вместо того, чтобы вычислять его по каждому слову в отдельности. В худшем случае временная сложность не улучшается асимптотически, но если сначала развернуть наиболее многообещающие ветви, вы получите что-то вроде времени для длины запроса m , размера алфавита σO(mk+1⋅σk) m σ k
источник
Я написал ответ на очень похожий вопрос на cs.stackexchange.com ( /cs//a/2096/1490 ), а затем нашел этот вопрос. Ответ есть для приблизительного поиска ближайшего соседа на расстоянии редактирования (т. Е. Алгоритм выводит строку, которая примерно так же близка к строке запроса, как и ближайший сосед строки запроса). Я публикую здесь, так как я не нахожу никаких ссылок, которые я дал там в ответах, приведенных здесь.
источник
Я думаю, что вам нужен алгоритм Вагнера-Фишера: https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm Основная идея заключается в том, что, поскольку словарь, через который вы проходите, отсортирован, два слова подряд очень вероятно, что у них будет длинный префикс, поэтому вам не нужно обновлять всю матрицу для каждого расчета расстояния.
источник
Вы можете использовать Вы имели в виду?
А затем найдите расстояние Левенштейна между ответом, возвращаемым «Вы имели в виду» »и строкой ввода, используя динамическое программирование.
источник
Did you mean?
особенность. Кроме того,Did you mean?
возвращает слово, которое очень близко к заданному входу и делает это довольно эффективно. :)Одним из способов является обучение модели машинного обучения для сопоставления слов с векторами и сопоставления расстояния Левенштейна с евклидовым расстоянием. Затем вы можете построить KDTree из векторов для словаря, который вы хотите использовать. Я создал блокнот Jupyter, который делает это здесь: https://gist.github.com/MichaelSnowden/9b8b1e662c98c514d571f4d5c20c3a03
Согласно комментариям DW:
Краткое описание структуры модели:
Мои тренировочные данные - это просто случайные строки, но я думаю, что результаты могли бы действительно улучшиться, если бы тренировочные данные были (опечатка / правильное слово) парами. Я просто использовал,
/usr/share/dict/words
потому что он общедоступен.источник