Алгоритм инвариантной оценки сходства двух строковых переменных методом Трех-Множеств
[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] - "неустойчивость алгоритма Джаккарда проявляется при наличии орфографических ошибок и синонимических замен".
Рассматриваемый ниже алгоритм обеспечивает нечувствительность (инвариантность) к перестановке слов в сравниваемых фразах и основан на вычислении строгого включения и пересечения между тремя конечными множествами. Одно множество А представляет собой совокупность символов латинского алфавита, которое должно строго включать пересечение двух множеств 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;
},
$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:
 |
Верхний график таблицы относится к строке $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:
 |
Литература:
- Функции сравнения строк. Справочник PHP.
- Расстояние Левенштейна.
- Применение алгоритмов нечеткого поиска в PHP
- Функция levenshtein(). Руководство по PHP.
- Функция similar_text(). Руководство по PHP.
- Вычисление метрики инвариантной к перестановке слов. Программа на PHP.
- Нечёткий поиск в тексте и словаре
- MinHash — выявляем похожие множества
- Н.В. Неелова, Сычугов А. А. Вычисление нечетких дублей по формуле Джаккарда с учетом синонимических замен и стоповых слов. Тула: Известия ТулГУ, 2009. К статье
- Оценка алгоритмов сходства строковых переменных. Зеркальное регулярное выражение
