Как называются семейство алгоритмов типа того что Google использует для исправления потенциальных опечаток в поисковых фразах.

Здравствуйте, Igor Sukhov, Вы писали:

IS>Как называются семейство алгоритмов типа того что Google использует для исправления потенциальных опечаток в поисковых фразах.

Spell Checkers?

Норвиг, когда пишет про Google, никак особенно алгоритм не называет:
http://norvig.com/spell-correct.html

Aspell, например, использует (в числе прочего) Metaphone:
http://aspell.net/metaphone/

Здравствуйте, z00n, Вы писали:

IS>>Как называются семейство алгоритмов типа того что Google использует для исправления потенциальных опечаток в поисковых фразах.

Z>Spell Checkers?

Z>Норвиг, когда пишет про Google, никак особенно алгоритм не называет:
Z>http://norvig.com/spell-correct.html

Z>Aspell, например, использует (в числе прочего) Metaphone:
Z>http://aspell.net/metaphone/

спасибо за ссылки, посмотрю. но наверно лучше уточнить вопрос.
тут даже не спел чекер нужен а SpellEx =).

задача примерно такая — есть некая небольшая база правильных слов (<= 100)
— названия переменных. Нужно сделать вот что — по введенному пользователем
части идентификатора предложить выбрать наиболее близкий по написанинию.

Хотелось чтобы алгоритм был умным и понимал такое как:

*пользователь напеча часть идентификатора
*пользователь напеМатал не ту букву (и более чем одну)
*пользователь напеЧЧЧаталЛ букву несколько раз.
*пользователь пропстил букву
и их комбинации и еще чтото.

кажется такое есть в IPhone.

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

вопрос — какая это должна быть ф-я?

Здравствуйте, Igor Sukhov, Вы писали:

IS>Здравствуйте, z00n, Вы писали:

IS>>>Как называются семейство алгоритмов типа того что Google использует для исправления потенциальных опечаток в поисковых фразах.

IS>Хотелось чтобы алгоритм был умным и понимал такое как:

IS>*пользователь напеча часть идентификатора
IS>*пользователь напеМатал не ту букву (и более чем одну)
IS>*пользователь напеЧЧЧаталЛ букву несколько раз.
IS>*пользователь пропстил букву
IS>и их комбинации и еще чтото.

IS>кажется такое есть в IPhone.

IS>В общем нужна т-я ф-я которая переводит базу слов в базу каких нить значений и
IS>далее мы берем ввод пользователя, вычисляем значение ф-и для этого ввода и
IS>сравниваем с уже имеющимся.

IS>вопрос — какая это должна быть ф-я?

Метрика Левенштейна. Другое название для нее "дистанция редактирования" (edit distance)
Но п.1 (про часть идентификатора) нужно реализовывать самому

Здравствуйте, Vadim M, Вы писали:

IS>>вопрос — какая это должна быть ф-я?

VM>Метрика Левенштейна. Другое название для нее "дистанция редактирования" (edit distance)
VM>Но п.1 (про часть идентификатора) нужно реализовывать самому

спасибо, похоже то что нужно. и достаточно просто.