OrionXL

Алгоритм Шинглов. Поиск дубликатов текста

Роман Иванов @ 14:12 15.01.2010

Алгоритм шинглов (шингл (shingles) с английского это черепичка, чешуйка) предназначен для нечеткого поиска дубликатов текста. Слово "нечеткий" означает, то что вхождения дублей ищется не точно, а размыто. К примеру, возможен дубликат не только строки, но и отдельных словосочетаний. В основном модификация алгоритма шинглов используется поисковыми системами для борьбы с поисковым спамом. Это позволяет из поисковой выдачи исключать тексты похожие друг на друга или полностью идентичные. Однако остается проблема первоисточника, т.е. источника на котором данная информация появилась в первые. Хотя считается, что поисковые системы четко фиксируют этот факт, но в любой системе случаются сбои. Рассмотрим более детально вопрос относительно этого метода, посмотрим с чем едят этот шингл!

Алгоритм метода шинглов

Для каждой части текста (подстроки) рассчитывается некая контрольная сумма, задача которой как-то идентифицировать данный текст, это шингл. Эти символьные кусочки текста должны идти в нахлест, друг за другом, чтобы ни один символ или слово не пропало. Далее из всего множества этих контрольных сумм отбираются те, которые отвечают какому либо критерию - четные, делятся на какое-нибудь число и т.д. В результате выборка имеет равномерный закон распределения, не делается акцент на какой либо части текста. В итоге, если между двумя кодированными текстами совпадут контрольные суммы, то схожесть текстов очевидна. И чем больше совпадений, тем больше схожести текстов.

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

Контрольную сумму можно считать с помощью хеширования, используя, к примеру, алгоритм MD5.

Пример использования алгоритма метода шинглов

Рассмотрим в качестве примера две слегка измененные выдержки из стихотворения А.С. Пушкина :-)

Оригинальный текст:

"
Буря мглою небо кроет,
Вихри снежные кружа,
То как зверь она завоет,
То заплачет как дитя
- Алгоритм метода шинглов в работе
"

Чуть подправленный текст:

"
Буря белым землю кроет,
Вихри снежные кружа,
То как лев она завоет,
То заплачет как дитя
- Алгоритм метода шинглов на старт
"

В качестве шага выберем слово. Длину подстроки возьмем равную 5 словам. Составлять строки будем в стык (друг за другом). Так как текст маленький, то исключать слова
В итоге получим кодированный текст длиной в 5 чисел.

пример алгоритма шинглов

Рис. 1 Пример компоновки текста методом шинглов

Вот у нас получился набор слов для первого случая:
БурямглоюнебокроетВихри | снежныекружаТокакзверь | оназавоетТозаплачеткак | дитяАлгоритмметодашингловв | работе
хеш:
a7bdbcb13968a694f626a5682b7f2dfd | 0e5aa06baba90d7c851f9a0450a60222 | c0c522529b0e810f73b210cc972e9966 | 95ed3beeb9bc9ff61affd4421a24c44f | 9c793e2986f7ee89f93953e3fbcab408

и второго:
БурябелымземлюкроетВихри | снежныекружаТокаклев | оназавоетТозаплачеткак | дитяАлгоритмметодашингловна | старт
хеш:
de5790caa3ee48c73f62e49000121c6f | 11da4405827ce2d70015f98a10563e1c | c0c522529b0e810f73b210cc972e9966 | 7172b4096aa49236a2f7edd298a47de2 | 690e13e46c9738d430d90570888d428f

В результате, у нас получилось одно совпадение - третье число (c0c522529b0e810f73b210cc972e9966). Это совпадение показывает то, что между двумя текстами схожесть составляет не менее 25%. Конечно для такого маленького текста, можно было уменьшить шаг, но и при таких начальных параметрах это является хорошим примером.

Супершингл

Если для каждого текста составлять даже уменьшенное каким-либо критерием набор шинглов, то все равно для большого объема документов вычислительные мощности, которые необходимо будет задействовать все равно останутся колоссальными. Поэтому на практике часто над набором шинглов документа считают еще одну контрольную сумму, так называемый «супершингл». Следовательно, совпавшими тогда будут считаться документы с полностью совпавшими наборами шинглов.

Замечания алгоритма метода шинглов

Однако, необходимо отметить, что на текущий момент применяются усовершенствованные алгоритмы определения дубликатов. К примеру, альтернативный алгоритм определения нечетких дубликатов, был создан и придуман в Яндексе. Модифицированный алгоритм тот факт, что поисковая система обладают индексным документом в виде инвертированного файла (или инвертированным индексом) и эту ситуацию можно с пользой использовать в процедуре нахождения почти-дубликатов.

Простое приближение метода шинглов на php

Приведем ниже описание и исходный код, для демонстрации алгоритма шинглов на языке php. Будем имитировать поисковую систему :-)

Первоначально необходимо скачать файл по сети. Это можно сделать с помощью простой функции на php:

<?php
$test_text=file_get_contents($url); // получить файл по ссылке $url
?>

Далее необходимо очистить файл от лишних элементов. Для простоты удалим из текста лишние html теги. Удаление других элементов текста оставим читателю.

<?php
$text=strip_tags($test_text); // удалим теги с помощью функции php
?>

Определим необходимые переменные

<?php
$i=0;$j=0;
$hesh_word=array(); // массив слов
$hesh_string=array(); // массив подстрок
$hesh_mass=array(); // массив значений хеш подстрок
$tmp=»;
?>

Создадим массив из слов. В качестве критерия разделения используем пробел.

<?php
$hesh_word = explode(« », $text); // опять стандартная функция php
?>

Сформируем массив подстрок. В этой функции мы просто складываем слова по пять штук вместе.

<?php
foreach ($hesh_word as $word)
{
$tmp.=$word;
if($j==4)
{
$hesh_string[$i]=$tmp;
$i++;
$j=0;
$tmp="";
}else $j++;
};
$hesh_string[$i]=$tmp;
?>

Сформируем массив хеш значений:

<?php
$i=0;
foreach ($hesh_string as $string)
{
$hesh_mass[$i]=hash(«md5″,$string);
$i++;
};
?>

В качестве функции сравнения воспользуемся простым перебором :-) В результате работы функции выводится процент совпадений.

<?php
$similar_counter=0;
foreach ($hesh_mass1 as $var1)
{
foreach ($hesh_mass2 as $var2)
{
if($var1==$var2)
{
$similar_counter++;
break;
}
}
}
echo 'Процент совпадения: '.$similar_counter*100/size($hesh_mass1);
?>

Комментариев нет

Комментариев нет.

RSS-лента комментариев к этой записи.

Извините, обсуждение на данный момент закрыто.

алгоритмы, методы, программы - OrionXL