Что хороший алгоритм должен пересечь Trie для проверки на написание предложений?
Предположение, что генерал Trie слов словаря создается, каков был бы лучший метод для проверки на 4 случая орфографических ошибок - замена, удаление, перемещение и вставка во время обхода?
Один метод должен выяснить все слова на расстояниях редактирования n пообещанного и затем проверяющий на них в Trie. Это не плохая опция, а лучшая интуиция здесь, кажется, использование динамическое программирование (или рекурсивный эквивалент) метод для определения лучших подпопыток, изменив слова во время обхода.
Любые идеи приветствовались бы!
PS, ценила бы фактические исходные данные, а не просто связывается в ответах.
4 ответа
Я на самом деле написал код для этого на днях:
https://bitbucket.org/teoryn/spell-checker/src/tip/spell_checker.py
Это основан на коде Питера Норвига ( http://norvig.com/spell-correct.html ), но хранит словарь в дереве для более быстрого поиска слов в пределах заданного расстояния редактирования.
Алгоритм проходит по дереву рекурсивно, применяя возможные изменения (или нет) на каждом этапе пути, потребляя буквы из входного слова. Параметр рекурсивного вызова указывает, сколько еще изменений можно сделать. Trie помогает сузить область поиска, проверяя, какие буквы действительно могут быть доступны из данного префикса. Например, при вставке символа вместо добавления каждой буквы в алфавит мы добавляем только буквы, доступные из текущего узла. Отказ от редактирования эквивалентен взятию ветви от текущего узла в дереве вдоль текущей буквы от входного слова. Если этой ветки нет, мы можем вернуться и избежать поиска в возможно большом пространстве, где не могут быть найдены настоящие слова.
Я думаю, вы можете сделать это с помощью прямого поиска по дереву: выберите порог количества ошибок, которые вы ищете, просто пробегайтесь по буквам слова, которые нужно сопоставить, по одной за раз, генерируя набор пар (префикс, субтри), достигнутых до сих пор, соответствующих префиксу, и пока вы находитесь ниже порога ошибок, добавьте к вашему набору следующие подцели:
- Нет ошибки в этом месте символа: добавьте подцель тройки в следующем символе слова
- Вставленный, удаленный или замененный символ в этом месте: найдите там соответствующую тройку и увеличьте счетчик ошибок;
- Не дополнительная цель, но обратите внимание, что транспозиции - это либо вставка, либо удаление, совпадающее с более ранним удалением или вставкой: если этот тест выполняется, то не увеличивайте счетчик ошибок.
Это кажется довольно наивным: есть ли в этом проблема, которая навела вас на мысль о динамическом программировании?
.Предполагая, что каждый последующий символ в вашем слове представляет один уровень в вашем дереве, тогда у вас есть пять падежей, которые нужно проверить для каждого символа (совпадение, удаление, вставка, замена и транспонирование). Я предполагаю, что транспозиции - это два соседних символа.
Вам понадобится функция (CheckNode), которая принимает узел дерева и символ для проверки. Ему нужно будет вернуть набор (дочерних / внучатых) узлов, представляющих совпадения.
Вам понадобится функция (CheckWord), которая принимает слово. Он проверяет каждый символ по очереди на набор узлов. Он вернет набор (листовых) узлов, представляющих совпадающие слова.
Идея состоит в том, что каждый уровень в дереве (дочерний, внучатый и т. Д.) Соответствует положению символа в слове. Если вы вызовете узел дерева верхнего уровня, уровень 0, тогда у вас будет уровень 1, уровень 2 и т. Д.
Очевидно, что для слова без ошибок существует взаимно однозначное соответствие между позицией символа и уровнем в дерево.
Для удаления вам нужно пропустить уровень в дереве.
Для вставки нужно пропустить символ в слове.
Для замен нужно пропустить и уровень, и персонажа.
Для транспонирования вам необходимо (временно) поменять местами символы в слове.
Обратите внимание на вычисление расстояния Левенштейна , которое обеспечивает решение динамического программирования для нахождения расстояния между двумя последовательностями.