Как работают программы проверки правописания?

Question

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

Я бы хотел написать это сам, хотя я действительно не знаю, с чего начать.

Answer 1

Читайте о дерева обхода. Основная концепция заключается в следующем:

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

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

Толковый словарь:

апекс яблоко назначить назначен

Дерево: (* указывает на действительный конец слова) обновление: спасибо Курту Сэмпсону за указание на то, что эта структура данных называется деревом Патрисии

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

Документ:

яблоко аппет апе

Результаты:

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

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

Answer 2

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

Answer 3

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

внезапно = внезапно + ля.

удалив ly's вы можете хранить только корневое слово.

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

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

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

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

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

Answer 4

E Джеймс дает отличный ответ о том, как сказать, является ли слово действительным. Вероятно, от проверки орфографии зависит, как они определяют возможные орфографические ошибки.

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

Если вы говорите, пишется: Страна как Контри. Сходство строк Левенштейна будет равно 1, так как вам нужно всего лишь добавить 1 букву, чтобы преобразовать страну в страну.

Затем вы можете просмотреть все возможные правильные варианты написания слов (только 171 000 английских слов и 3000 из них составляют 95% текста). Определите те, у кого наименьшее значение сходства строк Левенштейна, а затем верните верхние X слов, которые наиболее похожи на слово с ошибкой.

Существует отличный пакет на языке Python Fuzzy Wuzzy, который эффективно реализует это и генерирует% сходство между двумя словами или предложениями на основе этой формулы.

Answer 5

Хорошей отправной точкой может быть проверка орфографии Open Office Hunspell. Вот домашняя страница: http://hunspell.sourceforge.net/

Answer 6

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

Answer 7

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

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

Это также позволяет создавать текстовые интерпретаторы, такие как чат-боты