Эффективный способ обнаружения дубликатов web документов с использован...

Сергей Ильинский, Максим Кузьмин, Александр Мелков, Илья Сегалович "Эффективный способ обнаружения дубликатов web документов с использованием инвертированного индекса." Аннотация Развитие Интернета бросает вызов поисковым машинам, так как все больше и больше дубликатов web-документов являются результатами поиска, делая их менее важными для пользователя. Для решения этой проблемы был предложен метод "описательных слов" для выбора схожих документов. Он основан на выборе N слов из индекса для определения "подписи" документа и может быть использован в любом поисковике, основанном на инвертированном индексе. Он сравнивается с методом "каскада". С почти одинаковой точностью алгоритмов этот метод является более эффективным при использовании инвертированного индекса. Введение Развитие Интернета бросает вызов поисковым машинам, так как все больше и больше копий web-документов являются результатами поиска, делая их менее важными для пользователя. Происхождение копий довольно разнообразно. Один и тот же документ с одного и того же сервера может иметь различные варианты по техническим причинам - отличающиеся наборы знаков, форматы, а также размещение рекламы или текущей даты. С другой стороны, схожие документы создаются в огромных количествах серверами баз данных, например, сообщениями на форумах, описания продуктов в электронных магазинах и т.д. Проблема схожих документов исследовалась в работах [1,2,4,5] различных исследовательских групп. Предложенное решение может быть описано следующим образом. Отсканируйте каждый документ, вычислите значения хеш-функции ("отпечатки пальцев"), затем проверьте полученный результат с помощью подходящих критериев и используйте этот уменьшенный набор контрольных сумм ("схема") во всех последующих теоретико-множественных операциях. Фрагментами могут быть предложения [2], последовательность байтов [1], согласных [4] или слов [5]. Были предложены неизменные и переменные эскизы размеров: ряд самых маленьких контрольных сумм и все контрольные суммы, делимые каким-либо целым числом. В работе [3] был предложен метод выбора последовательности слов и улучшения модели векторного пространства для сравнения двуточечных документов. Метод "каскада" уменьшает размер множества для каждого документа и позволяет упростить выделение кластеров. В тоже время, кластеризация документов остается вычислительно сложной и, как правило, требует инвертирования соотношения документ-каскад. Мы создаем цифровую подпись документа, которая вероятностно неизменна при внесении изменений в документ, таким образом, кластеризация становится ненужной. Все имеющиеся в настоящее время поисковые машины уже имеют базу данных или "инвертированный индекс" всех слов и соответствующих идентификаторов документов. Типичная доступность мировой статистики слова предоставляет приемлемый выбор слов для точного и эффективного решения проблемы. Тогда как соответствующий подход с использованием каскада кажется более сложным из-за большого количества элементов множества каскада. Постановка задачи Рассмотрим множество документов. Документом считается последовательность слов. Следовательно, мы имеем дело только с лексической эквивалентностью. Мы предлагаем алгоритм, который составляет "множество копий". Точность алгоритма может быть выражена в терминах возможности двух типов ошибок. "Альфа-ошибкой" считается ситуация, когда алгоритм не определил копию, а "бета-ошибкой" - случай, когда алгоритм предложил неправильную копию. Очевидно, существует компромисс между двумя типами ошибок, поэтому, это не идеальный алгоритм. Следовательно, необходимо разделить нашу задачу на две части - первая состоит в создании "множества копий", а вторая - в проверке этого множества. Метод "описательных слов" Сначала необходимо выбрать некое множество слов N, которое мы назовем "описательным множеством"; выбор слов будет описан ниже. Для каждого слова давайте установим предельную частоту bi и для каждого документа подсчитаем вектор, где i-тый компонент вектора - единица, если величина относительной частоты i-того слова из "описательного множества" этого документа больше, чем выбранная предельная частота, в другом случае - ноль. Этот бинарный вектор считается нечеткой цифровой подписью документа. Каждый вектор однозначно определяет класс схожих документов. Следовательно, этот уникальный идентификатор может заменять соответствующий вектор. Вектора с 3 или менее словами выше пороговой величины в дальнейшем рассматриваться не будут. Сформулируем основной критерий выбора слов. 1. Множество слов должно покрывать максимально возможное количество документов. 2. "Качество" слова в смысле, описываемом ниже, должно быть самым лучшим. 3. Количество слов во множестве должно быть минимальным. "Качество" слова может быть определено как относительная стабильность соответствующего компонента вектора к небольшим изменениям документа. Это значит, что для "хорошего" слова i вероятность перехода (назовем его) пороговой величины минимальна в случае небольших изменений документа. Очевидно, что вероятность изменения вектора для документа является пороговая величина bi , которую мы выбираем, удовлетворяет следующему критерию - величина минимальна при условии, что обе доли (над и под пороговой величиной) не слишком мало. Это условие требуется, чтобы удостовериться, что почти все документы имеют ненулевые векторы. Оптимальное число слов (N) в "описательном множестве" мы определили экспериментальным путем. Опыты Мы использовали расстояние Левенштайна, чтобы определить схожесть двух документов. Документы были признаны практически одинаковыми, если разница между ними не превышает 8%. Эти данные были получены в результате опытов, во время которых 6 экспертов высказали 300 утверждений о схожести документов: мы попросили их указать, какие пары идентичны с точки зрения пользователя поисковой машиной. Предварительно из текстов убрали разметку в HTML-формате. В настоящее время наша метрика не принимает во внимание важность несогласованных слов, т.е. частотность слов, которая, как кажется, имеет значение в случае web-магазинов и других документов, созданных на основе баз данных. Мы взяли 60 миллионов документов-результатов поиска в Yandex [6]. Затем мы создали кластеры копий для разного размера "описательных множеств" и проверили каждый кластер на "фактическую эквивалентность" (8%) как описано выше. Размеры рассматриваемых множеств - от 1600 до 3000 слов. Уменьшение размера "описательного множества" снижает вероятность альфа-ошибки и увеличивает вероятность бета-ошибки. В какой-то момент количество "правильно определенных" копий перестало увеличиваться, в то время как количество ложных копий оставалось незначительным. Выбранное множество состояло из 2000 слов. Нижеприведенная таблица является сравнением нашего метода с методом "каскада" на одном и том же опыте. "Каскады" были подсчитаны согласно [5] по 10 слов в каскаде, контрольная сумма - 48 бит, коэффициент - 16, пороговая величина сходства - 7/8 множества каскада.

Метод	Количество предложенных копий	Разница < 8%	Разница < 15%	Разница < 30%	Время обработки данных
Метод "описательных множеств"	22 миллиона	61%	76%	91%	~1.5 часа
Метод "каскада"	19 миллионов	66%	80%	94%	~3.5 часа

Таблица 1. Сравнение метода описательных слов с методом "каскада" Заключение Алгоритм использует только инвертированный индекс, который доступен во многих поисковых машинах. Он является очень быстрым. Его очень легко заменить инкрементной версией, т.к. "размытая цифровая подпись" является признанной во всем мире характеристикой документа, и база данных не требует перекластеризации при каждом возрастающем просмотре. При практически одинаковой точности алгоритмов этот метод более эффективен при наличии инвертированного индекса. Ссылки 1. U. Manber. Finding similar files in a large file system. Proceedings of the 1994 USENIX Conference, pp. 1-10, January 1994. 2. S. Brin, J. Davis, H. Garcia-Molina. Copy Detection Mechanisms for Digital Documents. Proceedings of the ACM SIGMOD Annual Conference, San Francisco, CA, May 1995. 3. N. Shivakumar, H. Garcia-Molina. SCAM: A Copy Detection Mechanism for Digital Documents. Proceedings of the 2nd International Conference on Theory and Practice of Digital Libraries, Austin, Texas, 1995. 4. Nevin Heintze. Scalable Document Fingerprinting. Proceedings of the Second USENIX Workshop on Electronic Commerce, Oakland, California, November 18-21, 1996. 5. Andrei. Z. Broder, Steven. C. Glassman, and Mark. S. Manasse. Syntactic Clustering of the Web. In Proceedings of the Sixth World Wide Web Conference, 1997. 6. https://www.yandex.ru/ Оригинал документа: здесь Перевод: Лариса Шкредова (16.10.2004) Редактирование: Иван Севостьянов (ivan@webprojects.ru ) (18.10.2004)