Эффективный метод обнаружения копий веб- документов с помощью обратного индекса (инвертный индекс)

Перевод статьи:
An efficient method to detect duplicates of Web documents with the use of inverted index

Оригинал статьи на английском находится по адресу: http://company.yandex.ru/articles/article7.html

Расширение сети Интернет ведет к появлению проблем внутри поисковых машин, так как изобилие копий веб документов выскакивающих по результатам поиска делают их работу менее значимой. Рекомендуется метод “описательных слов” для определения копий документов. Метод основан на выборе слов N из индекса для определения “подписи" документа и может применяться для любой поисковой машины, основанной на обратном индексировании. Этот метод можно сравнить с методом, основанном на "шинглах". С практически одинаковой точностью алгоритмов, этот метод более эффективен при обратном индексировании.


Развитие Интернета ведет к появлению проблем внутри поисковых машин, так как изобилие дубликатов веб документов выскакивающих по результатам поиска делают их работу менее значимой. Природа дубликатов достаточно широка. Один и тот же документ на одном и том же сервере может отличаться по техническим причинам – разный набор символов, форматы, присоединение рекламы или текущей даты. С другой стороны, одинаковые документы массово производятся серверами базы данных, например, сообщения на форумах, страница продукта на сайтах интернет- магазинов и т.д.
Проблема обнаружения близких дубликатов исследовалась в работах [1,2,4,5] различных исследовательских групп. Согласно эти работам решение данной проблемы может быть описано следующим образом. Изучите каждый документ, подсчитайте количество хэша (“отпечатки пальцев”) на каждом, частично совпаденном фрагменте документа (“шингл”), затем создайте образец полученного сета при помощи какого- либо критерия, и используйте этот сокращенный сет контрольной суммы (“скетч”) во всех последующих операциях. Фрагменты могут составлять предложения [2] или ряд битов [1], согласных [4], или слов [5]. Были предложены скетчи с постоянным и переменным размером: количество наименьших контрольных сумм и всех контрольных сумм, делящихся на некоторое целое число. В работе [3]предлагается метод выбора ряда слов, а также модель векторного пространства для попарного сравнения документов.
Метод “шинглов” уменьшает размер ряда для каждого документа и позволяет упростить групповые задачи. В то же время группирование документов остается достаточно тяжелым процессом, так как правила требуют отношения инверсии “документ- шингл”. Мы осуществляем цифровую подпись документа, которая, по нашему мнению, устойчива к небольшим изменениям документа, таким образом процедура группировки становится излишней. Все работающие на данный момент поисковые машины уже имеют базу данных всех слов, а также соответствующие идентификаторы документа. У мировой статистики есть в наличии подходящий выбор слов для точного и эффективного решения проблемы, в то время как метод “шинглов” является более сложным из –за огромного множество “шинглов”.
Постановка проблемы.

Давайте возьмем ряд документов. Документ представляет собой ряд слов. Соответственно мы имеем дело с лексической эквивалентностью. Мы предлагаем алгоритм, который строит “ряд дубликатов”. Правильность алгоритма может быть выражена на основе возможности наличия двух видов ошибок. Мы назовем “ошибкой альфа” такую ситуацию, при которой алгоритм не определил дупликата, и “ошибкой бетта” такую ситуацию, при которой алгоритм предложил неверный дубликат. Очевидно, что здесь два вида ошибки меняются местами, что говорит о тои, что нет идеального алгоритма.
Поэтому необходимо разделить задачу на две части: первая - создать “дубликатный ряд”, а вторя – его проверить.

Метод “описательных (дискриптивных) слов”

В самом начале необходимо выбрать какой- то ряд слов N, который мы назовем “дискриптивный ряд”; выбор слов мы обсудим позже.
Для каждого слова установим предельную частоту bi, и для каждого документа вычислим вектор, где векторный компонент I установлен на 1 если значение относительной частоты (повторяемости) слова I из дискриптивного ряда в этом документе больше чем выбранная предельная частота, в противном случае – 0. Этот двойной вектор считается нечеткой цифровой подписью документа. Каждый вектор однозначно определяет класс схожих документов. Поэтому его уникальный идентификатор может заменить соответствующий вектор. Далее мы не будеи рассматривать вектор с тремя и менее словами.
Сформулируем основные критерии выбора слов

1. Ряд слов должен охватывать максимально возможное количество документов.

2. “Качество” слова (о нем речь пойдет ниже) должно быть наивысшим

3. Количество слов в ряде должно быть минимальным

"Качество" слова можно выразить как относительную стабильность соответствующего компонента вектора по отношению к небольшим изменениям документа. Это означает, что "хорошее" слово I - слово с минимальной возможностью перехода (обозначим его ) за пороговое значение при небольших изменениях. Явно, что возможность изменения вектора для документа следующая
.
Выбранное нами пороговое значение bi должно удовлетворять следующим критериям: значение минимально при условии, что обе части (выше и ниже предела) не слишком малы. Это условие необходимо для гарантии того, что практически все документы имеют не нулевые векторы
Оптимальное число слов (N) в "дискриптивном ряде" мы установили экспериментально.

Эксперименты
Мы использовали нормированную дистанцию Левенштейна для определения сходства между двумя документами. Документы считаются эквивалентными если различия между ними не составляют более 8%. Эта цифра была получена при проведении эксперимента, при котором 6 экспертов сделали 300 утверждений о похожести документов: мы попросили экспертов сказать нам, какие пары документов являются идентичными с точки зрения пользователя поисковой машины. Тексты были предварительно позаимствованы из HTML-markup. Наша метрика в настоящее время не берет во внимание важность непарных слов – повторяемость слов, которая кажется важной в случаях с интернет- магазинами и другими документами, созданными базой данных.

Мы взяли 60 млн. документов у Yandex [6]. Затем мы создали группы дупикатов для “дискриптивных рядов” разных размеров и проверили все группы на “практическую эквивалентность” (8%), о чем говорилось выше. Размеры дискриптивных рядов колебались от 1600 до 3000 слов. Уменьшение размера "дискриптивного ряда" уменьшает ошибку- альфа и увеличивает ошибку-бетта. Количество "верно определенных" дупликатов прекратило расти, в тот момент, когда неправильные дубликаты оставались на низком уровне. Оптимальный размер ряда – 2000 слов.

В этой таблице мы сравнили наш метод с методом “шинглов”, используя тот же самый эксперимент. “Шинглы” высчитывались согласно [5] с 10 словами в шингле, , 48-Бт контрольной суммой, модулем 16, и порогом похожести 7/8 в ряде шинглов. .

Table 1. Сравнение метода описательных слов и метода “шинглов”.

(c) http://www.langinfo.ru/index.php?sect_id=2823