Методы нечеткого поиска в 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, то метафоны должны быть один в один.