Транслитерация

Как много в вашем городе иностранных туристов? В моём мало, но встречаются, как правило стоят потерянные посреди улицы и повторяют одно единственное слово название чего бы то ни было. А прохожие пытаются им на пальцах объяснить куда пройти, а когда моя твоя не понимать берут за руку и ведут к пункту назначения. Как это не удивительно, обычно цель в пяти минутах ходьбы, т.е. какое-то примерное представление о городе эти туристы всё же имели. Может по бумажной карте ориентировались.

А как часто лично вы оказывались в такой ситуации, в незнакомом городе в другой стране?

Появление смартфонов и приложений для навигации решило много проблем. Ура, можно посмотреть свою геолокацию, можно найти куда идти, прикинуть в каком направлении и даже проложить маршрут.

Осталась одна проблема: все улицы в приложении подписаны местными иероглифами на местном наречии, и ладно если в стране пребывания принята латиница, клавиатура на латинице есть во всех смартфонах и мир к ней привык, и то я испытывал дискомфорт, из-за диакритических знаков, принятых в чешском алфавите. А боль и страдания иностранцев, видящих кириллицу, могу только представить, посмотрите псевдокириллицу и поймёте. Если бы я оказался на их месте, я бы писал названия и адреса латиницей, пытаясь воспроизвести звучание - фонетический поиск.

В публикации опишу как реализовать фонетические алгоритмы поиска Soudex на движке Sphinx Search. Одной транслитерацией здесь не обойдётся, хотя и без неё никуда. Получившийся конфигурационный файл, доступен на GitHub Gist.

Вступление

Понадобится база адресов, например, ФИАС или база названий чего-то, в общем то, что будем искать, и Sphinx Search.

Решение удобно тем, что ничего не придётся доделывать, достраивать дорабатывать в самой базе, т.е. данные останутся как есть, - всё сделает Sphinx.

Если мы решили, что, пользователи будут искать названия так, как они их на слух воспринимают, то наша беда в том, что слух у всех разный. Мы можем придумывать сколько угодно различных стандартов транслитераций, и они нам все в одинаковой степени и подходят, и нет.

Но, ничто не ново под луной и решение уже найдено до нас. Распространены два подхода Soundex и Metaphone, плюс их вариации. В публикации рассмотрим только Soundex и его варианты, Metaphone затрагивать не будем.

Более того, Sphinx уже поддерживает Soundex, как говорится, из коробки. Но рано бить баклуши, почивать на лаврах и стричь купоны, для кириллицы он не работает. Т.е. по сути не подходит для задачи. Придётся допиливать.

Для начала неплохо разобраться с тем что из себя представляют фонетические алгоритмы. На хабре есть статьи, лично мне нравятся: фонетический поиск краткая и лаконичная, подойдёт для тех кто хочет в двух словах понять идею не вдаваясь в детали реализации, и вторая фонетические алгоритмы, наоборот, для тех кому нужно подробнее. Я буду опираться на материал, написанный в них, стараясь как можно меньше его дублировать дабы не раздувать статью, для полноты картины, советую ознакомиться с ними, прежде чем продолжать.

А теперь подумаем, как завезти поддержку кириллицы в Soundex, реализовать и его, и улучшенную версию, и NYSIIS, и Daitch-Mokotoff.

К реализации

Будут приведены некоторые примеры работы на SphinxQL, для этого использую подключение в духе:

mysql -h 127.0.0.1 -P 9306 --default-character-set=utf8

но публикация про реализацию фонетических алгоритмов на Sphinx, а не про работу с ним, если вам нужно введение в Sphinx Search, то советую посмотреть блог Чакрыгина, к сожалению уже заброшенный, но для старта более чем достаточно. Там и про создание подключения есть.

Оригинальный Soundex и Транслитерация

Начнём с самого простого в реализации. Простоты добавляет тот факт, что Sphinx Search, как я уже писал выше, поддерживает из коробки реализацию для английского языка, т.е. половина дела уже в шляпе.

Кстати, делает это он не совсем канонично: не обрезает все коды до четырёх символов, а если символов меньше четырёх не дополняет всё нулями. Но я в этом ни каких проблем не вижу.

Всё что от нас требуется сделать транслитерацию на великий и могучий, остальное Sphinx сделает сам.

Сделать транслитерацию несложно, сложно выбрать правила, по которым она будет проходить, стандартов уйма, и скорее всего это ещё не всё, ознакомиться с ними можно в Википедии: транслитерация русского алфавита латиницей. Выбор чистая вкусовщина, если вам не навязывается стандарт каким-нибудь приказом МВД, то берите тот который больше нравится или скомбинируйте их в свой ни на что не похожий, в конце концов задача всех этих фонетических алгоритмов избавить нас от этих разночтений. Можно ещё посмотреть публикацию "всё о транслитерации", вдруг поможет определиться с выбором. Как ни выбирай, всё равно найдётся ситуация, когда все эти ухищрения не помогут, да и лошадиную фамилию всё равно не найдёт.

Прописываем в конфигурации Sphinx все правила транслита с помощью регулярных выражений:

regexp_filter = (А|а) => a

а для Ъ и Ь можно написать

regexp_filter = (Ь|ь) =>

Не буду приводить текст для всего алфавита, если что можно скопировать всё там же, с GitHub Gist.

И не забудьте включить soundex для латиницы:

morphology = soundex

Теперь, когда мы будем искать текст на кириллице он будет сначала транслитерироваться с помощью регулярных выражений, а полученная латиница будет обрабатываться Sphinx в соответствии с правилами оригинального Soundex.

Всё настроили, проиндексировали данные, создали подключение к Sphinx. Давайте попробуем найти что-нибудь. Раз уж наша цель - коммунизм интернационализм поисковой выдачи, то и искать будем улицы названные в честь деятелей интернационала, и сочувствующих. Поищем Ленина. Искать будем именно Ленина, а не Ленин, я почему-то уверен, что интуристы прямо так и будут искать Lenina, может даже ulitsa Lenina.

Чтобы понять что с ним происходит воспользуемся командой CALL KEYWORDS:

mysql> call keywords('Ленин Ленина Lenina Lennina Lenin', 'STREETS', 0);+------+-----------+------------+| qpos | tokenized | normalized |+------+-----------+------------+| 1    | lenin     | l500       || 2    | lenina    | l500       || 3    | lenina    | l500       || 4    | lennina   | l500       || 5    | lenin     | l500       |+------+-----------+------------+

Обратите внимание, в tokenized хранится то, что было получено после применения всех регулярных выражений. А в normalized, то по какому ключу Sphinx будет осуществлять поиск, и результат обусловлен тем, что включена morphology. 'Lenina' преобразуется в ключевое слово l500, и 'Ленина' в l500, спасибо транслиту, - уровнял, теперь на каком бы языке не искали найдётся одно и то же. Всё тоже самое и для Lennina, и для Lenena, и даже Lennona. Так что, если в вашем городе есть улица Джона Леннона, то тут может накладочка выйти.

Выполним поиск, наконец:

mysql> select * from STREETS where match('Lenena'); +------+--------------------------------------+-----------+--------------+| id   | aoguid                               | shortname | offname      |+------+--------------------------------------+-----------+--------------+|  387 | 4b919f60-7f5d-4b9e-99af-a7a02d344767 | ул        | Ленина       |+------+--------------------------------------+-----------+--------------+

Sphinx вернул нам один результат, даже если ввели с ошибкой. Вот с Плехановым посложнее. Тут уже в зависимости от того, какой мы способ транслитерации выберем:

mysql> call keywords('Плехановская Plechanovskaya Plehanovskaja Plekhanovska', 'STREETS', 0);+------+----------------+------------+| qpos | tokenized      | normalized |+------+----------------+------------+| 1    | plekhanovskaja | p42512     || 2    | plechanovskaya | p42512     || 3    | plehanovskaja  | p4512      || 4    | plekhanovska   | p42512     |+------+----------------+------------+

plehanovskaja -выбивается. Sphinx ничего не вернёт. Но, можно воспользоваться CALL QSUGGEST:

mysql> CALL QSUGGEST('Plehanovskaja', 'STREETS');+----------------+----------+------+| suggest        | distance | docs |+----------------+----------+------+| plekhanovskaja | 1        | 1    || petrovskaja    | 4        | 1    |+----------------+----------+------+

Функция вернёт предложения по исправлению запроса, и расстояние Левенштейна между запросом, и возможным результатом. Т.е. можно попробовать опять взять напильник в руки.

Не забудьте включить инфикс, для работы этой функции:

min_infix_len = 2

suggest содержит запись аналогичную по смыслу колонке tokenized, т.е. то, что получилось после применения регулярных выражений. В этом случае регулярные выражения касались только транслитерации, в других реализациях Soudex регулярные выражения будут применяться в том числе и для генерации кода, поэтому QSUGGEST работать не будет.

Попробуем что-нибудь ещё найти:

mysql> select * from STREETS where match('30 let Pobedy');+------+--------------------------------------+-----------+------------------------+| id   | aoguid                               | shortname | offname                |+------+--------------------------------------+-----------+------------------------+|  677 | 87234d80-4098-40c0-adb2-fc83ef237a5f | ул        | 30 лет Победы          |+------+--------------------------------------+-----------+------------------------+mysql> select * from STREETS where match('30 лет Побуды');+------+--------------------------------------+-----------+------------------------+| id   | aoguid                               | shortname | offname                |+------+--------------------------------------+-----------+------------------------+|  677 | 87234d80-4098-40c0-adb2-fc83ef237a5f | ул        | 30 лет Победы          |+------+--------------------------------------+-----------+------------------------+

Хорошо справляется, заодно и опечатки может исправить.

Спойлер: именно этот вариант в итоге и окажется самым приемлемым. Если лень читать полотенце ниже, то сразу переходите к итогам, всё равно вывод в пользу оригинального Soundex.

Улучшенный Soundex

Попробуем реализовать улучшенную версию. Улучшенность в том, что больше групп для кодирования символов, значит больше вариантов кодирования, значит меньше ложноположительных срабатываний.

Вначале копируем транслитерацию.

Sphinx поддерживает наследование для index, но вынести транслитерацию в родительский индекс, а потом унаследовать её в дочерних, не получится. При наследовании индексов, Sphinx полностью игнорирует регулярные выражения родителя, они считаются переопределёнными если вы добавляете в дочерний класс новые регулярные выражения. Т.е. наследовать можно, пока в дочернем не объявить regexp_filter, который переопределит все regexp_filter родителя.

Можно убрать morphology = soundex из конфигурации она нам уже ничем не поможет, только под ногами путается. Придётся всё прописывать самим, опять через регулярные выражения.

Sphinx будет их применять последовательно, в том порядке, в котором они в конфигурации прописаны! Это важно. Для регулярных выражений используется движок RE2.

Сразу после блока с транслитерацией запишем сохранение первого символа, например: regexp_filter = \A(A|a) => a

Затем остальные символы заменяются на числовой код, Гласные на 0.

regexp_filter = \B(A|a) => 0regexp_filter = \B(Y|y) => 0...

Хотя, гласные можно просто удалять regexp_filter = \B(Y|y) =>

Решайте сами какой вариант нравится больше, хозяин - барин. Но я гласные выкидываю, хотя бы для того чтобы ВЛКСМ и Veelkaseem давали один результат.

mysql> call keywords('ВЛКСМ Veelkaseem', 'STREETS', 0);+------+-----------+------------+| qpos | tokenized | normalized |+------+-----------+------------+| 1    | v738      | v738       || 2    | v738      | v738       |+------+-----------+------------+

иначе будет что-то такое:

mysql> call keywords('ВЛКСМ Veelkaseem', 'STREETS', 0);+------+-----------+------------+| qpos | tokenized | normalized |+------+-----------+------------+| 1    | v738      | v738       || 2    | v0730308  | v0730308   |+------+-----------+------------+

Далее, согласные H и W просто выкидываются.

Идущие подряд символы, или входящие в одну и ту же группу, или символы/группы, разделенные буквами H или W, записываются как один. Это самое последнее действие.

regexp_filter = 0+ => 0regexp_filter = 1+ => 1...

Проверяем что получается:

mysql> call keywords('Ленин Ленина Lenina Lennina Lenin', 'STREETS', 0);+------+-----------+------------+| qpos | tokenized | normalized |+------+-----------+------------+| 1    | l8        | l8         || 2    | l8        | l8         || 3    | l8        | l8         || 4    | l8        | l8         || 5    | l8        | l8         |+------+-----------+------------+mysql> select * from STREETS where match('Lenina');+------+--------------------------------------+-----------+--------------+| id   | aoguid                               | shortname | offname      |+------+--------------------------------------+-----------+--------------+|  387 | 4b919f60-7f5d-4b9e-99af-a7a02d344767 | ул        | Ленина       |+------+--------------------------------------+-----------+--------------+

Вроде всё нормально, и Ленина мы находим во всех вариациях. Но обратите внимание, поле tokenized теперь содержит не индексируемый текс, а soundex-код. QSUGGEST отказывается работать. Если кто-то знает, как включить пишите. Я пытался добавить юникод для цифр в ngram_chars. Но это не помогло.

Проверим на Плеханове:

mysql> call keywords('Плехановская Plechanovskaya Plehanovskaja Plekhanovska', 'STREETS', 0);+------+-----------+------------+| qpos | tokenized | normalized |+------+-----------+------------+| 1    | p738234   | p738234    || 2    | p73823    | p73823     || 3    | p78234    | p78234     || 4    | p73823    | p73823     |+------+-----------+------------+

Стало вариантов много, а правильный всего один, и QSUGGEST не придёт на помощь:

mysql> CALL QSUGGEST('Plehanovskaja', 'STREETS');Empty set (0.00 sec)mysql> CALL QSUGGEST('p73823', 'STREETS');Empty set (0.00 sec)mysql> CALL QSUGGEST('p78234', 'STREETS');Empty set (0.00 sec)

Хотели, как лучше, а получилось, как всегда. Сам алгоритм реализовали, вроде правильно, но непрактично. Хотя нерабочим его тоже не назовёшь. Например, вот как он побеждает 30 лет Победы:

mysql> call keywords('30 let Podedy', 'STREETS', 0);+------+-----------+------------+| qpos | tokenized | normalized |+------+-----------+------------+| 1    | 30        | 30         || 2    | l6        | l6         || 3    | p6        | p6         |+------+-----------+------------+mysql> select * from STREETS where match('30 let Pobedy');+------+--------------------------------------+-----------+------------------------+| id   | aoguid                               | shortname | offname                |+------+--------------------------------------+-----------+------------------------+|  677 | 87234d80-4098-40c0-adb2-fc83ef237a5f | ул        | 30 лет Победы          |+------+--------------------------------------+-----------+------------------------+

И даже так работает:

mysql> select * from STREETS where match('Вэлкасэем');+------+--------------------------------------+--------------+----------------------+| id   | aoguid                               | shortname    | offname              |+------+--------------------------------------+--------------+----------------------+|  873 | abdb0221-bfe8-4cf8-9217-0ed40b2f6f10 | проезд       | 30 лет ВЛКСМ         || 1208 | f1127b16-8a8e-4520-b1eb-6932654abdcd | ул           | 50 лет ВЛКСМ         |+------+--------------------------------------+--------------+----------------------+

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

NYSIIS

Ходят слухи что разработан он был для работы с американскими фамилиями. Американские это вообще какая-то условность. Да и фамилии тоже, подойдёт и для поиска по названиям улиц и другим именам собственным, тем более в России многие улицы названы чьей-то фамилией, хотя американцами эти люди не стали.

Далее будет использоваться модификатор (?i) для работы регулярных выражений без учёта регистра.

Начинаем с транслитерации, как всегда. Затем:

1. Преобразовать начало слова

   regexp_filter = (?i)\b(mac) => mcc

2. Преобразовать конец слова

   regexp_filter = (?i)(ee)\b => y

3. После гласных: удалить H, преобразовать W в А

   regexp_filter = (?i)(a|e|i|o|u|y)h => \1

   regexp_filter = (?i)(a|e|i|o|u|y)w => \1a

4. Преобразовываем все буквы кроме первой

   regexp_filter = (?i)\B(e|i|o|u) => a

   regexp_filter = (?i)\B(q) => g

5. Удалить S на конце

   regexp_filter = (?i)s\b =>

6. Преобразуем AY на конце в Y

7. Удалить A на конце

Напоминаю что регулярные выражения приведены не все, а минимум, для примера!!!

Самое замечательное, - это то, что код не числовой, а буквенный, а значит снова заработает CALLQSUGGEST.

Проверяем:

mysql> call keywords('Ленин Ленина Lenina Lennina Lenin', 'STREETS', 0);+------+-----------+------------+| qpos | tokenized | normalized |+------+-----------+------------+| 1    | lanan     | lanan      || 2    | lanan     | lanan      || 3    | lanan     | lanan      || 4    | lannan    | lannan     || 5    | lanan     | lanan      |+------+-----------+------------+mysql> call keywords('Плехановская Plechanovskaya Plehanovskaja Plekhanovska', 'STREETS', 0);+------+---------------+---------------+| qpos | tokenized     | normalized    |+------+---------------+---------------+| 1    | plachanavscaj | plachanavscaj || 2    | plachanavscay | plachanavscay || 3    | plaanavscaj   | plaanavscaj   || 4    | plachanavsc   | plachanavsc   |+------+---------------+---------------+

Пробуем понять что имел в виду пользователь, используем для этого CALL QSUGGEST Plehanovskaja, преобразовавшуюся в plaanavscaj:

mysql> CALL QSUGGEST('plaanavscaj', 'STREETS');+---------------+----------+------+| suggest       | distance | docs |+---------------+----------+------+| paanarscaj    | 2        | 1    || plachanavscaj | 2        | 1    || latavscaj     | 3        | 1    || sladcavscaj   | 3        | 1    || pacravscaj    | 3        | 1    |+---------------+----------+------+

И тут возникают коллизии. Да ещё и без пол-литра не разберёшься что тут такое.

С таким подходом мы любой адрес из-под земли достанем, даже если пользователь искал не его и ему туда не надо. Зато шансов что-то НЕ найти не осталось. Берите, если на неправильный запрос нужно возвращать много разных вариантов исправления. Может пользователь туда и не хотел, но вдруг передумает, глядя на предложенные варианты.

Daitch-Mokotoff Soundex

И последний по списку, но не по значению, из алгоритмов Soundex.

Чувствителен к порядку преобразования. Например, если преобразование выполняется по принципу за гласной, то нам не нужно запоминать что гласную удалили ещё не предыдущем шаге, раз удалили, - значит там её уже нет, и правило не сработает и не должно, - так и задумано.

Как всегда, в начале транслитерация.

Потом выполняем пошаговую трансформацию.

Каждый шаг состоит из трёх условий, т.е. три разных регулярных выражения:

• если буквосочетание в начале слова

  regexp_filter = (?i)\b(au) => 0

• если за гласной

  regexp_filter = (?i)(a|e|i|o|u|y)(au) => \17

• и остальные случаи, здесь даже \B в регулярном выражении можно не писать, потому что другие варианты уже были ранее обработаны

  regexp_filter = (?i)au =>

Иногда нет никакой разницы между двумя или тремя разными ситуациями и одного-два регулярных выражения на шаг хватит:

regexp_filter = (?i)j => 1

Глянем что получается:

mysql> call keywords('Ленин Ленина Lenina Lennina Lenin', 'STREETS', 0);+------+-----------+------------+| qpos | tokenized | normalized |+------+-----------+------------+| 1    | 866       | 866        || 2    | 866       | 866        || 3    | 866       | 866        || 4    | 8666      | 8666       || 5    | 866       | 866        |+------+-----------+------------+mysql> call keywords('Плехановская Plechanovskaya Plehanovskaja Plekhanovska', 'STREETS', 0);+------+-----------+------------+| qpos | tokenized | normalized |+------+-----------+------------+| 1    | 7856745   | 7856745    || 2    | 7856745   | 7856745    || 3    | 786745    | 786745     || 4    | 7856745   | 7856745    |+------+-----------+------------+

Опять исключительно числовой код, и опять QSUGGEST не поможет понять пользователя. Со всякими непонятками всё ещё справляется неплохо.

mysql> select * from STREETS where match('Veelkaseem'); show meta;+------+--------------------------------------+--------------+----------------------+| id   | aoguid                               | shortname    | offname              |+------+--------------------------------------+--------------+----------------------+|  873 | abdb0221-bfe8-4cf8-9217-0ed40b2f6f10 | проезд       | 30 лет ВЛКСМ         || 1208 | f1127b16-8a8e-4520-b1eb-6932654abdcd | ул           | 50 лет ВЛКСМ         |+------+--------------------------------------+--------------+----------------------+2 rows in set (0.00 sec)+---------------+-------+| Variable_name | Value |+---------------+-------+| total         | 2     || total_found   | 2     || time          | 0.000 || keyword[0]    | 78546 || docs[0]       | 2     || hits[0]       | 2     |+---------------+-------+

Ну и всё на этом, никакого чуда не произошло, - мы уже это видели.

Итоги

Реализовать Soundex, в целом получилось, из всех вариантов предпочтительнее оригинальный Soundex и NYSIIS, по той простой причине что работаем мы напрямую с буквенным кодом и можно вызвать CALL QSUGGEST, а Sphinx предложит варианты исправления, при том в NYSIIS много и всяких-разных. Улучшенный Soundex и Daitch-Mokotoff Soundex, должны снизить количество коллизий, охотно верю, что так и происходит, но проиндексировав 1286 названий улиц своего города, я не заметил, чтобы коллизии были хоть какой-то проблемой. Хотя встречаются:

mysql> call keywords('Воровского Вербовая', 'STREETS', 0);+------+------------+------------+| qpos | tokenized  | normalized |+------+------------+------------+| 1    | vorovskogo | v612       || 2    | verbovaja  | v612       |+------+------------+------------+

Это был оригинальный Soundex, в улучшенном уже нормально:

mysql> call keywords('Воровского Вербовая', 'STREETS', 0);+------+-----------+------------+| qpos | tokenized | normalized |+------+-----------+------------+| 1    | v9234     | v9234      || 2    | v9124     | v9124      |+------+-----------+------------+

Зато алгоритмы стали менее терпимы к опечаткам, особенно если она допущена в согласной. Например, оригинальный Soundex:

mysql> select * from STREETS where match('Ордхоникидзе');+------+--------------------------------------+-----------+--------------------------+| id   | aoguid                               | shortname | offname                  |+------+--------------------------------------+-----------+--------------------------+|   12 | 0278d3ee-4e17-4347-b128-33f8f62c59e0 | ул        | Орджоникидзе             |+------+--------------------------------------+-----------+--------------------------+

А остальные реализации ничего не возвращают.

Невозможность вызова QSUGGEST, тоже кажется существенной проблемой. Хотя, может я просто не умею её готовить. Если знаете, как делитесь рецептом.

В общем, не мудрствуя лукаво, мой совет: используйте оригинальный Soundex с транслитерацией. Единственный риск - коллизии, чтобы их разрешить, просто-напросто возьмите оригинальный запрос, и подсчитайте расстояние Левенштейна между ним, и теми несколькими записями что вам предлагает Sphinx.

Если возможности проводить постобработку нет, ни для исправления, ни для разрешения коллизий, то выбирайте улучшенный Soundex или Daitch-Mokotof - хотя бы Вербовую, вместо Воровского не получите. NYSIIS подойдёт если вы хотите пользователю, на запрос с ошибкой, предложить, как можно больше самых непохожих друг на друга вариантов.

Всё написанное испытано на sphinx-3.3.1, но должно работать на всём с версии 2.1.1-beta, в которой появились регулярные выражения. В том числе на Manticore. Разработчики ManticoreSearch, хвастаются что прогресс идёт в гору семимильными шагами. Может там будет поддержка и прочих алгоритмов, хотя бы для латиницы, а может и сразу для кириллицы.

И по большому счёту этот подход приемлем для всего, к чему можно прикрутить транслит. Можно хоть китайскую грамоту индексировать, только транслитерацию знай прикручивай.

P.S.

Статья получилось неожиданно большой, сам не ожидал. Поэтому про Metaphone не написал. Для него будет, или не будет, отдельная статья. Хотя принцип тот же:

1. Транслит-регулярки

2. Ещё регулярки

3. ????

4. PROFIT

Это продолжение публикации Интернационализация поиска по городским адресам. Реализуем русскоязычный Soundex на Sphinx Search, в которой я разбирал, как реализовать поддержку фонетических алгоритмов Soundex в Sphinx Search, для текста написанного кириллицей. Для текста на латинице поддержка Soundex уже есть. С Metphone аналогично, для латиницы есть, для кириллицы не очень, но попытаемся исправить этот досадный факт с помощью транслитерации, регулярных выражений и напильника.

Это прямое продолжение, в котором разберём как реализовать оригинальный Metaphone, русскийMetaphone (в том смысле что транслитерация не понадобится), Caverphone, и не сможем сделать DoubleMetaphone.

Реализация подойдёт как для использования на платформе SphinxSearch, так и ManticoreSearch.

В конце, в качестве бонуса, посмотрим как Metaphone воспримет "ракомакофон".

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

Оригинальный Metaphone

Реализуется элементарно, создаются регулярные выражения для транслитерации:

regexp_filter = (А|а) => aregexp_filter = (Б|б) => bregexp_filter = (В|в) => v

И включаем metaphone:

morphology = metaphone

Всё, как и с оригинальным Soundex. В прошлый раз, мы пришли к выводу, что лучше всего, из всех Soundex алгоритмов, использовать именно оригинальный Soundex, единственный недостаток которого коллизии, разрешается вычислением расстояния Левенштейна.

В этот раз, забегая вперёд, скажу, что снова сделал бы свой выбор в пользу оригинального Metaphone + транслит. А вот причина небанальна.

Дело в том что у Sphinx есть в такой параметр blend_chars. Смысл следующий, Sphinx индексирует по словам, а слова он находит по разделителям, например, если между буквами есть пробел, значит буквы два разных слова, перенос строки, табуляция, знаки препинания и т.д., и т.п. Но могут быть символы, которые одновременно разделяют слова, а могут быть и частью одного слова, например, &. M&Ms это сколько слов? А Рога&Копыта? Для таких случаев и существует blend_chars.

И тут можно пойти на хитрость, и добавить в blend_chars пробел:

blend_chars = U+0020

Теперь, когда кто-то будет искать улицу Мориса Тореза, то найдёт её, даже если подумает, что это одно слово. Да что там слитное написание, он её найдёт даже если решит, что Мать Тереза и Морис Торез родственники.

mysql> select * from metaphone where match('Морисатереза');+------+--------------------------------------+-----------+---------------------------+| id   | aoguid                               | shortname | offname                   |+------+--------------------------------------+-----------+---------------------------+| 1130 | e21aec85-0f63-4367-b9bb-1943b2b5a8fb | ул        | Мориса Тореза             |+------+--------------------------------------+-----------+---------------------------+

Можем увидеть, как работает индекс для Мориса Тореза, вызвав call keywords:

mysql> call keywords ('Мориса Тореза', 'metaphone');+------+---------------+------------+| qpos | tokenized     | normalized |+------+---------------+------------+| 1    | morisa toreza | MRSTRS     || 1    | morisa        | MRS        || 2    | toreza        | TRS        |+------+---------------+------------+

Обратите внимание, что два слова было воспринято как три: morisa, toreza и morisa toreza, притом при создании кода Metaphone, пробел был съеден.

Это особенность реализации Metaphone в Sphinx Search. Самостоятельно, с помощью регулярных выражений её не реализовать. Нет, конечно мы можем добавить регулярное выражение, удаляющее пробелы:

regexp_filter = [ ] => 

но тогда Мориса Тореза, и другие, будут всегда восприниматься как одно слово, а нам этого не надо.

Давайте сравним как работают другие индексы, в том числе те, которые ещё разобрать не успели, но они будут ниже.

Caverphone пробел сохраняет, поэтому при слитном написании просто не находит.

mysql> call keywords ('Мориса Тореза', 'caverphone');+------+-----------+------------+| qpos | tokenized | normalized |+------+-----------+------------+| 1    | mrsa trza | mrsa trza  || 1    | mrsa      | mrsa       || 2    | trza      | trza       |+------+-----------+------------+mysql> select * from caverphone where match('Морисатереза');Empty set (0.00 sec)

Оригинальный Soundex (из предыдущей публикации), в котором используется базовая реализация Sphinx, просто сходит с ума, и не понимает, как кодировать слово, в котором встретился пробел, morisa и toreza закодирован, а morisa toreza нет:

mysql> call keywords ('Мориса Тореза', 'simple_soundex');+------+---------------+---------------+| qpos | tokenized     | normalized    |+------+---------------+---------------+| 1    | morisa toreza | morisa toreza || 1    | morisa        | m620          || 2    | toreza        | t620          |+------+---------------+---------------+

Потому не включайте пробел в blend_chars в большинстве случаем это не просто бесполезно, но и вредно. Единственно исключение metaphone. И это позволяет решить самую сложную для исправления опечатку (с машинной точки зрения) опечатку в пробелах: как наличие лишних, так и отсутствие нужных.

А это дорогого стоит.

Double Metaphone

Для двойного Metaphone планировал использовать два индекса, вместо одного, как обычно, а затем искать поочерёдно в обоих.

К сожалению, я не понял, как реализовать двойной Metaphone с помощью регулярных выражений. Когда я начал искать по нему описание, меня как будто в гугле забанили, зато нашёл много реализаций на различных языках программирования, например, DoubleMetaphone.java. Я даже попытался понять этот алгоритм и реализовать его в виде регулярок, но дошёл до буквы C, и понял, что рассудок покидает меня.

Если Вы гуру гуглапоиска, или просто знаете способ, как сделать реализацию с помощью регулярных выражений пишите, пишите мне, пишите публикацию на хабр, придумаем как прикрутить его к Sphinx и Manticore.

Но будет нечестно, если про двойной Metaphone совсем ничего не написать. Опишу как бы я его сделал, если было бы ну очень нужно. Sphinx не понадобится. Но придётся программировать.

Для начала я бы подключил уже готовую библиотеку в которой он реализован, благо их нашлось множество для разных языков, я использую Java, поэтому подключаю Commons Codec. Библиотека не работает с кириллицей требуется транслитерация, и кодирует только первое слово. Поэтому если вам надо реализовать кодирование большого текста, разделённого пробелами то самостоятельно придётся разбивать строку на слова, и в цикле их перебирать.

В таблице БД, где хранятся данные, я бы добавил две новые колонки, в которых бы хранил закодированное значение. Это один из недостатков данной реализации требуется допиливать таблицы в БД.

Затем, перед вставкой новых записей в таблицу, я бы вызывал:

DoubleMetaphone dm = new DoubleMetaphone();String metaphone1 = dm.doubleMetaphone("Text", false);String metaphone2 = dm.doubleMetaphone("Text", true);

И сохранял metaphone1 и metaphone2 вместе с данными.

Это вторая большая проблема вся вставка теперь должна проходить через эту процедуру.

При поиске значений в таблице, кодируем поисковой запрос с помощью CommonsCodec. И теперь ищем по столбцам, в которых код сохранялся. Особенность двойного Metaphone в том, что кода мы кодируем поисковый запрос двумя реализациями, то мы получившиеся оба результата ищем и в первом столбце и во втором. А не первый код в первом столбце, второй код во втором: и первый, и второй код в первом столбце и первый и второй код во втором, и все их комбинации.

Без Sphinx всё стало очень неудобно.

Русский Metaphone

Не подойдёт для целей интернационализации.

Зато подразумевает отсутствие транслитерации. А это может быть весьма удобно, ибо транслитерация сама по себе несёт небольшое искажение. Получает как в игре глухой телефон, только глухой Metaphone.

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

Ну и ещё один момент, который нужно учесть при выборе, алгоритм не сжимает окончания. Значит, если улица Ленина, то надо так и писать Ленина, Ленин без окончания, не найдётся:

mysql> call keywords ('Ленина Ленин', 'rus_metaphone');+------+--------------+--------------+| qpos | tokenized    | normalized   |+------+--------------+--------------+| 1    | линина       | линина       || 2    | линин        | линин        |+------+--------------+--------------+

Реализуем регулярные выражения. Полный конфигурационный файл, как и ранее, лежит на GitHub Gist manticore.conf.

• Переделываем гласные:

regexp_filter = (?i)(йо|ио|йе|ие) => иregexp_filter = (?i)(о|ы|я) => аregexp_filter = (?i)(е|ё|э) => иregexp_filter = (?i)(ю) => у

• Для всех согласных букв, за которыми следует любая согласная, кроме Л, М, Н или Р, провести оглушение:

regexp_filter = (?i)(б)(б|в|г|д|ж|з|й|к|п|с|т|ф|х|ц|ч|ш|щ) => п\2regexp_filter = (?i)(г)(б|в|г|д|ж|з|й|к|п|с|т|ф|х|ц|ч|ш|щ) => к\2regexp_filter = (?i)(в)(б|в|г|д|ж|з|й|к|п|с|т|ф|х|ц|ч|ш|щ) => ф\2regexp_filter = (?i)(д)(б|в|г|д|ж|з|й|к|п|с|т|ф|х|ц|ч|ш|щ) => т\2regexp_filter = (?i)(ж)(б|в|г|д|ж|з|й|к|п|с|т|ф|х|ц|ч|ш|щ) => ш\2regexp_filter = (?i)(з)(б|в|г|д|ж|з|й|к|п|с|т|ф|х|ц|ч|ш|щ) => с\2

• Для согласных на конце слова, провести оглушение

regexp_filter = (?i)б\b => пregexp_filter = (?i)г\b => кregexp_filter = (?i)в\b => фregexp_filter = (?i)д\b => тregexp_filter = (?i)ж\b => шregexp_filter = (?i)з\b => з

• Склеиваем ТС и ДС в Ц

regexp_filter = (?i)(тс|дс|ц) => ц

Caverphone

Здесь сначала транслитерация.

• Затем, нужно перевести транслитерированное в нижний регистр:

regexp_filter = (A|a) => aregexp_filter = (B|b) => b

Это необходимо, потому что алгоритм для некоторых букв делает различие между тем, в каком она регистре, если в верхнем, то она считается как бы замороженной для любых изменений.

• Удалить e на конце

regexp_filter = e\b =>

• Происходит преобразование начала слова, но это актуально для новозеландских фамилий, этот шаг можно и пропустить:

regexp_filter = \b(cough) => cou2fregexp_filter = \b(rough) => rou2f

• Провести замены символов

regexp_filter = (cq) => 2qregexp_filter = (ci) => si

• Заменить все гласные в начале слова на a, в остальных случаях на 3

regexp_filter = (?i)\b(a|e|i|o|u|y) => Aregexp_filter = (?i)(a|e|i|o|u|y) => 3

• Провести очередные замены

regexp_filter = (j) => yregexp_filter = \b(y3) => Y3

• Удалить все цифры 2

regexp_filter = 2 => 

• Если на конце слова осталась цифра 3, то заменить её на A

regexp_filter = 3\b => A

• Удалить все цифры 3

regexp_filter = 3 =>

До 10 символов не сокращаю и не дополняю.

Проверим:

mysql> select * from caverphone where match ('Ленина');+------+--------------------------------------+-----------+------------------+| id   | aoguid                               | shortname | offname          |+------+--------------------------------------+-----------+------------------+|    5 | 01339f2b-6907-4cb8-919b-b71dbed23f06 | ул        | Линейная         ||  387 | 4b919f60-7f5d-4b9e-99af-a7a02d344767 | ул        | Ленина           |+------+--------------------------------------+-----------+------------------+

Кроме Ленина находит и Линейная. Согласен, некоторое сходство есть, другие алгоритмы так не смогли, ну разве что Daitch Mokotoff Soundex из предыдущей публикации выкинул что-то подобное с Лунная:

mysql> select * from daitch_mokotoff_soundex where match ('Ленина');+------+--------------------------------------+-----------+--------------+| id   | aoguid                               | shortname | offname      |+------+--------------------------------------+-----------+--------------+|  387 | 4b919f60-7f5d-4b9e-99af-a7a02d344767 | ул        | Ленина       ||  541 | 69b8220e-a42d-4fec-a346-1df56370c363 | ул        | Лунная       |+------+--------------------------------------+-----------+--------------+

Можем посмотреть как это всё кодируется:

mysql> call keywords ('Ленина Линейная Лунная', 'caverphone');+------+-----------+------------+| qpos | tokenized | normalized |+------+-----------+------------+| 1    | lnna      | lnna       || 2    | lnna      | lnna       || 3    | lna       | lna        |+------+-----------+------------+mysql> call keywords ('Ленина Линейная Лунная', 'daitch_mokotoff_soundex');+------+-----------+------------+| qpos | tokenized | normalized |+------+-----------+------------+| 1    | 866       | 866        || 2    | 8616      | 8616       || 3    | 866       | 866        |+------+-----------+------------+

Теоретически это не лишено смысла, если Вы ожидаете именно такого поведения, то смело используете, - то что надо. А коллизии всегда поможет разрешить расстояние Левенштейна, при необходимости.

Бонус: ищем ракомакофон. Вместо заключения

Это лишено практического смысла, но наблюдение забавное, поэтому напишу. Just for fun.

Помните ракомакофон, который слышится вместо rock the microphone?! Было интересно, сможет ли Metaphone понять ракомакофон. И ведь почти!

Во-первых, добавляем пробел в blend_chars, ведь нам надо чтобы три слова rock the microphone, воспринимались как одно:

blend_chars = U+0020

Поскольку у нас только один алгоритм умеет адекватно работать в такой ситуации - оригинальный metaphone, то его и применим.

Проверим с помощью keywords как оно воспринимается Sphinx:

mysql> call keywords ('ракомакофон', 'metaphone');+------+-------------+------------+| qpos | tokenized   | normalized |+------+-------------+------------+| 1    | rakomakofon | RKMKFN     |+------+-------------+------------+

И rock the microphone:

mysql> call keywords ('rock the microphone', 'metaphone');+------+---------------------+------------+| qpos | tokenized           | normalized |+------+---------------------+------------+| 1    | rock the microphone | RK0MKRFN   || 1    | rock                | RK         || 2    | the                 | 0          || 3    | microphone          | MKRFN      |+------+---------------------+------------+

Получилось RK0MKRFN, и RKMKFN, расстояние Левенштейна между ними всего 2(!). А если найти способ исключить the из кодирования, то получится RKMKRFN:

mysql> call keywords ('rock microphone', 'metaphone');+------+-----------------+------------+| qpos | tokenized       | normalized |+------+-----------------+------------+| 1    | rock microphone | RKMKRFN    || 1    | rock            | RK         || 2    | microphone      | MKRFN      |+------+-----------------+------------+

Между RKMKRFN и RKMKFN, расстояние Левенштейна всего 1! Мы почти у цели.

Проблема убрать the, параметр stopwords здесь не поможет, ибо из-за blend_chars = U+0020 the не будет восприниматься самостоятельно. Но даже если удастся сделать предобработку, то всё равно расстояние в 1, не позволит обнаружить похожий.

Надежда на qsuggest не оправдалась, - не даст подсказок. Почему? Можно заметить, что при вызове keywords есть два столбца tokenized и normalized, qsuggest даёт подсказку по столбцу tokenized и измеряет расстояние Левенштейна относительно него, qsuggest всё равно, что там, в normalized, расстояние равно 1.

Поэтому наблюдение забавное, но не практичное.