Каков хороший алгоритм для обхода Trie для проверки правописания?

Question

Предполагая, что построено общее три словарных слова, каков будет лучший способ проверить 4 случая орфографических ошибок - подстановка, удаление, транспонирование и вставка во время обхода?

Один из методов заключается ввычислите все слова в пределах n, отредактируйте расстояния данного слова и затем проверьте их в Trie.Это не плохой вариант, но лучшей интуицией здесь, по-видимому, является использование метода динамического программирования (или рекурсивного эквивалента) для определения лучших попыток после изменения слов во время обхода.

Любые идеибудет приветствоваться!

PS. Буду признателен за фактические данные, а не за ссылки в ответах.

Answer 1

Я на самом деле написал код, чтобы сделать это на днях:

https://bitbucket.org/teoryn/spell-checker/src/tip/spell_checker.py

Он основан на коде Питера Норвиг (http://norvig.com/spell-correct.html)), но хранит словарь в три для быстрого поиска слов на заданном расстоянии редактирования.

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

Answer 2

Я думаю, что вы можете сделать это с помощью простого поиска в дереве по ширине: выберите порог числа ошибок, которые вы ищете, просто пропустите буквы слова, которые должны совпадать по одной, генерируя набор пар (префикс, поддерево), достигнутый на данный момент, совпадающий с префиксом, и, пока вы находитесь ниже порога ошибки, добавьте к вашему набору следующих подцелей:

1. Нет ошибок в этом месте символа: добавьте подцель дерева в следующий символ в слове
2. Вставленный, удаленный или замещенный символ в этом месте: найдите там соответствующий три и увеличьте счетчик ошибок;
3. Не дополнительная цель, но обратите внимание, что транспонирование - это либо вставка, либо удаление, которое соответствует более раннему удалению или вставке: если этот тест удерживается, не увеличивайте счетчик ошибок.

Это кажется довольно наивным: есть ли проблема с этим, которая заставила вас задуматься о динамическом программировании?

Answer 3

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

Вам понадобится функция (CheckNode), которая принимает узел дерева и символ для проверки.Потребуется вернуть набор (дочерних / внучатых) узлов, представляющих совпадения.

Вам понадобится функция (CheckWord), которая принимает слово.Он проверяет каждый символ по очереди на множество узлов.Он вернет набор (листовых) узлов, представляющих совпавшие слова.

Идея состоит в том, что каждый уровень в дереве (дочерний, внучатый и т. Д.) Соответствует позиции символа в слове.Если вы вызовете узел дерева верхнего уровня, уровень 0, то у вас будет уровень 1, уровень 2 и т. Д.

Очевидно, что для слова без ошибок существует однозначное соответствие между позицией символа иуровень в дереве.

Для удаления необходимо пропустить уровень в дереве.

Для вставки необходимо пропустить символ в слове.

Длязамены, вам нужно пропустить и уровень, и символ.

Для транспонирования вам необходимо (временно) поменять местами символы в слове.

Answer 4

Взгляните на вычисление расстояния Левенштейна , которое обеспечивает решение для динамического программирования для определения расстояния между двумя последовательностями.