Методы нечеткого поиска в SQL: Расстояние Левенштейна

В одном из проектов, работающих внутри TheFroot, запилили любопытную штуку – нечеткий поиск в SQL посредством расстояния Левенштейна. В статье, за совместным авторством Виталия Прохоненкова и Виталия Тарасенко, рассказываем о том, что это и как с этим жить.

Магазин Froot

Это маркетплейс, где один товар могут продавать десяток продавцов, выставляя разную стоимость. Подробнее о проектах Froot в портфолио rocketfirm.com.



Товар в базу данных магазина продавец передает через XML или через API. Продавец указывает, как называется товар, сколько его штук и сколько он стоит — все из его базы данных товаров. С количеством и стоимостью товара никаких проблем нет — бери себе, складывай в соответствующие ячейки SQL и выводи после на сайте. Проблема появилась с названиями.


Чаще всего продавец уже продает товары через свой сервис — то есть, у него есть своя система названий товаров, которую он под нас менять не будет (это время, деньги и лень). Имеем проблему: товар под названием “iPhone X серый 256 гигабайт” и “iPhone X 256 Gray”, попав в нашу базу, не найдут друг друга и станут двумя разными товарами. Если таких продавцов 10, и у каждого свое название (не говоря об ошибках в названиях), это не сделает хорошо ни нам, ни покупателям.

В многих маркетах эту проблему решают просто: сидит специально обученный человек и совмещает это все руками. Пришел к нему “iPhone X Grey 256 retina”, он его заботливо добавляет к “iPhone X 256Gb Gray”. У клиента таких ресурсов не оказалось, но подвернулся интересный инструмент — расстояние Левенштейна.

Расстояние Левенштейна

Расстояние Левенштейна — алгоритм нечеткого поиска. С помощью “расстояния” есть возможность находить соответствие между записями, которые в базе данных выглядят по-разному. Использование этого алгоритма позволяет находить слова и фразы в которых сделали опечатку или написал английское слово русскими буквами. После нахождения сравниваем названия с теми, что у нас есть в базе данных, и руками добавлять товар к товару не нужно.


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

Например, в базе есть товар "Мобильный телефон Nokia 105 DS 2017 Blue". Его метафон будет примерно равен MBLNTELEFONNOK105DS. Если метафон фразы, на основании которой мы ищем поиск совпадет или похож (при соблюдении заданных ограничений), система примет два товара за один.

Минус “Левенштейна”, что если у случайного товара окажется похожий метафон, он добавится не к своей записи. То есть, применять расстояние Левенштейна бессмысленно, когда товар называется S3 (подразумевая Samsung S3), ибо точно найдется что-то другое, что на сто процентов будет совпадать по названию, но не будет являтся Самсунгом S3. Риск легко реализуется, увидь вы, как изгаляются с названиями продавцы.

Скрипт можно настроить, указав, насколько жестким должно быть сравнение – настраиваем количество символов, которые могут не соответствовать друг другу.

На практике, это работает так:

Ищем "Мобильный телефон Nokia 105 DS 2017 Blue"

Находим Мобильный телефон Nokia 105 DS 2017 Blue


Ищем Mobile telephone Nokia 105 DS 2017 Blue

Находим Мобильный телефон Nokia 105 DS 2017 Blue


Ищем "Мобильный телефон Nokia 105 DS 2017"

Находим Мобильный телефон Nokia 105 DS 2017 Blue


Ищем "Nokia telephone Мобильный 2017 105 DS"

Находим Мобильный телефон Nokia 105 DS 2017 Blue


Ищем "Нокиа ТИлИфон МАбЕльнЙЫ 105 DS"

Находим Мобильный телефон Nokia 105 DS 2017 Blue


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

Установка для MySQL

1. Устанавливаем плагин к MySQL отсюда: https://github.com/ifsnop/damlev. При установке могут возникнуть проблемы с локалью, самое простое решение – установка локали в LC_ALL.

2. В файле srs/damlevlim.c, в строке 169 нужно заменить setlocale(LC_CTYPE, "es_ES.UTF-8") на setlocale (LC_ALL,""); , что установит системную локаль. Или же можно установить какую то конкретную локаль, как в файле, но обязательно чтобы она была установлена и в системе.

3. Делаем расчет метафонов для каждого слова или фразы, так как метафон можно рассчитать только для латиницы, то слово или фразу нужно транслитерировать.

4. Далее запрос в БД:

SELECT id, title FROM table WHERE damlevlim("BNNBKF",metaphone,20)=1

Где damlevlim – функция которую предоставляет плагин. Функция принимает три параметра – две строки для сравнения, и целое число INT – верхняя граница, то есть, максимальное количество символов, которые будут браться с каждой строки для сравнения.

Metaphone – поле в таблице хранящее метафон тайтла,

"BNNBKF" — метафон от искомого значения,

1 – расстояние Дамерау-Левенштейна в 1 символ, говоря проще если 1 то допускается одно несоответствие в метафонах, если 0, то метафоны должны быть один в один.

Информация в сети

О Расстоянии Левенштейна в википедии

Подробная статья на хабре

February 25, 2019
by Rocket Firm
1
31

Результаты внутреннего конкурса дизайнеров


В «Ракетную» часто требуются талантливые ребята. В этот раз мы искали дизайнеров и попросили сделать их тестовое задание. Арт-директор Максим Перфильев расскажет о результатах.

Задание

Предложите мобильную версию главной страницы epay.railways.kz: функциональные улучшения и новое оформление. Результат работы — 1 картинка в формате jpeg или png.

Немного статистики

194 отклика 
72 предложения выполнить тестовое задание
42 задания выполнено
5 дизайнерам предложена работа
3 дизайнера остались работать спустя месяц

Конверсия — говно. Если бы это была форма на сайте — стоило бы её переделать.

Оценка работ

Оцениваем работы по 5-бальной системе

Работы на 1-2

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

Работы на 3

Тут либо проблема с оформлением, либо с решением задачи. Глаза местами всё ещё кровоточат, но уже не так сильно. Ребята попытались подумать, но что-то не получилось и они решили взять кальку с авиасейлс. На вопрос о принятых решениях в основном отвечают что на авиасейлс так и разницы нет, если учесть что оба проекта продают билеты. (спойлер: она есть, и большая)

Работы на 4

На этих работах видно, что ребята подумали, посмотрели авиасейлс, еще раз подумали и потом уже нарисовали. Визуально норм, но не больше. Задача решена также, как оформлена — норм. Я все еще не найду билет, но не найду его более комфортно. Поле «обратно» усиливает вероятность не найти билет с помощью поиска.

Итог

Работ на «пятёрочку» не прислал никто. Нарисовать красивенько и исправить поверхностные проблемы смогли многие, но самая большая проблема так и не была решена — я все еще фиг найду билет с помощью поиска.

December 12, 2018
by Rocket Firm
2
131
Show more