Как работают проверки орфографии?

Ответ 1

Прочитайте Траверс дерева. Основная концепция такова:

• Прочитайте файл словаря в память (этот файл содержит весь список правильно записанных слов, которые являются возможными/общедоступными для данного языка). Вы можете скачать бесплатные словарные файлы онлайн. Один пример - java.sun.com
• Разберите этот файл словаря в дереве поиска, чтобы сделать фактический текстовый поиск максимально эффективным. Я не буду описывать все грязные детали этого типа древовидной структуры, но дерево будет состоять из узлов, которые имеют (до) 26 ссылок на дочерние узлы (по одному для каждой буквы), плюс флаг для указания или не текущий node - это конец действительного слова.
• Прокрутите все слова в вашем документе и проверьте каждый из них в дереве поиска. Если вы достигнете node в дереве, где следующая буква в слове не является допустимым дочерним элементом текущего node, слово не находится в словаре. Кроме того, если вы дойдете до конца своего слова, а флаг "действительный конец слова" не установлен на node, слово не находится в словаре.
• Если слово не найдено в словаре, сообщите об этом пользователю. На этом этапе вы также можете предлагать альтернативные варианты написания, но это немного сложнее. Вам придется прокручивать каждый символ в слове, заменяя альтернативные символы и проверять каждый из них на дереве поиска. Вероятно, есть более эффективные алгоритмы поиска рекомендуемых слов, но я не знаю, что они собой представляют.

Действительно короткий пример:

Словарь:

Назначение apex apple назначается

Дерево: (* указывает допустимый конец слова) update: Спасибо Curt Sampson за то, что эта структура данных называется Patricia Tree

A -> P -> E -> X*
      \\-> P -> L -> E*
           \\-> O -> I -> N -> T* -> E -> D*

Документ:

apple appint ape

Результаты:

• "яблоко" будет найдено в дереве, поэтому оно считается правильным.
• "appint" будет помечен как неверный. Пересекая дерево, вы будете следовать за A -> P -> P, но второй P не имеет дочернего I node, поэтому поиск не выполняется.
• "ape" также потерпит неудачу, так как E node в A -> P -> E не имеет установленного флага "действительный конец слова".

edit: Подробнее о предложениях по написанию см. в Levenshtein Distance, который измеряет наименьшее количество изменений это должно быть сделано для преобразования одной строки в другую. Лучшими предложениями будут словарные слова с самым маленьким Левенштейном. Расстояние до неправильно написанного слова.

Ответ 2

Учитывая, что вы не знаете, с чего начать, я бы предложил использовать существующее решение. См., Например, aspell (Лицензия GLPL). Если вам действительно нужно реализовать его самостоятельно, пожалуйста, сообщите нам, почему.

Ответ 3

Нужно смотреть на префиксы и суффиксы.

внезапно = внезапно + ly.

удалив, вы можете избавиться от хранения только корневого слова.

Аналогично preallocate = pre + allocate.

И любовно = любовь + ing + ly становится немного сложнее, так как вызывается английские правила для ing.

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

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

Я бы посоветовал прототипирование небольшим набором слов. Проведите много испытаний, затем увеличьте масштаб. Это замечательная образовательная проблема.

Ответ 4

Разделение слова на корень и суффикс является knonw как "Портерский алгоритм стемнинга", это хороший способ подгонки английского языка в удивительно маленькую память.
Это также полезно для ознакомления, поэтому "проверка орфографии" также найдет "проверку орфографии" и "проверку орфографии"

Ответ 5

Я сделал это в классе

Вы должны рассмотреть python Natural Language Toolkit NLTK, который специально разработан для этого.

Он также позволяет создавать текстовые интерпретаторы, такие как chatbots

Ответ 6

Проверка орфографии Open Office Hunspell может быть хорошей отправной точкой. Вот домашняя страница: Hunspell в Sourceforge