Я программирую spellcheck программу в Python. У меня есть список допустимых слов (словарь), и я должен произвести список слов из этого словаря, которые имеют расстояние редактирования 2 от данного недопустимого слова.
Я знаю, что должен запустить путем генерации списка с расстоянием редактирования одного от недопустимого слова (и затем выполнить это снова на всех сгенерированных словах). У меня есть три метода, вставляет (...), удаления (...) и изменяется (...), который должен произвести список слов с расстоянием редактирования 1, где вставляет выводы все допустимые слова с еще одной буквой, чем пообещанный, выводы удалений все допустимые слова с одним меньшим количеством буквы, и изменяет выводы все допустимые слова с одной другой буквой.
Я проверил набор мест, но я, может казаться, не нахожу алгоритм, который описывает этот процесс. Все идеи, которые я придумал, включают цикличное выполнение через список словаря многократно, который был бы чрезвычайно трудоемким. Если бы кто-либо мог бы предложить некоторое понимание, я был бы чрезвычайно благодарен.
Конкретный алгоритм, который вы описываете, называется расстоянием Левенштейна. Быстрый поиск в Google позволяет найти несколько библиотек Python и рецептов для его вычисления.