Расстояние Левенштейна в MySQL и алгоритмы нечёткого поиска средствами PHP

Расстояние Левенштейна в MySQL и алгоритмы нечёткого поиска средствами PHP

Знаменитый советский и российский математик Владимир Иосифович Левенштейн (кстати, ушедший из жизни два с небольшим месяца назад) в начале второй половины прошлого века ввёл понятие дистанции редактирования, которым мы пользуемся по сей день в различных сферах — от поисковых систем до биоинформатики. В этой статье мы применим его принцип для нечёткого поиска в MySQL (поскольку MySQL на данный момент пока не предлагает встроенного решения), вычислив самый эффективный (т.е. быстрый) способ из нескольких найденных в интернете, построим алгоритм такого поиска и реализуем его на PHP.

Чем будем пользоваться:

    и расстояние Дамерау-Левенштейна: оба представляют собой минимальное количество операций для преобразования одной строки в другую, отличаясь операциями — Левенштейн предложил операции вставки, удаления и замены одного символа, а Дамерау дополнил их операцией транспозиции, т.е. когда два соседних символа меняются местами; для MySQL были предложены следующие имплементации:
      , автор — Gordon Lesti опубликованная в книге Get It Done With MySQL 5&Up (ред. Peter Brawley и Arthur Fuller), автор — Jason Rust написанная на основе функции на Си, написанной Линусом Торвальдсом, автор — Diego Torres
    • в PHP представлен функцией similar_text
    • в PHP представлен функцией metaphone
      и его PHP функция soundex: алгоритм устарел (был предложен в начале прошлого века), совершенно не похожие друг на друга слова получают одинаковые индексы , т.к. у PHP нет соответствующих им функций

    Алгоритм нечёткого поиска

    Очевидно, что нет смысла при каждом поиске вычислять расстояние Левенштейна между введённым словом и каждым словом из словаря в БД, т.к. это займёт много времени. Кстати, несколько лет назад на хабре был описан способ, в котором при каждом поиске весь словарь из БД загонялся в PHP-массив, транслитерировался, и дальше подбирались похожие слова, попеременно используя то функцию levenshtein, то metaphone, то similar_text, то две сразу. Решение предварительной быстрой фильтровки и последующего рафинирования найденных вариантов напрашивается само собой.

    Таким образом, суть алгоритма нечёткого поиска может быть сведена к следующему:

    1. Вычислить метафон поискового запроса.
    2. Найти все слова в словаре в БД по метафону с расстоянием Левенштейна (или Дамерау-Левенштейна) < 2 символов.
    3. Если ничего не найдено — юзер сделал слишком много ошибок в слове, прекращаем мучить БД и пишем, что юзер идёт в баню ничего не найдено.
    4. Если найдено 1 слово — возвращаем его.
    5. Если найдено > 1 слова — рафинируем: находим процент похожести поискового запроса с каждым найденным словом из словаря в БД; находим максимальный процент похожести; возвращаем все слова с этим процентом (на случай, если несколько слов будут иметь одинаковый процент, который окажется максимальным).

    Подготовка БД

    Для всех тестов была выбрана база населённых пунктов, 4 года назад вытащенная из Вконтакте. Для тестов использовалась таблица городов, которая содержит более 2,2 миллионов записей, частично переведённых на 13 языков. Были оставлены только колонки с русским переводом, которые содержали много непереведённых названий. Также был сделан индекс по колонке city_id.

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

    Таким образом, PHP-код для добавления колонки метафонов выглядит следующим образом:

    Для 2 246 813 строк расчёт метафона и его вставка заняли

    Также был сделан индекс по колонке metaphone, т.к. дальнейшие операции поиска будут происходить только в ней.

    Выбираем имплементацию расстояния Левенштейна для MySQL

    Как было отмечено раннее, на быстроту будут проверяться три имплементации — запрос Лести, функция Раста и функция Торреса.

    Для тестов будут использоваться 5 слов (а точнее, их ошибочное написание), 3 из них на кириллице, и 2 на латинице: № Правильное написание Его метафон Неправильное написание Его метафон Левенштейн метафонов 1. Александровск-Сахалинский ALKSNTRFSKSHLNSK Аликсандравск-саголинзкий ALKSNTRFSKSKLNSK 1 2. Семикаракорск SMKRKRSK Семикораковск SMKRKFSK 1 3. Чаренцаван XRNTSFN Черенцева XRNTSF 1 4. Bounounbougoula BNNBKL Bonunboguva BNNBKF 1 5. Kampong Tenaki Kawang KMPNKTNKKWNK Kampontenaki Kavang KMPNTNKKFNK 2 В последнем слове намеренно было сделано больше ошибок, чтобы расстояние Левенштейна было в 2 символа. Если каждый способ работает правильно, при поиске последнего слова каждый раз будет возвращаться 0 строк.

    Запрос Лести

    Первый вариант — самый примитивный из всех трёх: здесь за основу взят принцип расстояния Левенштейна (операции вставки, удаления и замены), который имитируется в SQL-запросе, используя большое количество операторов LIKE. Если строка (слово) состоит из символов (букв), количество операторов LIKE при поиске расстояния Левенштейна в 1 символ будет равно (или при поиске расстояния Левенштейна < 2 символов).

    В конце статьи автор предлагает PHP-функцию для автоматизации составления таких SQL-запросов. Эта функция изменена применительно для нашего поиска по метафонам, но принцип оставлен тот же:

    LIKE проверялся с обоими шаблонами поиска, как со знаком подчёркивания, так и со знаком процента. № слова t для LIKE с "_", сек Найдено t для LIKE с "%", сек Найдено 1. 24.2 1 24.6 1 2. 14.1 1 14.8 4 3. 11.9 188 12.3 224 4. 11.9 70 12.8 87 5. 18.1 0 19.6 0 Чем длиннее слово, тем больше времени нужно для поиска похожих метафонов (что очевидно), но, в то же время, — чем длиннее слово, тем меньше времени тратится на каждую букву (что не очевидно). Предположим, что — общее время, затраченное на поиск похожих метафонов, а — общее количество букв в метафоне, похожести которого мы искали; если первое слово короче второго ( ) и, соответственно, общее время, затраченное на поиск похожих метафонов для первого слова меньше, чем для второго ( ), то

    Также ожидался резкий всплеск во времени при замене шаблона поиска "_" на "%", но общее время увеличивалось в пределах 2-8%.

    Функция Раста

    Второй вариант представляет собой пользовательскую функцию levenshtein, которая принимает два параметра — две строки VARCHAR(255), и возвращает число INT — расстояние Левенштейна. Предлагается также вспомогательная функция levenshtein_ratio, которая на основе рассчитанного предыдущей функцией расстояния Левенштейна возвращает процент похожести двух строк (по аналогии с PHP-функцией similar_text). Тестировать будем только первую функцию.

    Попробуем найти все слова с расстоянием Левенштейна в 1 символ:

    Поиск похожих метафонов для четвёртого названия (у которого самый короткий метафон) дал такие же результаты, как и при поиске с помощью LIKE с шаблоном поиска "_", однако занял

    66 минут, поэтому было решено не продолжать тестировать остальные слова.

    Функция Торреса

    Третий вариант представляет собой имплементацию функции, написанной на Си Линусом Торвальдсом. Эта функция принимает три параметра — две строки для сравнения, и целое число INT — верхняя граница, т.е. максимальное количество символов, которые будут браться с каждой строки для сравнения.

    Установим универсальную верхнюю границу для всех метафонов из нашего теста — 20 символов, и попробуем найти все слова с расстоянием Дамерау-Левенштейна в 1 символ:

    Результаты: № слова t для ф-ии Торреса, сек Найдено 1. 11.24 1 2. 9.25 1 3. 9.19 173 4. 8.3 86 5. 11.57 0 Функция Торреса показала превосходные результаты в сравнении с запросом Лести и особенно в сравнении с функцией Раста. Второй плюс — Торрес использовал расширенный алгоритм Дамерау-Левенштейна, где к операциям вставки, удаления и замены добавлена операция транспозиции. Сравним результаты функции Торреса и запроса Лести: № слова t для запроса Лести, сек t для ф-ии Торреса, сек Запрос Лести, найдено слов Ф-я Торреса, найдено слов 1. 24.2 11.24 1 1 2. 14.1 9.25 1 1 3. 11.9 9.19 188 173 4. 11.9 8.3 70 86 5. 18.1 11.57 0 0 Разница в количестве возвращаемых строк может быть объяснена разницей в использованных алгоритмах (Левенштейна и Дамерау-Левенштейна для запроса Лести и функции Торреса соответственно). В 5 случаях из 5 победителем стала функция Торреса, поэтому она и будет применяться в завершающей реализации на PHP, где полученный результат рафинируется функцией similar_text.

    Реализация на PHP

    Наиболее точные результаты при рафинировании могут быть получены, если поисковый запрос не будет транслитерироваться, т.е. после получения похожих слов они будут сравниваться с оригиналом. В ходе экспериментов было установлено, что функция similar_text возвращает разные результаты для слов на кириллице и латинице при одинаковом расстоянии Левенштейна. Поэтому для чистоты рассчётов дополнительно будет использована функция utf8_to_extended_ascii, изначально предложенная luciole75w для решения такой же проблемы при использовании PHP-функции levenshtein.

    Результат может выглядеть так: Ищем название: Черенцева Возможно, Вы ищите: Чаренцаван, Черенцовка

    Итоги

    Самой быстрой оказалась имплементация расстояния Дамерау-Левенштейна, написанная Линусом Торвальдсом на Си и адаптированная Диего Торресом для MySQL в виде пользовательской функции. На втором месте с небольшой разницей во времени идёт примитивная имитация расстояния Левенштейна в виде SQL-запроса с большим количеством операторов LIKE, автор — Гордон Лести. На третьем месте далеко позади осталась пользовательская функция для MySQL от Джейсона Раста.

    В заключении хотелось бы добавить, что использовать рассчёт расстояния Левенштейна в MySQL в продакшене необходимо только в случаях, когда строка, с которой нужно сравнивать, — короткая, а таблица со словами, которые подлежат сравнению со строкой — маленькая. В противном случае возможным решением в случае таблицы с большим словарём может быть её разделение на несколько таблиц, например, по первой букве, или по длине слова или его метафона.

    Чаще всего, область применения алгоритмов нечёткого поиска в вебе — поиски названий и имён по имеющемуся словарю, где высока вероятность того, что юзер может сделать опечатку или ошибиться хотя бы на 1 символ. В любом случае, постарайтесь предусмотреть, чтобы предлагаемые вашим скриптом варианты не становились объектом скриншотов: