Алгоритм инвариантной оценки сходства двух строковых переменных методом "Трех-множеств"

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

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

Одной из наиболее востребованных функций в системах поиска текста является функция сравнения двух строк [1]. Судя по постам и публикациям, многие программисты отдают предпочтение алгоритму Левенштейна, который обеспечивает реализацию нечеткого поиска, т.е. поиска при не строгом задании поисковой фразы [2,3,7]. Не последнюю роль в выборе функции Левенштейна играет наличие соответствующей подпрограммы levenshtein() на языке PHP [4]. Метрика или расстояние Левенштейна представляет собой минимальное количество (целое число) операций вставки, удаления и замены одного символа на другой, необходимых для превращения одной строки в другую. Так же нужно отметить еще одну подпрограмму в спецификации функций PHP, функцию similar_text(), которая находит степень похожести двух строк по алгоритму Оливера (Oliver). В алгоритме Oliver на PHP производится поиск количества общих символов в сравниваемых строках. Подпрограмма similar_text() возвращает численное значение похожести двух строк в процентах [5].

Автор настоящей статьи использовал названные подпрограммы (и ряд других) при формировании семантического ядра много-страничных сайтов. Проблема автоматизированного подбора уникальных или квази-уникальных названий в семантике сайтов (интернет магазинов) известна. Основной недостаток подпрограмм levenshtein() и similar_text() состоит в чуствительности к перестановке слов в сравниваемых фразах. Рассмотрим реальный пример. В качестве первой строки будем использовать фразу «художественная резьба по камню», а во второй строке сделаем перестановку слов без их изменения – «резьба по камню художественная». Результат применения функции similar_text() составил значение похожести – 49.12%, а возвращаемое значение функции levenshtein() составило значение 38, что соответствует в относительной мере к длине строк – 29.63%.

С последней проблемой хорошо справляется бинарная мера сходства, предложенная Полем Джаккардом (Jaccard). Вместе с тем, существенный недостатк алгоритма Джаккарда заключается в критичности к ошибкам в написании слов в сравниваемых текстах: так если в одной из строк слово «художественная» будет иметь ошибку - «художественая», результат вычисления коэффициента Джаккарда, в среднем, составляет 59%, при точности 0.1 (100 итераций) [8]. Как справедливо отмечено в работе [9] - "неустойчивость алгоритма Джаккарда проявляется при наличии орфографических ошибок и синонимических замен".

Рассматриваемый ниже алгоритм обеспечивает нечувствительность (инвариантность) к перестановке слов в сравниваемых фразах и основан на вычислении строгого включения и пересечения между тремя конечными множествами. Одно множество А представляет собой совокупность символов латинского алфавита, которое должно строго включать пересечение двух множеств S1 и S2, образованных последовательностями символов двух сравниваемых фраз текста. В терминах математических множеств можно записать так:
A = {a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z},
S1 = {s1, s2, s3 ... sn},
S2 = {s1, s2, s3 ... sm},

причем S1 ⊆ A и S2 ⊆ A - должно выполняться всегда. Непосредственное вычисление пересечения S1 ∩ S2 нам мало, что даст. Искомую метрику подобия определим как разность мощностей пересечений S1 ∩ A и S2 ∩ A:
Sim(S1,S2) = |S1 ∩ A| - |S2 ∩ A|.

Нормированная метрика в положительном диапазоне чисел от 0 до 1 примет вид:

Sim(S1,S2) = ||S1 ∩ A| - |S2 ∩ A||/|S1| + |S2|.

Для наглядности на рисунке ниже, с помощью диаграммы Эйлера-Венна, показано искомое соотношение трех множеств:
Диаграмма Эйлера-Венна для соотношения трех множеств

Диаграмма Эйлера-Венна для соотношения трех множеств.


В программе на PHP, мощности множеств |S1| и |S2|, двух сравниваемых последовательностей символов str1 и str2, вычислим как хэши символов $hschar1 и $hschar2:
  $str1eng = preg_replace('/[^a-z]/', '', $str1eng);
  $char1 = count_chars($str1eng, 1);
  foreach ($char1 as $key => $val) {
                    $ch = chr($key);
                    $hschar1{$ch} = $val;
                                   }
  $str2eng = preg_replace('/[^a-z]/', '', $str2eng);
  $char2 = count_chars($str2eng, 1);
  foreach ($char2 as $key => $val) {
                    $ch = chr($key);
                    $hschar2{$ch} = $val;
                                    },
где count_chars() – стандартная подпрограмма PHP, а строки $str1eng и $str2eng, последовательности символов приведенные к латинице и нижнему регистру. Последняя процедура известна как транслитерация русского алфавита латиницей в нижнем регистре, например:
$r = array('а','б','в','г','д','е','ё','ж','з','и','й','к','л','м', 'н','о','п',
'р','с','т','у','ф','х','ц','ч', 'ш', 'щ', 'ъ','ы','ь','э', 'ю', 'я');

$l = array('a','b','v','g','d','e','e','g','z','i','y','k','l','m','n', 'o','p',
'r','s','t','u','f','h','c','ch','sh','sh','', 'y','y', 'e','yu','ya');

$streng = str_replace( $r, $l, mb_strtolower($str, 'UTF-8') ),
где mb_strtolower() – стандартная функция PHP. Регулярное выражение /[^a-z]/ обеспечивает строгое включение S1 ⊆ A и S2 ⊆ A.

Множество символов латиницы A определено переменной $alfb. Вычисление метрики подобия $sim совмещено с процедурой вычисления мощностей пересечений |S1 ∩ A| и |S2 ∩ A| представлено кодом:
$alfb = "abcdefghijklmnopqrstuvwxyz";
$alfbarr = preg_split("//",$alfb);
$sim = 0;
foreach($alfbarr as $aw){
            if($aw!=""){
                   $val =  $hschar1{$aw};
                   if($val){ 
                            $vv=$val;   
                             }else{ $vv=0; }
                   $val2 =  $hschar2{$aw};
                   if($val2){ 
                             $vv2=$val2;   
                             }else{ $vv2=0;}
                   $sim += abs($vv - $vv2);
            }
}       
$percent = 100*(1 - $sim/$lengtotal),
где $percent - близость (Similarity) сравниваемых строк в процентах. Графический пример гистограммы значений мощности множеств двух строк в пространстве символов латинского алфавита:
$str1 = "Сравнение двух строк с помощью инвариантной метрики"
и 
$str2 = "Сравнение двух строк с помощью метрики, инвариантной к перестановке слов"
представлен в таблице 1:
Гистограмма значений мощности множеств двух строк

Таблица 1. Гистограмма значений мощности множеств текстовых переменных в пространстве символов латинского алфавита.

Верхний график таблицы относится к строке $str1. Мера близости вычисляется с помощью подпрограммы invarDistance(), которая возвращает следующие значения:
Array
(
    [lengtotal] => 111
    [Error.count] => 17
    [Similarity] => 84.68
),
где lengtotal – суммарная длина строк, Error.count – количество «ошибочных» символов, мера близости Similarity в процентах. Построение графиков осуществляется с помощью подпрограммы invarDistanceGraph(). Скачать архив подпрограмм invarDistance() и invarDistanceGraph(), а также пример сравнения двух строк на PHP можно по адресу three_sets.zip [6]. В архиве реализован вариант множества символов A:
$alfb = "abcdefghijklmnopqrstuvwxyz0123456789".
В заключение рассмотрим еще один пример сравнения двух строк с произвольной перестановкой слов и одной "ошибкой":
$str1 = "Алгоритм поиска и анализ текста";
        и
$str2 = "Алгоритм анализа и поиска текста";
Результат вычисления метрики:
Array
(
    [lengtotal] => 55
    [Error.count] => 1
    [Similarity] => 98.18
)
Полученный результат демонстрирует регистрацию одной ошибки и практически 100%-ное подобие сравниваемых строк, несмотря на перестановки. Интересно сравнить этот результат с вычислением коэффициента Джаккарда, так же обеспечивающего инвариантность к перестановкам слов. Оценка подобия по Джаккарду дает значительно заниженный результат: 0.55-0.63 (точность 0.05, 400 итераций).

Выводы:
Метод "трех-множеств" обеспечивает инвариатность к перестановкам слов и демонстрирует устойчивость к ошибкам в написании текстов. Экспериментальное сравнение с метрикой Левенштейна, алгоритмом Оливера и коэффициентом подобия Джаккарда показало преимущество метода "трех-множеств". К недостаткам алгоритма можно отнести снижение эффективности при сравнении строковых переменных большой длины. При работе со строковыми переменными более 200-256 символов лучшие результаты демонстрирует алгоритм "зеркального регулярного выражения" [10].

Литература:
  1. Функции сравнения строк. Справочник PHP.
  2. Расстояние Левенштейна.
  3. Применение алгоритмов нечеткого поиска в PHP
  4. Функция levenshtein(). Руководство по PHP.
  5. Функция similar_text(). Руководство по PHP.
  6. Вычисление метрики инвариантной к перестановке слов. Программа на PHP.
  7. Нечёткий поиск в тексте и словаре
  8. MinHash — выявляем похожие множества
  9. Н.В. Неелова, Сычугов А. А. Вычисление нечетких дублей по формуле Джаккарда с учетом синонимических замен и стоповых слов. Тула: Известия ТулГУ, 2009. К статье
  10. Оценка алгоритмов сходства строковых переменных. Зеркальное регулярное выражение

Статьи:
1. Программное обеспечение. Цифровая голография. Скрытые водяные знаки. Распознавание образов.
2. Инвариантная оценка сходства двух строковых переменных методом "Трех-Множеств"
3. On-line вычисление коэффициента Джаккарда (javascript)
4. Регистрация и восстановление цифровых голограмм в традиционных носителях информации на бумажной и пластиковой основе
5. Распределение вероятностей частоты поисковых запросов