Несколько занятных штук на почитать.
читать дальшеСперва перевод статьи Питера Норвига. Он пишет простой вариант (сама программа написана на питоне - но код можно не читать) подобной программы.
Краткая суть, как было сказано в другой статье:
поверить слово в словаре
если нет, сгенерировать однобуквенные ошибки, и проверить в словаре
если опять неудача, сгенерирвоать двубуквенные ошибки, и снова по словарю
+ к этому немного учета частоты употребления слов.
Статья: Как написать проверку орфографии («спеллчекер»)
Следующая статья - небольшая доработка. Там рассмартивается проблема добавления русского языка и отдельного словаря для него. А также проблема ошибочных раскладок.
Спеллчекер простой, доработанный
Дальше более сложный кандидат на изучение. Так как рассмотренный выше способ имеет серьезный недостаток: большое время работы даже для ошибок в две буквы. А ведь яндекс и гугл исправляют и по 4 неверных буквы в слове. В этой статье предлагается другой подход.
Для начала можно вспомнить что такое конечные автоматы и расстояние Левенштейна (отсылаю к вики).
Кстати, в статье вики расстояние Левенштейна в разделе формула я так и не поняла до конца что скрывается за обозначением: m(S1[i], S2[j]) *вероятно туплю*
Ну, и сама статья: Penisland, или как написать спеллчекер
Кстати, здесь тоже без вопросов у меня не обошлось. Построение конечного преобразователя, конечно, интуитивно понятно, от более точных указаний я бы не отказалась.
@темы:
Алгоритмы,
Программирование