Поиск на сайте, с учётом разных вариантов написания слова (как у Google)?

Question

[Pesetsu]

Здравствуйте, коллеги и заглянувшие.
Есть некая таблица, в ней есть столбец, назовём его title. Есть строка, в которой title = Хирошима, и альтернативный вариант написания Hiroshima (ромадзи). Есть пользователь N, он ищет слово "Херасима", и подразумевает найти "Хирошима", но естественно не находит. Кроме того можно написать "Хиросима, херасима, хирошимо, или даже херашима". Подобных записей может быть сотни тысяч, прописывать все возможные варианты написания не вариант (во первых это займет много времени, во вторых, нужно знать как на слух воспримет тот или иной название пользователь, чтобы учесть все варианты).
Всё это происходит в первую очередь потому, что эти слова являются вольной транслитерацией на слух с азиатских языков. Преимущественно, с Японского. Есть и другие причины, но в данном контексте, это неважно.
Ищу алгоритм, который позволит исправлять слова на правильные, как это делает Google.

Answer 1

[Сергей Горностаев]

Стивен Скиена - Алгоритмы Руководство по разработке, глава 8, страница 300. Но лучше не изобретать велосипед и просто взять движок полнотекстового поиска с поддержкой нечёткого поиска.

Comments

[NubasLol]

spasibo

Answer 2

[skrimafonolog]

"Так как в Google сделать самому" - забудьте сразу.
Одна из богатейших фирм мира, где поиск является основной частью бизнеса, следовательно, над реализацией поиска работают лучшие умы в этой области - вам с ними не соревноваться.

1) Можно подключить поиск Google к своему сайту.

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

Как составляются правила
Конференция Highload. Почему оно не находится!

Как пример, см. реализацию алгоритма soundex.

Answer 3

[Артур]

Sphinx, ElasticSearch и подобные

Comments

[skrimafonolog]

Sphinx, ElasticSearch и подобные

Это т.н. полнотекстовый поиск.
Когда находит слово внутри большого текста - причем не важно в начале, конце или середине.

А у автора вопрос про формы одного слова:

Есть некая таблица, в ней есть столбец, назовём его title. Есть строка, в которой title = Хирошима, и альтернативный вариант написания Hiroshima (ромадзи). Есть пользователь N, он ищет слово "Херасима", и подразумевает найти "Хирошима", но естественно не находит. Кроме того можно написать "Хиросима, херасима, хирошимо, или даже херашима".

Это совсем о другом.
Ни Sphinx ни Elastic не будут давать этого.