Developing.ru

Задача такая: на входе есть правильно написанное слово, на выходе надо получить список возможных вариантов опечаток.

Буду благодарен любым идеям, у самого есть такие:

1. Пропуск буквы
2. Дублирование буквы
3. Перестановка соседних букв.
4. Замена буквы на соседнюю по клавиатуре.

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

Спасибо.

Еще у меня случается что не замена буквы на соседнюю по клавиатуре, а добавляется соседняя
например приветь
И еще на мягких клавиатурах бывает попадание буков, лежащих н апути между соседними - например
гид - "грид" (просто палец не поднимаешь а ведешь по клавишам - вот промежуточная и срабатывает)

В Punto Switcher подобный алгоритм используется. Правда для коррекции очепяток. Но 100% там именно статистическая инфа используется (видимо не только, но не суть). Интересно, они её сами набирали, или же готовое брали?

Насколько я помню пару лет назад была статья о пунто свитчере там указывался другой алгоритм.
что-то вроде есть статистика сочетаний русских буков и английских и на основе данных таблиц делается вывод о том какую раскладку пользовать.
ТОгда же авторы писали что они сами составляли данные таблицы.
Правда с нуля или просто обобщали имеющиеся данные - не уточнялось

Да, но кроме статистики сочетаний они использовали и наиболее рапространённые очепятки. Это было их ноу-хау.
Кстати, правильные сочетания можно у Кнута утянуть - он в TEX-е их для вычисления мест переносов использовал.

Во, ещё идея - использовать алгоритм Soundex. Это не совсем опечатки, скорее неправильное написание.

Во, ещё идея - использовать алгоритм Soundex

Soundex позволяет выяснить, являются ли 2 слова похожими по звучанию, а у тебя совсем другая задача - найти похожие по звучанию. Т.е. это однозначно не Soundex, а совсем наоборот.
Думаю было бы неэффективно генерить случайным образом много слов, а потом проверять их Sounex-ом на схожесть звучания.

По поводу пропуска букв: можно пропускать гласные буквы (желательно кроме первой и ударной). В большинстве случев читатель такую опечатку даже не замтит.

Обязательно нужно отдельно предусмотреть замену ЖИ/ШИ на ЖЫ/ШЫ Ну а также надо просто взять учебники русского языка для начальной школы переиначить все правила наоборот - вот и получатся весьма хорошие алгоритмы.

Можно вспомнить печатную машинку "великого комбинатора", которая не печатала "е" - и при замене "е" на "э" у нее появлялся грузинский акцент. Вообще, придание тексту звучания с каккиим нибудь аккцентом таам с фиинским, или еще каким нибудь - это весьма интелектуальная задача.
Например, было бы круто придумать алгоритм, который делает такое:
"Почему трубку не берешь?" --> "Пасущи, пачему турубка нэ бэрёшь, да?"

Это так пара идей навскидку... Может еще что придумаю...

PS
А можно робко поинтересоваться?
Это будет программа по рассылке спама или наоборот спам-фильтр или все-таки исправлятор опечаток

Можно конечно и для спама использовать, но это не мой профиль
Это для поиска. Есть два предположения: тот, кто ищет - грамотный человек, и тот кто текст писал, тоже грамотный. Но мог опечатки допускать. Поэтому, слава богу, конструкций типа аффтар жжот обрабатывать не надо

Oh, I see!

Да, вот еще что.
Не всегда опечтка\ошибка приводит к неверному написанию слова.
Так "неграмотное место" возможно нужно искать как "неграмотный место".
Вобщем, это частный случай преобразовния текста к тексту, отражающему акцент.

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

Ну, для этого есть готовые решения. Технология стемминг называется - бессловарное определение корня (не совсем корня, просто умное слово забыл ) слова.
Т.е. на самом деле ищут не грамотный -грамотное, а грамотн.

просто умное слово забыл

Основа

А в Punto, если мне память не изменяет, идея алгоритма в том, что определенные буквосочетания невозможны в том или ином языке, например, bdf в английском или фсу в русском.