Нечеткий поиск php и mysql

Применение алгоритмов нечеткого поиска в PHP

Для исправления опечаток в словах понадобится:
Расстояние Левенштейна (или расстояние Дамерау-Левенштейна — разница будет незначительной) — levenshtein()
Metaphone — metaphone()
Алгоритм Оливера — similar_text()
База русских слов (с падежами, учетом времен и т.д.).

Функция для транслитерации слов:

Итак, для начала получим весь словарь из БД и запишем его в массив парами, где ключ — русское слово, значение — транслитерация.

Далее проверяем наше введенное слово на наличие в словаре, если нету — делаем его транслитерацию:

После этого запускаем цикл, который будет выбирать из массива те слова, расстояние Левенштейна между «метафонами» которых не будет превышать половину «метафона» введенного слова (грубо говоря, допускается до половины неправильно написанных согласных букв), потом, среди выбранных вариантов, снова проверяем расстояние, но по всему слову, а не по его «метафону» и подошедшие слова записываем в массив:

Теперь зададим переменные, где расстояние Левенштейна будет равно заведомо большому числу, а «similar text» — заведомо малое число.

Это нужно для определения максимального значения «подобности» между нашим словом и словами в массиве, а также минимального расстояния Левенштейна. Для начала найдем минимальное расстояние Левенштейна:

И, аналогично, ищем максимальное значение «подобности» для тех слов, в которых расстояние Левенштейна будет минимальным:

Теперь запускаем цикл, который выберет все слова с наименьшим расстоянием Левенштейна и наибольшим значением «подобности» одновременно:

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

И получаем окончательный массив, который, в идеале, должен содержать одно слово:

И возвращаем правильное слово, которое хранится как ключ:

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

Результат:

Минус:

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

Источник

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

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

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

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

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

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

При каждом поиске необходимо будет рассчитывать расстояние Левенштейна. Для этого нужно найти самую быструю имплементацию алгоритма для MySQL.

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

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

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

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

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

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

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

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

Для тестов будут использоваться 5 слов (а точнее, их ошибочное написание), 3 из них на кириллице, и 2 на латинице:

В последнем слове намеренно было сделано больше ошибок, чтобы расстояние Левенштейна было в 2 символа. Если каждый способ работает правильно, при поиске последнего слова каждый раз будет возвращаться 0 строк.

Запрос Лести

LIKE проверялся с обоими шаблонами поиска, как со знаком подчёркивания, так и со знаком процента.

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

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

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

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

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

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

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

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

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

Функция Торреса показала превосходные результаты в сравнении с запросом Лести и особенно в сравнении с функцией Раста. Второй плюс — Торрес использовал расширенный алгоритм Дамерау-Левенштейна, где к операциям вставки, удаления и замены добавлена операция транспозиции. Сравним результаты функции Торреса и запроса Лести:

Разница в количестве возвращаемых строк может быть объяснена разницей в использованных алгоритмах (Левенштейна и Дамерау-Левенштейна для запроса Лести и функции Торреса соответственно). В 5 случаях из 5 победителем стала функция Торреса, поэтому она и будет применяться в завершающей реализации на PHP, где полученный результат рафинируется функцией similar_text.

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

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

Результат может выглядеть так:

Итоги

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

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

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

Источник

Нечеткий поиск PHP / MySQL

Я ищу реализовать нечеткий поиск небольшого приложения PHP / MySQL. В частности, у меня есть база данных с около 2400 записей (записи добавляются со скоростью около 600 в год, поэтому это небольшая база данных). Три интересующих поля – это адрес улицы, фамилия и дата. Я хочу иметь возможность искать по одному из этих полей и, по существу, иметь толерантность к ошибкам орфографии / символа. т.е. адрес «123 Main Street» также должен соответствовать «123 Main St», «123 Main St.», «123 Mian St», «123 Man St», «132 Main St» и т. д., а также для имени и дата.

Основные вопросы, которые я имею с ответами на другие подобные вопросы:

Ответ Рацци (или с использованием Дамерау-Левенштейна ) оценивает список матчей кандидатов в соответствии с их близостью к поисковому ключу. (Позаботьтесь: если клавиша «12 Main St», то «13 Main St» имеет такое же расстояние ввода, что и «12 Moin St», но вы можете захотеть ранжировать его на низком уровне или даже исключить его, как в 11 и 22 Main St и т.д.)

Но как вы выбираете список кандидатов управляемого размера для ранжирования?

Один из способов – вычислить значение метафона (или значения, используя двойной метафон) для каждого слова в строках, которые вы собираетесь искать. Сохраните каждый из этих метафонов в другой таблице с идентификатором строки, содержащей исходную строку. Затем вы можете быстро найти эти значения метафонов с помощью LIKE ‘key%’, где ключ является метафоном слова из текста поиска.

Источник

mysql — PHP / SQL: множественный нечеткий поиск по ключевым словам на основе сходства (Расширенный поиск SQL)

В настоящее время я выполняю поиск по ключевым словам, используя несколько ключевых слов в PHP и SQL. Поле, к которому я применяю поиск, является заглавие поле, которое представляет собой поле 250 VARCHAR.

Пользователь может ввести одно ключевое слово, например, «яблоко» или также несколько, например «яблочно-банановый желтый». Первый вариант тривиален. Для второго варианта мой текущий алгоритм работает так:

Алгоритм очень простой, но достаточно забавный, работает довольно хорошо.

Однако сейчас я пытаюсь реализовать более умный алгоритм поиска без необходимости полагаться на внешние оплаченный скрипты, такие как сервисы Amazon. Я ищу способ реализовать следующее:

Как лучше всего начать такой поиск? Я использую InnoDB для MySQL.

Решение

Предполагая MySQL, вы можете добавить полный текстовый индекс. Затем, есть ряд функций, которые позволят вам выполнять такие базовые поиски, которые соответствуют всем перечисленным потребностям: https://dev.mysql.com/doc/refman/5.7/en/fulltext-search.html

В итоге вы используете синтаксис, такой как:

Чтобы увидеть счет матча

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

Кроме того, приятно отметить, что существуют системные конфигурации, которые необходимы для управления символами мин / макс слов / токенов для индексации. Ты можешь читать https://dev.mysql.com/doc/refman/5.7/en/fulltext-fine-tuning.html чтобы получить более глубокое понимание вариантов индексирования. Перкона также хороший ресурс https://www.percona.com/blog/2013/02/26/myisam-vs-innodb-full-text-search-in-mysql-5-6-part-1/ (обычно более удобоваримый, чем документация MySQL).

Источник

Нечеткий поиск php и mysql

Бывает, что нужно найти в списке слов наиболее похожие на заданное слово.
Например, если у вас есть список городов, и нужно найти среди них наиболее похожий на то, что ввёл пользователь, даже если при вводе пользователь допустил ошибки.

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

Для таких случаев я написал на php инструмент для нечеткого поиска среди массива строк.

В каких случаях может пригодится данный инструмент:

1. Поиск среди списка стран мира

2. Поиск среди названий страниц вашего сайта в админ-панели

3. Поиск среди уникальных имён ваших пользователей

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

Я, например, написал этот инструмент для того, чтобы разделять поле ФИО, в которое люди вписывают имя, фамилию и отчество в произвольном формате, на отдельные поля Имя, Фамилия и Отчество, с соответствующими значениями.

Где взять:

Можно взять класс FastFuzzySearch прямо из репозитория:
https://github.com/MihanEntalpo/FastFuzzySearch

Также, можно установить FastFuzzySearch с использованием composer:

В вашем файле composer.json нужно прописать:

Использование:

Принцип действия

Работа программы основана на алгоритме, основанном на так называемых n-gram’ах, похожем на алгоритм шинглов.

Для понимания её работы можно взглянуть на вот такую простую функцию для нечёткого сравнения двух строк (приведена для примера, в FastFuzzySearch она не используется):

Быстродействие

Для проверки быстродействия был написан скрипт, формирующий массивы слов разного размера, и запускающий поиск среди них тремя способами: с помощью быстрого нечёткого поиска, с помощью расстояния левештейна и с помощью функции similar_text. Такие функции как metaphone и soundex я не стал использовать, так как назначение у них другое — находить похожие по звучанию слова. В моём же случае, поиск найдёт даже не слишком похожие по звучанию, но, при этом, близкие по нечёткому сравнению.

Как раз для этой цели в класс FastFuzzySearch добавлены функции findByLevestaine и findBySimilarText.
Сам код проверки на быстродействие находится в файле /examples/example2.php из упомянутого выше репозитория.

При проверке производится поиск 200 слов по массиву, состоящему из 21376 слов (это список всех более-менее крупных городов России, повторённый 16 раз для увеличения сложности).

Результат:

Здесь:
Инициализация с нуля — это построение поискового индекса FastFuzzySearch по переданному массиву.
Сериализация индекса — это преобразование поискового индекса в строку для хранения её в кэше, и быстрой загрузки (если ваш массив, по которому требуется искать, не меняется каждый раз — имеет смысл вместо перестроения индекса просто закешировать его где-то (в memcache, в файле, в базе данных), чтобы быстро загружать перед использованием)
Инициализация из сериализованного индекса — это как раз процесс загрузки сериализованного индекса, вместо построения с нуля. Как видно, этот процесс в 30 раз быстрее чем инициализация с нуля, причём, чем больше слов в индексе, тем больше этот разрыв.

Как несложно заметить, функция FastFuzzySearch->find работает достаточно быстро, чтобы использовать её в случаях, когда требуется, например, подсказывать пользователю исправленный вариант введённого им с ошибками запроса, когда вариантов не слишком много.

Зависимость быстродействия от входных данных

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

Выводы сделанные в ходе экспериментов:

1) При росте количества строк в индексе довольно быстро растёт объём индекса (в байтах), и время его построения, однако скорость поиска снижается весьма медленно.

2) При росте длины строк в индексе, вплоть до 640 байт, размер индекса растёт очень быстро, вплоть до 300МБ, полученных в эксперименте, скорость же поиска практически никак не меняется.

3) При увеличении длины искомого слова, время поиска увеличивается пропорционально квадрату длины слова.

8 комментариев

Спасибо за найденную ошибку. Исправил баг, выгрузил версию 0.2.2

алгоритм вычисления процента сходства дает не всегда нужный результат:
при поиске «аспирин» — слово «ир» имеет такой-же процент сходства, как и «аспирин».
ир — 1/1 = 100%, аспирин — 15/15 = 100%

Да, нелогичное поведение. Проверю, и попробую поправить.

Доработал алгоритм, выгрузил в гитхаб и обновил версию в composer’е, теперь процент вычисляется исходя из общего количества «кусочков», на которые разбиваются слова — то, которое ищем + то, которое нашли. Соответственно, такой проблемы, как 100% соответствие искомого слова и более короткого слова в базе — больше нет.

В result[‘word’] надо возвращать оригинально значение из словаря, а не то что вернулось из prepare_word, отправил пулл реквест.

Спасибо, соглашусь с тем, что логично возвращать такое же слово, какое было принято при инициализации. Запросил у тебя две мелкие правки в твоём пулл реквесте, как внесёшь их — сразу же и приму 🙂

Принял изменение. А ещё подправил алгоритм сравнения, так-как он изредка давал результаты более 100%. Теперь всё вычисляется правильно. Обновил пакет в composer, там теперь v0.2.4

Источник