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

Question

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

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

Answer 1

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

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

Очень короткий пример:

Словарь:

Апекс Яблоко назначен назначен

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

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

Документ:

яблочный аппетит

Результаты:

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

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

Answer 2

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

Answer 3

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

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

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

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

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

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

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

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

Answer 4

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

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

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

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

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

Answer 5

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

Answer 6

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

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

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

Answer 7

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