05.04.2021 04:53
Tkachenko-Ivan 2 445 Источник

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

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

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

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

Докер образ

Подготовил докер образ tkachenkoivan/searchfonetic, для того чтобы можно было "пощупать" результат. В образ добавлены все индексы и из этой публикации и из предыдущей, но, внимание, названия индексов из предыдущей публикации не соответствуют тому что хранится в образе. Почему? Потому что хорошая мысля приходит опосля.

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

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

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

	regexp_filter = (А|а) => a
	regexp_filter = (Б|б) => b
	regexp_filter = (В|в) => v
	…

И включаем metaphone:

morphology = metaphone

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

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

Дело в том что у Sphinx есть в такой параметр blend_chars. Смысл следующий, Sphinx индексирует по словам, а слова он находит по разделителям, например, если между буквами есть пробел, значит буквы – два разных слова, перенос строки, табуляция, знаки препинания и т.д., и т.п. Но могут быть символы, которые одновременно разделяют слова, а могут быть и частью одного слова, например, «&». «M&M’s» это сколько слов? А «Рога&Копыта»? Для таких случаев и существует 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 вместе с данными.

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

При поиске значений в таблице, кодируем поисковой запрос с помощью Commons Codec. И теперь ищем по столбцам, в которых код сохранялся. Особенность двойного 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)(б)(б|в|г|д|ж|з|й|к|п|с|т|ф|х|ц|ч|ш|щ) => п\2
regexp_filter = (?i)(г)(б|в|г|д|ж|з|й|к|п|с|т|ф|х|ц|ч|ш|щ) => к\2
regexp_filter = (?i)(в)(б|в|г|д|ж|з|й|к|п|с|т|ф|х|ц|ч|ш|щ) => ф\2
regexp_filter = (?i)(д)(б|в|г|д|ж|з|й|к|п|с|т|ф|х|ц|ч|ш|щ) => т\2
regexp_filter = (?i)(ж)(б|в|г|д|ж|з|й|к|п|с|т|ф|х|ц|ч|ш|щ) => ш\2
regexp_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) => a
regexp_filter = (B|b) => b
…

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

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

regexp_filter = e\b =>

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

regexp_filter = \b(cough) => cou2f
regexp_filter = \b(rough) => rou2f
…

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

regexp_filter = (cq) => 2q
regexp_filter = (ci) => si
…

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

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

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

regexp_filter = (j) => y
regexp_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.

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