Поиск опечаток

[Роберт]

Как Word/Google/Янекс находит опечатки? По какому принципу?
Функция Soundex тут точно не поможет, так как там поиск звучания (присваивание одинаковым звукам близких значений), а опечатка - чисто математическая функция. Но как правильно реализовать?

P.S. Только БЕЗ словофом и морфологических анализов изначального слова в именительном подеже...

 

[Redjik]

Поставь Sphinx

У него эта плюшка из коробки работает

 

[Sender]

Почитай про расстояние Левенштейна

 

[Роберт]

Неее... Расстояние Левенштейна это уже больше к определению весов в зависимости от опечатки.
А я интересуюсь больше по поводу самого алгоритма поиска возможных вариантов опечаток.
Может я что-то упустил?

P.S. В моём случа поиск идёт по городам и населённым пунктам России (их около 160 тысячь, так что оценка того, на что больше похожа опечатка, несколько иная)

 

[A1x]

Поставь Sphinx
У него эта плюшка из коробки работает

что-то не помню такого прямо "из коробки", я делал как здесь описано - http://habrahabr.ru/blogs/sphinx/61807/

 

[Sender]

Неее... Расстояние Левенштейна это уже больше к определению весов в зависимости от опечатки.
А я интересуюсь больше по поводу самого алгоритма поиска возможных вариантов опечаток.
Может я что-то упустил?

P.S. В моём случа поиск идёт по городам и населённым пунктам России (их около 160 тысячь, так что оценка того, на что больше похожа опечатка, несколько иная)

почитай еще

 

[Роберт]

Sender, что я пропустил?

 

[Sender]

Что возвращает и какие аргументы принимает функция расстояния Левенштейна? Чем является возвращаемое значение?

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

Даже на вики написано http://ru.wikipedia.org/wiki/Расстояние_Левенштейна:

{{{
Применение

Расстояние Левенштейна и его обобщения активно применяется:
для исправления ошибок в слове (в поисковых системах, базах данных, при вводе текста, при автоматическом распознавании отсканированого текста или речи).
}}}

Тебе же это и надо?

 

[Redjik]

что-то не помню такого прямо "из коробки", я делал как здесь описано - http://habrahabr.ru/blogs/sphinx/61807/

Положа руку на сердце, все никак руки не доходят самому поставить sphinx, судя по презентации (zend), этот функционал работает из коробки.
Парень, который вел презентацию несколько раз на этом акцент ставил.

 

[alekciy]

Положа руку на сердце, все никак руки не доходят самому поставить sphinx

а советовать значит руки доходят?
Наличие большого словаря не делает систему умной искаропки.

 

[alekciy]

Мне алгоритм поиска через триграммы показался интересным: http://habrahabr.ru/blogs/postgresql/78566/

 

[A1x]

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

 

[weregod]

в юности старший товарищ давал почитать "распознование текста с ошибками" или как-то так, в общем, существует литература, возможно, и в цифре-интернетах