Какой алгоритм дает предложения в проверке орфографии?

какой алгоритм обычно используется при реализации проверки орфографии, которая сопровождается предложениями word?

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

5 104
language-agnostic algorithm spell-checking levenshtein-distance

5 ответов:

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

требования к проверке орфографии слабее. Вам нужно только узнать, что слова нет в словаре. Вы можно использовать Bloom Filter чтобы построить проверку орфографии, которая потребляет меньше памяти. Древняя версия описана в Жемчужины Программирования Джон Бентли, используя 64kb для английского словаря.

A BK-Tree альтернативный подход. Хорошая статья здесь.

расстояние Левенштайна не совсем правильное расстояние редактирования для проверки орфографии. Он знает только вставки, удаления и замены. Транспонирование отсутствует и производит 2 для транспозиции 1 символа (это 1 удаление и 1 вставка). Дамерау–Левенштейна расстояние право изменить дистанцию.

184

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

идея состоит в том, чтобы посмотреть на типы орфографических ошибок, которые делают люди, и разработать хэш-функции, которые назначили бы неправильное написание тому же ведру, что и его правильное написание.

например, распространенной ошибкой является использование неправильной гласной, например definate вместо определенный. Таким образом, вы создаете хэш-функцию, которая обрабатывает все гласные как одну и ту же букву. Простой способ сделать это-сначала "нормализовать" входное слово, а затем поместить нормализованный результат через обычную хэш-функцию. В этом примере функция нормализации может отбросить все гласные, поэтому definite становится dfnt. "Нормализованное" слово затем хэшируется с помощью типичной хэш-функции.

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

теперь, когда вы находите слово с ошибками, вы просматриваете списки столкновений для ведра, которое отображается с ошибками во вспомогательных индексах. Та да: у вас есть список предложений! Все, что вам нужно сделать, это ранжировать слова на нем.

на практике, вам понадобится несколько вспомогательных индексов с другими хэш-функциями для обработки других типов ошибок, таких как транспонированные буквы, одиночная/двойная буква и даже упрощенный Soundex-подобный, чтобы поймать фонетические ошибки написания. На практике я нашел упрощенные произношения, которые прошли долгий путь и по существу устарели некоторые из них, предназначенные для поиска тривиальных опечаток.

Итак, теперь вы просматриваете орфографические ошибки в каждом из вспомогательных индексов и объединяете списки коллизий раньше ранжирование.

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

обновление: С тех пор я нашел одно описание алгоритма, похожее на это,фару распределенный Поиск. Это все еще ограниченный поиск на расстоянии редактирования, но он очень быстрый, потому что шаг предварительного расчета работает как моя идея "плохих хэш-функций". Фару просто использует ограниченную концепцию плохой хэш-функции.

16

алгоритм

  1. возьмите неверно написанное слово в качестве входных данных.
  2. сохранить список английских слов вместе с их частотами в текстовом файле.
  3. вставьте все доступные английские слова (сохраненные в текстовом файле) вместе с их частотами (мера того, как часто слово используется в английском языке) в троичном дереве поиска.
  4. теперь пройдите вдоль троичного дерева поиска -
    • для каждого слова, встречающегося в тернарном Поиск дерева, вычислить его Levensthein расстояние от неправильно написанного слова.
    • Если расстояние Levensthein
    • Если два слова имеют одинаковое расстояние редактирования, один с более высокой частотой терка. Распечатайте 10 лучших элементов из очереди приоритетов.

оптимизация

  1. вы можете выделить слова в поддереве текущего узла, если расстояние редактирования подстроки входного слова от текущее слово терка, чем 3.
    Вы можете найти более подробное описание и исходный код проект github.
5

вам не нужно знать точное расстояние редактирования для каждого слова в словаре. Вы можете остановить алгоритм после достижения предельного значения и исключить слово. Это сэкономит вам много вычислительного времени.

2

проверка орфографии очень проста в реализации, как в программе заклинаний Unix. Исходный код доступен в открытом доступе. Коррекция может быть задействована, один из методов-сделать правки и снова проверить, есть ли это новое слово в словаре. Такие новые изменения могут быть сгруппированы и показаны пользователю.

система Unix использует программу, написанную Mc IllRoy. Альтернативный способ-использовать Trie, который может быть полезен в случае огромных файлов.

подход unix требует очень меньше места для огромного словаря, так как он использует алгоритм разброса хэша.

1