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

[English] Автор: Смирнов М.В.
Аннотация

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

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

Рассматриваемый ниже алгоритм обеспечивает нечувствительность (инвариантность) к перестановке слов в сравниваемых фразах и основан на вычислении строгого включения и пересечения между тремя конечными множествами. Одно множество А представляет собой совокупность символов латинского алфавита, которое должно строго включать пересечение двух множеств S₁ и S₂, образованных последовательностями символов двух сравниваемых фраз текста. В терминах математических множеств можно записать так:

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}, S₁ = {s₁, s₂, s₃ ... s_n}, S₂ = {s₁, s₂, s₃ ... s_m},

причем S₁ ⊆ A и S₂ ⊆ A - должно выполняться всегда. Непосредственное вычисление пересечения S₁ ∩ S₂ нам мало, что даст. Искомую метрику подобия определим как разность мощностей пересечений S₁ ∩ A и S₂ ∩ A:

Sim(S₁,S₂) = |S₁ ∩ A| - |S₂ ∩ A|.

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

Sim(S₁,S₂) = ||S₁ ∩ A| - |S₂ ∩ A||/|S₁| + |S₂|.

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

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

В программе на PHP, мощности множеств |S₁| и |S₂|, двух сравниваемых последовательностей символов 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]/ обеспечивает строгое включение S₁ ⊆ A и S₂ ⊆ A.

Множество символов латиницы A определено переменной $alfb. Вычисление метрики подобия $sim совмещено с процедурой вычисления мощностей пересечений |S₁ ∩ A| и |S₂ ∩ 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 итераций).

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

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

К недостаткам алгоритма можно отнести снижение оценки похожести (similarity) при сравнении строковых переменных значительной длины. Для улучшения качества оценки (больших текстовых сообщений), без потери скорости вычислений, необходимо перейти от гистограмм 1-го порядка (таблица 1) к гистограммам 2-го порядка, как это показано в таблице 2:


Таблица 2. Гистограмма второго порядка. Выведены значения мощности множеств двух текстов (1904 символа) в пространстве символов латинского алфавита. Так же хорошие результаты, в этом плане, демонстрирует алгоритм зеркального регулярного выражения[10] при сравнении текстовых сообщений большой длины.

Литература:

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

Статьи:
1. Программное обеспечение. Цифровая голография. Скрытые водяные знаки. Распознавание образов.
2. Инвариантная оценка сходства двух строковых переменных методом "Трех-Множеств"
3. An invariant the similarity estimate of two string variables by the "Three-Sets" method
4. On-line вычисление коэффициента Джаккарда (javascript)
5. Регистрация и восстановление цифровых голограмм в традиционных носителях информации на бумажной и пластиковой основе
6. Распределение вероятностей частоты поисковых запросов
7. Защита конфиденциальных данных методами цифровой голографии
Поиск объектов на карте по широте и долготе ГЛАВНЫЙ МИФ О ДЕПРЕССИИ