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

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

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

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

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

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

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

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

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

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

    Документ:

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

    Результаты:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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