Оценка алгоритмов сходства строковых переменных. Применение зеркального регулярного выражения.
Автор: Смирнов М.В. |
Предложено использование зеркального регулярного выражения в задачах сравнения и поиска текста. Зеркальное регулярное выражение вычисляется внутри двумерного вложенного массива слов, для двух оцениваемых на схожесть текстов. Выполнено сравнение результатов вычислений с известными алгоритмами, такими как метрика Левенштейна, алгоритм Оливера, коэффициент подобия Джаккарда.
Одной из наиболее востребованных функций в системах поиска текста является функция сравнения двух строк [1]. Судя по постам и публикациям, многие программисты отдают предпочтение алгоритму Левенштейна, который обеспечивает реализацию нечеткого поиска, т.е. поиска при не строгом задании поисковой фразы [2,3,7]. Не последнюю роль в выборе функции Левенштейна играет наличие соответствующей подпрограммы levenshtein() на языке PHP [4]. Метрика или расстояние Левенштейна представляет собой минимальное количество (целое число) операций вставки, удаления и замены одного символа на другой, необходимых для превращения одной строки в другую. Так же нужно отметить еще одну подпрограмму в спецификации функций PHP, функцию similar_text(), которая находит степень похожести двух строк по алгоритму Оливера (Oliver). В алгоритме Oliver на PHP производится поиск количества общих символов в сравниваемых строках. Подпрограмма similar_text() возвращает численное значение похожести двух строк в процентах [5].
Автор настоящей статьи использовал названные подпрограммы (и ряд других) при формировании семантического ядра много-страничных сайтов в целях SEO-оптимизации под поисковые запросы [11]. Проблема автоматизированного подбора уникальных или квази-уникальных названий в семантике сайтов (интернет магазинов) известна. Основной недостаток подпрограмм levenshtein() и similar_text() состоит в чуствительности к перестановке слов в сравниваемых фразах. Рассмотрим реальный пример. В качестве первой строки будем использовать фразу «художественная резьба по камню», а во второй строке сделаем перестановку слов без их изменения – «резьба по камню художественная». Результат применения функции similar_text() составил значение похожести – 49.12%, а возвращаемое значение функции levenshtein() составило значение 38, что соответствует в относительной мере к длине строк – 29.63%.
С последней проблемой неплохо справляется алгоритм Джаккарда. Существенным недостатком алгоритма Джаккарда является критичность к ошибкам в написании слов в сравниваемых текстах: так если в одной из строк слово «художественная» будет иметь ошибку - «художественая», результат вычисления коэффициента Джаккарда, в среднем, составляет 59%, при точности 0.1 (100 итераций) [8,10]. Как справедливо отмечено в работе [9] - "неустойчивость алгоритма Джаккарда проявляется при наличии орфографических ошибок и синонимических замен". Наиболее успешным в плане инвариантности показал себя алгоритм "Трех-Множеств" [12], который так же обеспечивает улавливание единичных ошибок. Основной недостаток алгоритма "Трех-Множеств" заключается в снижении эффективности результатов сравнения при длине текста более 200-250 символов и/или при сравнении случайного набора символов, т.е. абракадабры.
Чтобы как-то оценить возможности улучшения сходства предлагается применить зеркальное регулярное выражение (ЗРВ) для всех слов в сравниваемых строковых переменных:
if( preg_match("/$ws1/",$ws2) || preg_match("/$ws2/",$ws1) ){
........ }else{ ......} ,
где строковые переменные $ws1 и $ws2 являются отдельными словами сравниваемых текстов. Основным вычислительным блоком программной реализации являтся двумерный вложенный массив:
$eq=0;
foreach($arr1 as $ws1){
foreach($arr2 as $ws2){
$lengws1 = strlen($ws1);
$lengws2 = strlen($ws2);
$deltalenws = abs($lengws1 - $lengws2);
if( preg_match("/$ws1/",$ws2) || preg_match("/$ws2/",$ws1) ){
if( $deltalenws <= $_delta_lett ){
print "совпадение: $ws1 $ws2\n";
$eq++;
}
}else{ ...алгоритм обработки несовпадения... }
}
} ,
где $arr1 и $arr1 - массивы слов сравниваемых текстов, параметр $_delta_lett, используется для игнорирования совпадения слов, разность длин которых превышает $delta_lett. Алгоритм обработки несовпадения (АОН) является дополнительным при вычислении ЗРВ. Выше представленный код реализован в подпрограмме evaltextRus(). Оценка сходства, представленных выше фраз с одной ошибкой «художественая», составила значение 92.86 %. Рассматриваемый алгоритм нечувствителен (инвариантен) к перестановкам слов в сравниваемых фразах и реагирует на отдельные ошибки снижением сходства в процентах.
Скачать архив подпрограмы evaltextRus(), а также пример сравнения двух строк на PHP можно по адресу http://www.smirnov.sp.ru/cgi_java/php/evaltextrus_zip.html [6]. Если входными данными являются текстовые (строковые) переменные в кодировке UTF-8, то в этом случае длины $lengws1 и $lengws2 удваиваются и требуется их уменьшение в 2 раза:
$lengws1 = strlen($ws1)>>1;
$lengws2 = strlen($ws2)>>1;
В алгоритме АОН применяется посимвольное сравнение и оценка несовпадения при помощи параметра $prob75. По этому параметру игнорируется
совпадение слов, если их сходство менее $prob75 % относительно длины наибольшего слова. Обычно $prob75 задается в диапазоне 0.7-0.8.
Литература:
[1] Функции сравнения строк. Справочник PHP.
[2] Расстояние Левенштейна.
[3] Применение алгоритмов нечеткого поиска в PHP
[4] Функция levenshtein(). Руководство по PHP.
[5] Функция similar_text(). Руководство по PHP.
[6] Скачать функцию evaltextRus. Вычисление зеркального регулярного выражения. Программа на PHP.
[7] Нечёткий поиск в тексте и словаре
[8] MinHash — выявляем похожие множества
[9] Н.В. Неелова, Сычугов А. А. Вычисление нечетких дублей по формуле Джаккарда с учетом синонимических замен и стоповых слов. Тула: Известия ТулГУ, 2009. К статье ..."Вычисление нечетких дублей ..."
[10] On-line вычисление коэффициента Джаккарда на JavaScript
[11] Распределение вероятностей частоты поисковых запросов
[12] Инвариантная оценка сходства двух строковых переменных методом "Трех-Множеств"