Какой алгоритм обычно используется при реализации проверки орфографии, которая сопровождается предложениями слов?
Сначала я подумал, что имеет смысл проверять каждое новое введенное слово (если не найдено в словаре) расстояние Левенштейна от каждого другое слово в словаре и возвращение лучших результатов. Тем не менее, похоже, что это было бы очень неэффективно, нужно было бы многократно оценивать весь словарь.
Как это обычно делается?
Существует хорошее сочинение Питера Норвига, как реализовать корректор орфографии. Это в основном подход грубой силы, который пытается использовать строки-кандидаты с заданным расстоянием редактирования. (Вот несколько советов, как вы можете улучшить производительность корректора орфографии, используя Bloom Фильтр и более быстрое хэширование кандидатов.)
Требования для проверки орфографии слабее. Вам нужно только выяснить, что слова нет в словаре. Вы можете использовать Bloom Filter для создания проверки орфографии, которая потребляет меньше памяти. Древние версии описываются в Программирование Pearls от Jon Bentley с использованием 64kb для английского словаря.
A BK-Tree - альтернативный подход. Хорошая статья здесь.
Расстояние Левенштейна - это не совсем правильное расстояние редактирования для проверки орфографии. Он знает только вставку, удаление и замену. Транспонирование отсутствует и выдает 2 для транспонирования 1 символа (это 1 удаление и 1 вставка). Расстояние Дамерау-Левенштейна - это правильное расстояние редактирования.
Подход для создания предложений, которые я использовал успешно, но никогда не видел нигде, - это предварительное вычисление предложений (при построении словаря) с помощью "плохих" хеш-функций.
Идея состоит в том, чтобы посмотреть на типы ошибок орфографии, которые создаются людьми, и создавать хеш-функции, которые назначали бы неправильное написание в том же ведре, что и его правильное написание.
Например, распространенная ошибка заключается в использовании неправильного гласного, например, определенного вместо определенного. Таким образом, вы создаете хеш-функцию, которая обрабатывает все гласные как одну и ту же букву. Легкий способ сделать это - сначала "нормализовать" входное слово, а затем поместить нормализованный результат через обычную хэш-функцию. В этом примере нормализующая функция может удалить все гласные, поэтому definite становится dfnt. "Нормализованное" слово хэшируется с типичной хэш-функцией.
Вставьте все словарные слова во вспомогательный индекс (хеш-таблицу), используя эту специальную хэш-функцию. Ведра в этой таблице будут иметь длинный список столкновений, потому что хеш-функция "плохая", но эти списки столкновений являются по существу предварительными расчетами.
Теперь, когда вы найдете слово с ошибкой, вы просматриваете списки столкновений для ведра, с которым отображается орфографическая ошибка во вспомогательных индексах. Ta da: У вас есть список предложений! Все, что вам нужно сделать, это ранжировать слова на нем.
На практике вам понадобятся несколько вспомогательных индексов с другими хэш-функциями для обработки других типов ошибок, таких как транспонированные буквы, однократная/двойная буква и даже упрощенная Soundex-подобная, чтобы поймать фонетические орфографические ошибки. На практике я нашел простейшие произношение, чтобы пройти долгий путь и по существу устаревшие некоторые из них, предназначенные для поиска тривиальных опечаток.
Итак, теперь вы просматриваете орфографические ошибки в каждом из вспомогательных индексов и объединяете списки конфликтов перед ранжированием.
Помните, что в списках столкновений содержатся только слова, которые находятся в словаре. С подходами, которые пытаются сгенерировать альтернативные варианты написания (как в статье Питера Норвига), вы можете получить (десятки) тысяч кандидатов, которые вы сначала должны фильтровать против словаря. С заранее рассчитанным подходом вы получаете, может быть, пару сотен кандидатов, и вы знаете, что все они правильно написаны, поэтому вы можете перейти прямо к ранжированию.
Обновление. С тех пор я нашел одно описание алгоритма, подобное этому, распределенный поиск FAROO. Это все еще ограниченный поиск с дистанцией редактирования, но он очень быстрый, потому что шаг предварительного расчета работает, как идея "плохой хеш-функции". FAROO просто использует ограниченную концепцию плохой хэш-функции.
Вам не нужно знать точное расстояние редактирования для каждого слова в словаре. Вы можете остановить алгоритм после достижения предельного значения и исключить слово. Это сэкономит вам много времени.
Проверка орфографии очень проста в использовании, как в программе заклинаний Unix. Исходный код доступен публично. Коррекция может быть задействована, один способ - сделать изменения и снова проверить, находится ли это новое слово в словаре. Такие новые изменения могут быть сгруппированы и показаны пользователю.
Система Unix использует программу, написанную Mc IllRoy. Альтернативный способ - использовать Trie, который может быть полезен в случае огромных файлов.
В подходе unix требуется очень мало места для огромного словаря, так как он использует алгоритм хеширования.