Нечеткое сравнение строк php

similar_text

(PHP 4, PHP 5, PHP 7, PHP 8)

similar_text — Вычисляет степень похожести двух строк

Описание

Список параметров

Изменение порядка string1 и string2 может привести к другому результату; см, пример ниже.

При передаче по ссылке третьего аргумента, similar_text() присваивает ему степень похожести двух строк в процентах, деля результат similar_text() на среднее число длин заданных строк 100 раз.

Возвращаемые значения

Возвращается количество совпадающих символов в двух строках.

Количество совпадающих символов вычисляется путём нахождения самой длинной первой общей подстроки, а затем делает это для префиксов и суффиксов рекурсивно. Добавляются длины всех найденных общих подстрок.

Примеры

Пример #1 Пример использования similar_text() с заменой аргументов

В этом примере показано, что изменение порядка аргументов string1 и string2 может дать разные результаты.

Результатом выполнения данного примера будет что-то подобное:

Смотрите также

User Contributed Notes 13 notes

Be aware when using this function, that the order of passing the strings is very important if you want to calculate the percentage of similarity, in fact, altering the variables will give a very different result, example :

= ‘PHP IS GREAT’ ;
$var_2 = ‘WITH MYSQL’ ;

Please note that this function calculates a similarity of 0 (zero) for two empty strings.

Recursive algorithm usually is very elegant one. I found a way to get better precision without the recursion. Imagine two different (or same) length ribbons with letters on each. You simply shifting one ribbon to left till it matches the letter the first.

$str1 = ‘12345678901234567890’ ;
$str2 = ‘12345678991234567890’ ;

Note that this function is case sensitive:

= ‘Hello’ ;
$var2 = ‘Hello’ ;
$var3 = ‘hello’ ;

Actually similar_text() is not bad.
it works good. But before processing i think is a good way to make a little mod like this

$var_1 = strtoupper(«doggy»);
$var_2 = strtoupper(«Dog»);

The speed issues for similar_text seem to be only an issue for long sections of text (>20000 chars).

I found a huge performance improvement in my application by just testing if the string to be tested was less than 20000 chars before calling similar_text.

20000+ took 3-5 secs to process, anything else (10000 and below) took a fraction of a second.
Fortunately for me, there was only a handful of instances with >20000 chars which I couldn’t get a comparison % for.

If you have reserved names in a database that you don’t want others to use, i find this to work pretty good.
I added strtoupper to the variables to validate typing only. Taking case into consideration will decrease similarity.

Well, as mentioned above the speed is O(N^3), i’ve done a longest common subsequence way that is O(m.n) where m and n are the length of str1 and str2, the result is a percentage and it seems to be exactly the same as similar_text percentage but with better performance. here’s the 3 functions i’m using..

//this table will be used to compute the LCS-Length, only 128 chars per string are considered
$LCS_Length_Table = array(array( 128 ),array( 128 ));

To calculate the percentage of similarity between two strings without depending on the order of the parameters and be case insensitive, I use this function based on levenshtein’s distance:

?>

This will always return a number between 0 and 1, representing the percentage, for instance 0.8 represents 80% similar strings.

If you want this to be case-sensitive, just remove the strtoupper() functions.

Источник

Нечеткое сравнение строк php

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

При этом, разумеется, есть мощные профессиональные системы поиска, такие как 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

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Запрос Лести

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

Чем длиннее слово, тем больше времени нужно для поиска похожих метафонов (что очевидно), но, в то же время, — чем длиннее слово, тем меньше времени тратится на каждую букву (что не очевидно). Предположим, что — общее время, затраченное на поиск похожих метафонов, а — общее количество букв в метафоне, похожести которого мы искали; если первое слово короче второго () и, соответственно, общее время, затраченное на поиск похожих метафонов для первого слова меньше, чем для второго (), то

\frac$» data-tex=»display»/>

Также ожидался резкий всплеск во времени при замене шаблона поиска «_» на «%», но общее время увеличивалось в пределах 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 символ. В любом случае, постарайтесь предусмотреть, чтобы предлагаемые вашим скриптом варианты не становились объектом скриншотов:

Источник

Нечёткое сравнение строк: пойми меня, если сможешь

Привет!

На естественном языке сказать об одном и том же факте можно бесконечным числом способов. Можно переставлять слова местами, заменять их на синонимы, склонять по падежам (если говорим о языке с падежами) и тд.

Необходимость определять схожесть двух фраз возникла при решении одной небольшой практической задачи. Я не использовал машинное обучение, не вил нейронные сети, но использовал простые метрики и собранную статистику для калибровки коэффициентов.

Результатом работы, описанием процесса, кодом на git’е готов поделиться с вами.

Итак, кратко задачу можно озвучить так: «С определенной периодичностью из различных источников приходят актуальные новости. Необходимо фильтровать их таким образом, чтобы на выходе не было двух новостей об одном и том же факте.»

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

Ограничения задачи

Задача имеет прикладной характер, необходимо задать ограничения:

16; Правительство внесло изменения в программу развития Курил
18; Кабмин увеличил финансирование федеральной программы развития Курил
19; Правительство увеличило финансирование программы развития Курил

6; Инженеры стали самыми востребованными на рынке труда
12; Названы самые востребованные в России профессии
20; Стали известны самые востребованные профессии в России
26; Инженеры признаны самыми востребованными на рынке труда в РФ
32; Инженеры стали самыми востребованными на рынке труда РФ в сентябре
51; Названы самые востребованные профессии в России
53; Минтруд назвал самые востребованные профессии в России

25; Сбербанк с 16 октября снижает ставки по потребительским кредитам
31; Сбербанк снизил процентные ставки по ряду кредитов
37; Сбербанк снизил ставки по ряду кредитов

0; В России выпустят собственную криптовалюту — крипторубль
5; Россия срочно создает крипторубль
27; В России займутся выпуском крипторубля
35; В России создадут свою криптовалюту
36; Россия начнет выпускать крипторубли
42; Россия выпустит собственную криптовалюту – крипторубль

Способы нечёткого сравнения строк

Опишу несколько методов для решения задачи определения степени схожести двух строк.

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

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

Алгоритм шинглов

Разбивает тексты на шинглы (англ. — чешуйки), т.е цепочки по 10 слов (с пересечениями), применив к шинглам хеш-функции получает матрицы, которые и сравнивает между собой.
Свойства: чтобы реализовать алгоритм надо подробно изучать мат.часть; работает на больших текстах; нет зависимости от порядка предложений.

Коэффициент Жаккара (частное — коэф. Танимото)

здесь a — количество символов в первой строке, b — количество символов во второй строке, c — количество совпадающих символов.
Свойства: прост в реализации; низкая точность, так как «abc» и «bca» для него одно и то же.

Комбинированных подход

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

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

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

Выделение слов
Словами считаются все последовательности символов без пробелов, которые имеют длину >= 3. Этим самым удаляются почти все предлоги, союзы и тд. — в какой степени это можно отнести к продолжению нормализации.

Сравнение слов по подстрокам

Здесь применяется коэффициент Танимото, но не к символам, а к кортежам из подряд идущих символов, причем кортежи составляются с нахлестом.

Применение коэффициента Танимото к заголовку
Мы знаем сколько всего слов в каждом из предложений, знаем количество «нечётко совпадающих» слов и применяем к этому знакомую формулу.

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

ThresholdSentence — порог принятия нечеткой эквивалентности всего предложения;
ThresholdWord — порог принятия нечеткой эквивалентности между двумя словами;
SubtokenLength — размер подстроки при сравнении двух слов (от 1 до MinWordLength)

Оценка качества работы алгоритмы

Для оценки качества работы были выделены 100 различных заголовков новостей, которые приходили друг за другом. Далее была размечена квадратная матрица 100×100, где я поставил 0, если заголовки были на разные темы и 1, если темы совпадали. Понимаю, что выборка небольшая и, возможно, не очень точно будет демонстрировать точность работы алгоритма, но меня на большее не хватило.

Теперь, когда есть образец, с которым можно сравнивать выход алгоритма, будем оценивать точность простой формулой — отношением правильных ответов к общему числу сравнений. Кроме того, как метрику, можно оценивать число ложных срабатываний.

Наилучшие результаты c точность 87% и числом ложных срабатываний 3% получаются при следующих параметрах: ThresholdSentence = 0.25, ThresholdWord = 0.45, SubtokenLength = 2;

Сравнение результатов работы алгоритма с моделью

Трактовать результаты можно так:
Наилучшая точность и наименьшее число ошибок получается, если при сравнении слов считать длину подстрок равной 2 символам, при этом должно быть отношение количества совпадающих подстрок к количеству несовпадающих большим или равным 0.45, а два заголовка будут эквивалентными, если не менее четверти слов совпадали.

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

ВТБ снизил минимальную ставку по кредитам наличными
Сбербанк снизил ставки по ряду кредитов

Заключение

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

Готовая реализация алгоритмы в виде библиотеки: SentencesFuzzyComparison.

Источник