Интернационализация поиска по городским адресам. Реализуем русскоязычный 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) => 0
regexp_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+ => 0
regexp_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 на конце

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

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

Проверяем:

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    |
+---------------+----------+------+

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

Узнать правду

paanarscaj → Пионерская

plachanavscaj → Плехановская

latavscaj → Литовская

sladcavscaj → Сладковская

pacravscaj → Покровская

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

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. Разработчики Manticore Search, хвастаются что прогресс идёт в гору семимильными шагами. Может там будет поддержка и прочих алгоритмов, хотя бы для латиницы, а может и сразу для кириллицы.

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

P.S.

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

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

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

3. ????

4. PROFIT

UPD Metaphone

Статья по Metaphone вышла: "Продолжаем интернационализацию поиска по адресам с помощью Sphinx или Manticore. Теперь Metaphone".

UPD Docker

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