Интернационализация поиска по городским адресам. Реализуем русскоязычный Soundex на Sphinx Search

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

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

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

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

В публикации опишу как реализовать фонетические алгоритмы поиска 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