Пару лет назад была задача написать для одного из сайтов такой поиск, который бы распознавал опечатки и предлагал бы исправленные запросы. Было перепробовано несколько вариантов, об одном из которых я и хотел тут написать. Поиск на основе звучания слов может стирать языковые границы, поскольку имена собственные на разных языках созвучны. Например, ищешь «Арнольд Шварцнеггер» на русском — находишь «Arnold Schwarzenegger» на английском, или ищешь «Michael Jordan» — находишь «Майкл Джордан», или ищешь «Чак Норрис» — и вдруг он сам тебя находит. Помимо поиска созвучных слов этот метод нивелирует большое количество опечаток. А то че-то задолбала попса, надо больше про инсайд…
Чтобы четко понимать принципы работы этого поиска, необходимо иметь представление о soundex. Скажу сразу, что предлагаемое ниже решение построено НЕ на основе soundex, а использует русифицированную и доработанную мной таблицу Daitch-Mokotoff, чтобы было интереснее. Soundex — штука древняя и хорошо известная. Читатель может пропустить следующий параграф, если уже знаком с этим алгоритмом. Далее небольшое введение для тех, кто не знаком, чтобы потом понимать о чем речь ваще…
Soundex юзают национальные архивы США, хранящие генеалогическую информацию о гражданах. В качестве одного из требований чувачкам предъявили: алгоритм должен находить искомое в разных вариантах написания, поскольку многие имена собственные на слух записываются неоднозначно (например, Smith / Smyth). Гражданин Рассел почесал свой американский затылок и выкатил такое:
Очевидно, что кодируются только согласные, т.к. именно они составляют фонетически опорную часть слова в английском языке. Двойные согласные кодируются, как одна. Получившийся код обрезается или дополняется нулями до 4 символов. Например, Washington кодируется, как W252 («W» первая, «a» выкидывается, «s» = 2, «h» выкидывается, «n» = 5, «g» = 2, оставшиеся символы выкидываются), Lee кодируется, как L000 («L» первая, «e» выкидывается дважды, 000 — дополнение до четырех символов). Первая буква слова всегда остается оригинальной, даже если это гласная, и даже если ее нет в таблице. Таким образом, зная soundex-код, американские бабульки могут быстренько откопать в картотеках всех Smith'ов, Smyth'ов и Smooth'ов. Читать подробнее про soundex. Все равно soundex шняга, и не катит, потому что Jones, James и Jeans кодирует одинаково.
Хрен знает, может для английской фонетики soundex'а достаточно, но правила soundex не подходят для остальных языков и слов, например, для нашего великого и могучего — в русском языке недостаточно кодировать только согласные. Чувачок Дэйч и налогоплательщик Мокотофф прикинули вечерком собственную таблицу, учитывающую особенности произношения, свойственные европейским языкам. Вот такая хрень:
Принцип кодирования тот же, что и в soundex, но с дополнениями:
Таблица рассчитана на языки на основе латиницы, поэтому, чтобы кодировать русский мат, надо юзать волшебный транслит.
Итого получилось две функции — dmword и dmstring, одна кодирует слово в daitch-mokotoff-код, другая разбивает строку на слова и кодирует каждое слово, затем склеивает все в строку daitch-mokotoff-кодов через пробел. Это подача для реализации, в данном случае, написано на php, но переписать можно под что угодно. Получившиеся коды суются в бд и дергаются, как обычно. Работает с UTF8.
Посмотреть обе функции в исходнике.
Сразу скажу, в некоторых особо запущенных случаях такой поиск может ошибаться, но поддается тюнингу под большинство языков и под конкретное использование. Прибегать к нему надо тогда, когда нет точных совпадений — как фолбэк. Представленный вариант разработан так, чтобы наилучшим образом поддерживать русско-английский транскодинг. Юзать такое можно:
Чтобы четко понимать принципы работы этого поиска, необходимо иметь представление о soundex. Скажу сразу, что предлагаемое ниже решение построено НЕ на основе soundex, а использует русифицированную и доработанную мной таблицу Daitch-Mokotoff, чтобы было интереснее. Soundex — штука древняя и хорошо известная. Читатель может пропустить следующий параграф, если уже знаком с этим алгоритмом. Далее небольшое введение для тех, кто не знаком, чтобы потом понимать о чем речь ваще…
Intro / Soundex
Soundex юзают национальные архивы США, хранящие генеалогическую информацию о гражданах. В качестве одного из требований чувачкам предъявили: алгоритм должен находить искомое в разных вариантах написания, поскольку многие имена собственные на слух записываются неоднозначно (например, Smith / Smyth). Гражданин Рассел почесал свой американский затылок и выкатил такое:
- Каждое слово представляется кодом из 4 символов.
- Первый символ четырехзначного кода — это первая буква кодируемого слова.
- Каждая следующая буква слова заменяется цифрой в соответствии с таблицей кодировки.
- Символы, которые не представлены в таблице, выкидываются нафиг и не кодируются.
Очевидно, что кодируются только согласные, т.к. именно они составляют фонетически опорную часть слова в английском языке. Двойные согласные кодируются, как одна. Получившийся код обрезается или дополняется нулями до 4 символов. Например, Washington кодируется, как W252 («W» первая, «a» выкидывается, «s» = 2, «h» выкидывается, «n» = 5, «g» = 2, оставшиеся символы выкидываются), Lee кодируется, как L000 («L» первая, «e» выкидывается дважды, 000 — дополнение до четырех символов). Первая буква слова всегда остается оригинальной, даже если это гласная, и даже если ее нет в таблице. Таким образом, зная soundex-код, американские бабульки могут быстренько откопать в картотеках всех Smith'ов, Smyth'ов и Smooth'ов. Читать подробнее про soundex. Все равно soundex шняга, и не катит, потому что Jones, James и Jeans кодирует одинаково.
Daitch-Mokotoff
Хрен знает, может для английской фонетики soundex'а достаточно, но правила soundex не подходят для остальных языков и слов, например, для нашего великого и могучего — в русском языке недостаточно кодировать только согласные. Чувачок Дэйч и налогоплательщик Мокотофф прикинули вечерком собственную таблицу, учитывающую особенности произношения, свойственные европейским языкам. Вот такая хрень:
Принцип кодирования тот же, что и в soundex, но с дополнениями:
- Слова кодируются 6 цифрами, где каждая цифра обозначает один из звуков из левого столбца таблицы.
- Когда в слове мало букв, код дополняется до 6 символов нулями. Если букв слишком много — обрезается до 6 символов. В слове GOLDEN кодируется только четыре звука [G-L-D-N] и получается 583600.
- Буквы A, E, I, O, U, J, и Y всегда заменяются цифрой, будучи первыми в слове, как, например, в имени Alpert 087930. В остальных случаях эти буквы пропускаются и ничем не заменяются, только если две таких буквы подряд формируют пару и сразу за парой идет еще одна гласная. Например, в имени Breuer 'eu' кодируется 791900, но не в имени Freud.
- Буква H заменяется цифрой, если она первая, как в Haber 579000, или если сразу за ней идет гласная, как в Manheim 665600, в остальных случаях ее пропускают.
- Когда соседние буквы формируют более длинную последовательность, представленную в таблице, надо кодировать наиболее длинный подходящий вариант. Mintz кодируется как MIN-TZ 664000, но не MIN-T-Z.
- Когда соседствующие буквы образуют два одинаковых кода подряд, они записываются, как один, например, TOPF превращается в TO-PF 370000, но не в TO-P-F 377000. Исключением в этом пункте является комбинации MN и NM, которые в любом случае кодируются отдельно и не поддаются слиянию, как в Kleinman 586660, а не 586600.
- Последовательности CH, CK, C, J, и RS могут по-разному звучать в некоторых языках — для них предложены два варианта (в таблице русский вариант выде��ен красным).
Таблица рассчитана на языки на основе латиницы, поэтому, чтобы кодировать русский мат, надо юзать волшебный транслит.
Outro
Итого получилось две функции — dmword и dmstring, одна кодирует слово в daitch-mokotoff-код, другая разбивает строку на слова и кодирует каждое слово, затем склеивает все в строку daitch-mokotoff-кодов через пробел. Это подача для реализации, в данном случае, написано на php, но переписать можно под что угодно. Получившиеся коды суются в бд и дергаются, как обычно. Работает с UTF8.
Посмотреть обе функции в исходнике.
dmstring('Майкл Джордан') == dmstring('Michael Jordan') == 658000 493600
dmstring('Арнольд Шварцнеггер') == dmstring('Arnold Schwarzenegger') == 096830 479465
dmstring('Орнольд Шворцнегир') == dmstring('Arnold Schwarzenegger') == 096830 479465
// ... про Чака Норриса - проверите сами.
Сразу скажу, в некоторых особо запущенных случаях такой поиск может ошибаться, но поддается тюнингу под большинство языков и под конкретное использование. Прибегать к нему надо тогда, когда нет точных совпадений — как фолбэк. Представленный вариант разработан так, чтобы наилучшим образом поддерживать русско-английский транскодинг. Юзать такое можно:
- в поиске по именам и фамилиям людей в социальных сетях
- в геопоиске по названиям городов, мест, объектов
- в поиске по актеру/автору/исполнителю в магазинах контента/на инфосайтах
- в общем поиске по названиям и именам собственным
- в любых других случаях, когда пишется не так, как читается...
