Оценка алгоритмов сходства строковых переменных. Применение зеркального регулярного выражения.

Автор: Смирнов М.В.
Оценка алгоритмов сходства строковых переменных методом зеркального регулярного выражения
Аннотация

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

Одной из наиболее востребованных функций в системах поиска текста является функция сравнения двух строк [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] - "неустойчивость алгоритма Джаккарда проявляется при наличии орфографических ошибок и синонимических замен".

Чтобы как-то оценить возможности улучшения сходства предлагается применить зеркальное регулярное выражение (ЗРВ) для всех слов в сравниваемых строковых переменных:
  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] Распределение вероятностей частоты поисковых запросов



Home http://www.smirnov.sp.ru/
The elements of the probabilistic analysis of the Forex markethttp://www.smirnov.sp.ru/forex_html/forex3eng.html
Currency Prediction Software of market FOREXhttp://www.smirnov.sp.ru/forex_html/usd_euro15.html
Technology of a GUARD of text files from unauthorized copyinghttp://www.smirnov.sp.ru/graphic_text/pastxt1eng.html
Software for evaluating of ground resolution of remote sensing optical-systemhttp://www.smirnov.sp.ru/special/index.html
Objective estimation of digital scanners qualityhttp://www.smirnov.sp.ru/scanner/scan02.html
Watermarking photoshttp://www.smirnov.sp.ru/watermark/index.html
Restoration of imageshttp://www.smirnov.sp.ru/scanner/filter/index.html
Visual Gallery Manager 2.0http://www.smirnov.sp.ru/vgm20/index.html
Physical simulation of optical-electronic system of high-resolutionhttp://www.smirnov.sp.ru/simult_oes/index.html
Technology of counteraction to falsification of credit cardshttp://www.smirnov.sp.ru/watermark/cards/card_eng.html
Free Advertisment. Free Bulletin Board (english).http://www.smirnov.sp.ru/wwwboard/engboard.html
Free Advertisment. Free Bulletin Board (russian).http://www.smirnov.sp.ru/wwwboard/rusboard.html
Contact ushttp://www.smirnov.sp.ru/wwwboard/eng/contact.html
Ozon Bookshophttp://www.smirnov.sp.ru/ozon/index.html
The latent transfer and storage of the confidential information on the Internet and cellular communicationhttp://www.smirnov.sp.ru/watermark/conf_data/guarding_eng.html
Software Prices http://www.smirnov.sp.ru/prices/prices_eng.html
Smirnov HomePage http://www.smirnov.sp.ru/man/page1eng.html

St. Petersburg, Russia
Mobile: +7(921)343-33-97
E-mail: smirnoff04@mail.ru
http://www.smirnov.sp.ru/