Pull to refresh

Фонетический поиск

Reading time 4 min
Views 16K
Пару лет назад была задача написать для одного из сайтов такой поиск, который бы распознавал опечатки и предлагал бы исправленные запросы. Было перепробовано несколько вариантов, об одном из которых я и хотел тут написать. Поиск на основе звучания слов может стирать языковые границы, поскольку имена собственные на разных языках созвучны. Например, ищешь «Арнольд Шварцнеггер» на русском — находишь «Arnold Schwarzenegger» на английском, или ищешь «Michael Jordan» — находишь «Майкл Джордан», или ищешь «Чак Норрис» — и вдруг он сам тебя находит. Помимо поиска созвучных слов этот метод нивелирует большое количество опечаток. А то че-то задолбала попса, надо больше про инсайд…



Чтобы четко понимать принципы работы этого поиска, необходимо иметь представление о soundex. Скажу сразу, что предлагаемое ниже решение построено НЕ на основе soundex, а использует русифицированную и доработанную мной таблицу Daitch-Mokotoff, чтобы было интереснее. Soundex — штука древняя и хорошо известная. Читатель может пропустить следующий параграф, если уже знаком с этим алгоритмом. Далее небольшое введение для тех, кто не знаком, чтобы потом понимать о чем речь ваще…

Intro / Soundex


Soundex юзают национальные архивы США, хранящие генеалогическую информацию о гражданах. В качестве одного из требований чувачкам предъявили: алгоритм должен находить искомое в разных вариантах написания, поскольку многие имена собственные на слух записываются неоднозначно (например, Smith / Smyth). Гражданин Рассел почесал свой американский затылок и выкатил такое:
  1. Каждое слово представляется кодом из 4 символов.
  2. Первый символ четырехзначного кода — это первая буква кодируемого слова.
  3. Каждая следующая буква слова заменяется цифрой в соответствии с таблицей кодировки.
  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, но с дополнениями:

  1. Слова кодируются 6 цифрами, где каждая цифра обозначает один из звуков из левого столбца таблицы.
  2. Когда в слове мало букв, код дополняется до 6 символов нулями. Если букв слишком много — обрезается до 6 символов. В слове GOLDEN кодируется только четыре звука [G-L-D-N] и получается 583600.
  3. Буквы A, E, I, O, U, J, и Y всегда заменяются цифрой, будучи первыми в слове, как, например, в имени Alpert 087930. В остальных случаях эти буквы пропускаются и ничем не заменяются, только если две таких буквы подряд формируют пару и сразу за парой идет еще одна гласная. Например, в имени Breuer 'eu' кодируется 791900, но не в имени Freud.
  4. Буква H заменяется цифрой, если она первая, как в Haber 579000, или если сразу за ней идет гласная, как в Manheim 665600, в остальных случаях ее пропускают.
  5. Когда соседние буквы формируют более длинную последовательность, представленную в таблице, надо кодировать наиболее длинный подходящий вариант. Mintz кодируется как MIN-TZ 664000, но не MIN-T-Z.
  6. Когда соседствующие буквы образуют два одинаковых кода подряд, они записываются, как один, например, TOPF превращается в TO-PF 370000, но не в TO-P-F 377000. Исключением в этом пункте является комбинации MN и NM, которые в любом случае кодируются отдельно и не поддаются слиянию, как в Kleinman 586660, а не 586600.
  7. Последовательности 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

// ... про Чака Норриса - проверите сами.

Сразу скажу, в некоторых особо запущенных случаях такой поиск может ошибаться, но поддается тюнингу под большинство языков и под конкретное использование. Прибегать к нему надо тогда, когда нет точных совпадений — как фолбэк. Представленный вариант разработан так, чтобы наилучшим образом поддерживать русско-английский транскодинг. Юзать такое можно:
  • в поиске по именам и фамилиям людей в социальных сетях
  • в геопоиске по названиям городов, мест, объектов
  • в поиске по актеру/автору/исполнителю в магазинах контента/на инфосайтах
  • в общем поиске по названиям и именам собственным
  • в любых других случаях, когда пишется не так, как читается...
PR: люблю Picamatic
Tags:
Hubs:
+121
Comments 77
Comments Comments 77

Articles