Какой алгоритм обычно используется при реализации средства проверки правописания, которое сопровождается предложениями слов?
Сначала я подумал, что имеет смысл проверять каждое новое введенное слово (если оно не найдено в словаре) на расстояние Левенштейна от каждого другого слова в словаре и возвращать лучшие результаты. Однако это кажется крайне неэффективным, если придется многократно оценивать весь словарь.
Как это обычно делается?
Есть хорошее эссе Питера Норвига, как реализовать корректор орфографии. По сути, это метод грубой силы, пробующий строки-кандидаты с заданным расстоянием редактирования. ( Вот несколько советов, как повысить производительность корректора орфографии с помощью фильтра Блума и более быстрого хеширования кандидатов .)
Требования для проверки орфографии слабее. Вам нужно только узнать, что слова нет в словаре. Вы можете использовать фильтр Блума для создания средства проверки орфографии, которое потребляет меньше памяти. Древняя версия описана в Programming Pearls Джона Бентли с использованием 64 КБ для английского словаря.
BK-дерево представляет собой альтернативный подход. Хорошая статья здесь .
Расстояние Левенштейна - не совсем правильное расстояние редактирования для средства проверки орфографии. Он знает только вставку, удаление и замену. Транспонирование отсутствует и дает 2 для транспонирования 1 символа (это 1 удаление и 1 вставка). Расстояние Дамерау – Левенштейна - это правильное расстояние редактирования.
Подход к генерации предложений, который я успешно использовал, но нигде не встречал описанного, - это предварительное вычисление предложений (при построении словаря) с использованием «плохих» хэш-функций.
Идея состоит в том, чтобы посмотреть на типы орфографических ошибок, которые делают люди, и разработать хэш-функции, которые будут назначать неправильное написание тому же сегменту, что и его правильное написание.
Например, распространенной ошибкой является использование неправильной гласной, например, определения вместо определенного . Итак, вы создаете хеш-функцию, которая обрабатывает все гласные как одну и ту же букву. Самый простой способ сделать это - сначала «нормализовать» входное слово, а затем передать нормализованный результат через обычную хеш-функцию. В этом примере функция нормализации может отбросить все гласные, поэтому
definiteстановитсяdfnt. Затем "нормализованное" слово хешируется с помощью типичной хеш-функции.Вставьте все свои словарные слова во вспомогательный индекс (хеш-таблицу) с помощью этой специальной хеш-функции. У сегментов в этой таблице будут длинные списки конфликтов, потому что хеш-функция «плохая», но эти списки конфликтов по сути являются предварительно вычисленными предложениями.
Теперь, когда вы обнаруживаете слово с ошибкой, вы просматриваете списки конфликтов для сегмента, которому оно соответствует во вспомогательных индексах. Ta da: У вас есть список предложений! Все, что вам нужно сделать, это ранжировать слова на нем.
На практике вам понадобится несколько вспомогательных индексов с другими хэш-функциями для обработки других типов ошибок, таких как транспонированные буквы, одинарные / двойные буквы и даже упрощенный Soundex-подобный индекс для обнаружения фонетических орфографических ошибок. На практике я обнаружил, что упрощенные варианты произношения имеют большое значение и существенно устарели некоторые из них, предназначенные для поиска тривиальных опечаток.
Итак, теперь вы ищите орфографические ошибки в каждом из вспомогательных индексов и объединяете списки конфликтов перед ранжированием.
Помните, что списки конфликтов содержат только слова, которые есть в словаре. С помощью подходов, которые пытаются генерировать альтернативные варианты написания (как в статье Питера Норвига), вы можете получить (десятки) тысяч кандидатов, которых вам сначала нужно отфильтровать по словарю. При использовании заранее рассчитанного подхода у вас может быть пара сотен кандидатов, и вы знаете, что все они написаны правильно, поэтому вы можете сразу перейти к ранжированию.
Обновление : с тех пор я нашел одно описание алгоритма, похожее на это, распределенный поиск FAROO . Это все еще поиск с ограниченным расстоянием редактирования, но он очень быстрый, потому что этап предварительного вычисления работает как моя идея о «плохих хэш-функциях». FAROO просто использует ограниченную концепцию плохой хеш-функции.
источник
Алгоритм
оптимизация
Вы можете найти более подробное объяснение и исходный код в проекте github .
источник
Вам не нужно знать точное расстояние редактирования для каждого слова в словаре. Вы можете остановить алгоритм после достижения предельного значения и исключить слово. Это сэкономит вам много вычислительного времени.
источник
Проверка орфографии очень проста в реализации, как и в программе проверки орфографии Unix. Исходный код общедоступен. Может быть задействовано исправление, один из способов - внести правки и снова проверить, есть ли это новое слово в словаре. Такие новые правки можно сгруппировать и показать пользователю.
В системе Unix используется программа, написанная Мак Иллроем. Альтернативный способ - использовать Trie, который может быть полезен в случае больших файлов.
Подход unix требует очень мало места для огромного словаря, поскольку он использует алгоритм хеширования разброса.
источник