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

Read на Обход дерева . Фундаментальное понятие следующие:

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

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

Словарь:

яблоко вершины назначают назначенными

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

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

Документ:

яблоко appint обезьяна

Результаты:

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

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

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

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

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

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

путем удаления ly's можно уйти, храня просто корневое слово.

Аналогично предварительно выделяют = пред +, выделяют.

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