Пользователь
0,0
рейтинг
9 июля 2008 в 08:50

Разработка → Фонетический поиск

PHP*
Пару лет назад была задача написать для одного из сайтов такой поиск, который бы распознавал опечатки и предлагал бы исправленные запросы. Было перепробовано несколько вариантов, об одном из которых я и хотел тут написать. Поиск на основе звучания слов может стирать языковые границы, поскольку имена собственные на разных языках созвучны. Например, ищешь «Арнольд Шварцнеггер» на русском — находишь «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
provocateur @provocateur
карма
61,7
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (77)

  • +25
    Чувачок, ты объяснил так просто такую хрень )))
    • +3
      Бутыльски, осталось нам найти Водкина!
      • +1
        Рюмкин, аналогично и вам )))
        может сообразим на троих? ))
        • +9
          я тут!
          • +1
            вот и чудненько
            • 0
              Наливай ;)
          • 0
            Бухаем ;)
            • 0
              Можно с вами? :)
        • +1
          соображайте на троих. только уж на статью интересную соображайте!
  • +3
    отлично!
    замечательная статья, все бы такие были.

    заинтересовало очень.
  • +2
    Правда интересно и доходчиво написано!
  • 0
    Да, саундекс отличная штука. Позволяет не геморроиться со всякими там стеммерами и прочими морфологическими приблудами.

    Вообще мне вот интересно, как, допустим, яндекс режет приставки, падежи и т.д., наверняка же где-то есть и эти алгоритмы. Стеммер Портера не предлагать :)
    • +3
      Это называется "поиск с учетом морфологии". Есть несколько таких готовых движков, сам яндекс свой раздает. А можно написать и что-то подобное самому.
      • 0
        Про яндекс то я в курсе, просто это некая программулина, а не набор скриптов, соответственно на шаред хостинге не факт, что заработает как надо. А вот за вторую ссылку спасибо, почитаю.
        • 0
          Если я не ошибаюсь, то на яндексе есть и сорс всего этого, и порты под разные системы. Тем более, сделать обработчик готовой проги не так сложно. Она ж там на си написана.

          Еще раз повторюсь: не уверен в том, что только что написал, надо скачать и смотреть. Просто с годик назад качал и запускал на хостинге спокойно
          • 0
            Нет там сырцов, вы что :) Порты, да, есть.
    • 0
      посмотрите на сфинкс.
      он "из коробки" умеет морфологию русского и английского, мы достаточно просто добавили и украинский.
      • 0
        Он не подойдет для shared-хостинга.
        Кстати, а в сфинксе есть поиск по фразе (типа как если в "ковычки" слова в гугле взять) ?
        • 0
          да, вы правы, для виртуального проще использовать работу со словарями прямо в mysql, примерно как это описано у вас во второй ссылке. так тоже работали ) пока не понадобился украинский. с ним больше проблем из-за морфологического изменения корня слова в существительных.

          поиск по фразе есть, насколько помню, но лучше посмотреть документацию, как именно это делается.
          • 0
            Поясню, что спросил об этом не случайно. Этот вопрос для меня действительно сейчас актуален. Вот в том поиске, который с версии 8.3 вшит в Postgres, нету поиска фраз. Я уже посмотрел в мануале, есть в нем фразовый поиск, да. Это гуд.
        • 0
          Шаред конечно не требование, но большинство клиентов вряд ли разорятся на хотя бы VPS/VDS.
    • НЛО прилетело и опубликовало эту надпись здесь
  • 0
    Респект, отличная статья.
  • 0
    Реально, полезная вещь... А ведь можно этот поиск как-то и семантическим сделать
  • 0
    хеширование слов %\
  • +1
    Какой позитив с утра =)
    Спасибо за статью.
  • –2
     Респект. Былаб возможность - добавил бы плюсов.
  • НЛО прилетело и опубликовало эту надпись здесь
  • +2
    Вторая хорошая статья на хабре за последние сутки.
    Спасибо огромное.
    Вот теперь думаю, как бы это реализовать в MySQL.
    • +1
      Ну, самый простой и прямой вариант перевесить на мускул - считать коды на пхп, а в мускул пихать fulltext-индекс, затем искать binary fulltext в виде match (fulltext_key) against ('+845747 +773644' in boolean mode)
      а если совсем хочется глубоко закопаться - можно на процедурах сделать
      • 0
        Не. Я придумал иначе. Сделаю отдельную таблицу, в которой будет айдишник итема и коды названия (ну типа один итем ко многим кодам).
        И генерить коды при добавлении нового итема.
  • +4
    Ясность изложения говорит о большом понимании автором.
    А то вечно напишут что-то запутанное, а потом делают вид, что шарят :)
    Побольше бы таких замечательных статей!
  • +1
    Раз уж статья опубликована в разделе PHP, то, думаю, едва ли можно обидеть вниманием такую замечательную встроенную PHP-функцию, как metaphone() - собственно, реализация уже упомянутого алгоритма Metaphone. Есть еще такая реализация, как double metaphone (можно взять на http://swoodbridge.com/DoubleMetaPhone/). Она хоть и точнее, но работает, правда, помедленнее. Сама же функция metaphone - весьма шустрая, предназначена, к сожалению, только для латиницы, так что, без транслита все же не обойтись :(
    • 0
      С релизом шестерки, проблемы с латинецей и metaphone исчезнут слава богу )
  • 0
    Отличное решение сложной проблемы!
  • +1
    спасибо большое за интересную и простую подачу такого, казалось бы, туманного алгоритма.
    кто набрался смелости посчитать циферки для чака норриса — отпишитесь. страшно запускать.
  • 0
    полезная и хорошо написанная статья! спасибо!
  • 0
    Пять баллов.
  • 0
    Отлично написано, и все понятно. Автору плюсеги и спасибо :)
  • 0
    Попробую поставить к себе в поиск на аукцион фолбэкомм. У меня около 20% запросов с ошибками и еще 10% необходимо транслитирировать.
  • 0
    респектище! вот только возник вопрос, а что с умляутами? там в таблице только пару букв с закорючками. я так понимаю, должна быть где-то табличка замены всех этих буковок с точками/черточками на стандартную латиницу?
  • +1
    С нокией незадача.

    нокия: 654000
    nokia: 650000

    Может надо еще эти ия иа учитывать?
    • 0
      Да, есть некоторые исключения, но это легко подогнать под задачу - чуть усовершенствовать функцию транслитерации, чтобы двойной звук "й" после гласной не кодировать - из звучащего в транслите nokija/нокийа должно получится nokia/нокиа. Оставляю тюнинг на усмотрение тех, кто захочет попробовать этот поиск. )
      • 0
        Меня больше удивило:
        Bill: 780000
        Paul: 780000
        Тут я даже не знаю в какую сторону тюнить:)
    • +1
      Для Perl есть готовый модуль Text::Phonetic::DaitchMokotoff
      Так вот там, результат не код, а массив кодов (потому что "Some strings in the Daitch-Mokotoff algorithm produce ambigous results"). Для транслитерированного "нокия" результат - 2 кода: 654000 и 650000.
      • 0
        Да, можно выдавать оба возможных варианта - если кому-то захочется, можно приписать пару строк. Мне проще работать с теми языками, на которых я умею говорить, поэтому сделал, как сделал.
        • +1
          Ну, честно говоря непонятно, почему вы при транслитерации меняете Й на J, а далее как русский аналог J у вас выступает DZH. Правильнее тогда-бы пожалуй было транслитерировать Й в другую букву (последовательность букв).
          • 0
            Так я о том и написал четырьмя коментами выше. Почему - потому что мне на тот момент было выгоднее, чтобы Johnson == Джонсон, а не Johnson == Йонсон. Т.е. надо или тюнить транслит, или сами коды, или выдавать несколько возможных вариантов (последнее - правильный подход, но учитывая, что такой поиск используется, как фолбэк, когда нет точных совпадений, все в меру разумно... и Bill/Paul по той же причине я не рассматривал, потому что по таким вещам обычно не опечатываются и редко ищут - короткий запрос. А вот по MacCartnie, McCartney, Маккартни, Мокартни - самое то )). Спасибо за коменты, радует то, что многим все-таки не лень разобраться в теме.
            • 0
              В самой таблице (не в коде, а в html-таблице) я все же оставил оба возможных варианта для референса...
            • 0
              Johnson = Джонсон - вопросов нет:) Если вариант с несколькими кодами не прокатывает, то тюнить надо функцию транслит. Я у себя кроме й->j еще кое какие варианты затюнил.
              По поводу Bill/Paul это еще что, я вот на повеселее вариант наткнулся.
              Есть такая актриса Zawieruszanka (479465). Так вот Schwarzenegger (479465) ее фонетический родственник:)
  • 0
    Очень нравятся статьи написаны в доходчивой форме как эта )
    Спасиба!
  • 0
    Спасибо большое за ликбез!
  • 0
    преподнесено в меру вульгарно и весьма доходчиво, читалось легко. Спасибо )
  • НЛО прилетело и опубликовало эту надпись здесь
    • 0
      вряд ли он поможет при этом...
      посмотри в сторону phpmorphy
    • 0
      По правилам такие слова кодируются, как если бы они были без пробела, но потребуется внести дополнительные изменения, чтобы получить ожидаемый результат для Вашего конкретного случая использования.
  • 0
    А я когда-то читал про русский Soundex здесь http://community.livejournal.com/ru_php/…
  • 0
    Блин =)
    Привинтил к поиску на сайте. Решил поискать.
    Набрал, естественно, слово «хуй». Вылетел эксэпшон.
    Методом научного тыка установил, что функция работает, если строка содержит пять или больше символов.
    Сейчас попробую разобраться, почему так.
    • 0
      От четырех символов, если быть точным. Большинство слов до 4 символов не нуждаются в поддержке со стороны такого поиска, потому что либо достаточно коротки, чтобы быть написанными без опечаток, либо попадают в разряд "stopwords" (артикли, предлоги, местоимения и всякие другие короткие слова). В принципе, все это можно тюнинговать, там в коде эти ограничения видны. Ваше, в частности, надо поменять в preg_replace
      • 0
        а я уже сам догадался
        к тому же все короткие слова очень похожи ) поэтому ищешь «хуй», а находишь «мел»
        Ну это грубо говоря.
        А вообще ещё раз спасибо. Весь день сижу и играюсь: ищу всякое )
    • 0
      Неприлично же) Хоть бы звёздочку поставили =)
  • 0
    Это прям нереально крутая штуковина, господа!
    Будем думать и внедрять)
  • 0
    Вы меня, конечно, извините. Но я не понял как вы осуществили поиск? Не добавили же дополнительные поля в DB, где весь текст был в кодах, и по нему осуществлялся бы поиск.
    • 0
      ну, если это поиск по базе людей, то не проблема к колонкам имя и фамилия добавить еще 2 с кодами
  • НЛО прилетело и опубликовало эту надпись здесь
  • 0
    Очень интересно, только исходник функций пропал куда-то.
    • 0
      Поправил, перезалил исходник.
      • 0
        Спасибо.
  • 0
    Сэр, благодарю за интересный пост!
  • 0
    Спасибо!
    Интересненькое дело!
    Будет необходимость - поиграюсь!
    Пока что, просто на заметку!
    Спасибо! )
  • 0
    А у меня опять всё не слава богу. Одни нули теперь показывает.
    • 0
      Верните старый код :) Этот не работает. А то я с работы скачал - всё пахало, уже на апач грешить стал. Ан нет.
      • 0
        Вернул, плохо скопипастил, пардон.
  • 0
    описание==общение
    :(
    • 0
      заказ==секс
      световой==свадьба
      хостинг==гостиница
      музыка==месяц
      видео==фото :))
  • 0
    Никогда бы не догадался, респект :) Но, судя по комментом, много косяков? :) Интересно, как на Yandex и др. сервисах пашет фича "Возможно вы имели ввиду".
  • 0
    Насчет косяков - я там выше написал, что это фолбэк-онли. И применяется в основном к именам собственным.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.