Способ реализации "Получить все строки с расстоянием Левенштейна меньше X"

Question

Мне интересно, есть ли эффективная структура данных для выполнения «Извлечь все строки с расстоянием Левенштейна меньше X».

Мало что мне интересно:

• Объяснение алгоритма.
• Существует ли существующая реализация в существующей базе данных / языке программирования?
• Статья / статья, на которую я могу сослаться?

Answer 1

это поиск ближайшего соседа в метрическом пространстве с расстоянием Левенштейна в качестве метрической (или дистанционной) функции

a VP-дерево является одним из способов решения этой проблемы

this Реализация Python VP-дерева - это рабочая демонстрация, которая показывает, как работает VP-дерево, запускает его, скажем, в списке слов, предоставляет интерактивную оболочку, где вы вводите слово, и возвращает слова этот список не более чем на расстояние X от введенного вами слова

Answer 2

Походит на простой поиск в ширину , где каждое поколение находится всего в одном «редактировании» от предыдущего - и с проверками на месте, чтобы гарантировать, что строка появляется в одном-единственном-одномlevel.

Это легко реализовать, используя пару хеш-наборов / хеш-таблиц в паре циклов.