Что алгоритм дает предложениям в программе проверки правописания?
Какой алгоритм обычно используется при реализации программы проверки правописания, которая сопровождается с предложениями слова?
Сначала я думал, что могло бы иметь смысл проверять каждое новое введенное слово (если не найденный в словаре) против, он - расстояние Левенштейна от любого слова в словаре и возврате главных результатов. Однако это кажется, что было бы очень неэффективно, имея необходимость неоднократно оценивать весь словарь.
Как это обычно делается?
2 ответа
Есть хорошее эссе Питера Норвига о том, как реализовать корректор орфографии. По сути, это метод грубой силы, пробующий строки-кандидаты с заданным расстоянием редактирования. ( Здесь есть несколько советов, как можно улучшить производительность корректора орфографии, используя фильтр Блума и более быстрое хеширование кандидатов .)
Требования к проверке правописания слабее. Вам нужно только узнать, что слова нет в словаре. Вы можете использовать Фильтр Блума для создания средства проверки правописания, которое потребляет меньше памяти. Древняя версия описана в Programming Pearls Джона Бентли, использующего 64 КБ для английского словаря.
BK-Tree - альтернативный подход. Хорошая статья здесь .
Расстояние Левенштейна - не совсем правильное расстояние редактирования для проверки орфографии. Он знает только вставку, удаление и замену. Транспонирование отсутствует и дает 2 для транспозиции 1 символа (это 1 удаление и 1 вставка). Расстояние Дамерау – Левенштейна - это правильное расстояние редактирования.
Вам не нужно знать точное расстояние редактирования для каждого слова в словаре. Вы можете остановить алгоритм после достижения предельного значения и исключить слово. Это сэкономит вам много вычислительного времени.