Новости
09.05.2023
с Днём Победы!
07.03.2023
Поздравляем с Международным женским днем!
23.02.2023
Поздравляем с Днем защитника Отечества!
Оплата онлайн
При оплате онлайн будет
удержана комиссия 3,5-5,5%








Способ оплаты:

С банковской карты (3,5%)
Сбербанк онлайн (3,5%)
Со счета в Яндекс.Деньгах (5,5%)
Наличными через терминал (3,5%)

МЕТОДЫ ВЫЯВЛЕНИЯ ДУБЛИКАТОВ WEB-СТРАНИЦ

Авторы:
Город:
Москва
ВУЗ:
Дата:
18 декабря 2016г.

В настоящее время постоянно увеличивается количество информации в сети Интернет. Среди представленных в сети web-документов встречается немало дубликатов. При этом в результате поисковых запросов пользователь получает ссылки на страницы с идентичным или похожим содержимым. Сообщения, публикуемые одним источником, зачастую многократно перепечатываются другими – в исходном виде или с небольшими изменениями. В этом случае возникает необходимость фильтрации схожих ресурсов.

Проблема обнаружения нечетких дубликатов является одной из наиболее важных задач анализа web-данных и информационного поиска. Актуальность этой проблемы определяется широким практическим применением алгоритма выявления схожих текстовых документов: улучшение качества индекса и архивов поисковых систем за счет удаления избыточной информации; объединение новостных сообщений в сюжеты на основе сходства этих сообщений по содержанию; фильтрация спама (как почтового, так и поискового); установление нарушений авторских прав при незаконном копировании информации (проблема плагиата) и ряд других.

В зависимости от степени сходства различают точные (полные) и нечеткие (частичные) дубликаты. Точные дубликаты web-страниц обычно представляют собой одну и ту же страницу, которая имеет разную адресацию из-за ошибок программирования сайта. Нечеткими дубликатами  называют страницы, содержание которых различается незначительно: такое очень часто встречается в интернет-магазинах. К нечетким дубликатам относятся и различные версии страницы. Нечеткие дубликаты имеют незначительные отличия даже для визуального восприятия пользователя в виде перестановки блоков навигации, новостей или других элементов сайта.

Дубликаты страниц на сайте делают текст, размещенный на них неуникальным. К тому же снижается доверие к подобному web-ресурсу со стороны поисковых систем. В сети Интернет также встречается немалое количество дубликатов, нарушающих законные права их создателей на размещение исключительно на своих ресурсах.

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

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

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

Существующие специализированные средства поиска дубликатов web-страниц обычно используют метод шинглов, предложенный Андреем Бродером в 1997 году [1]. В данном методе документ представлялся в виде множества всевозможных подпоследовательностей фиксированной длины, состоящих из соседних слов. Такие последовательности были названы «шинглами». Два документа считались схожими, если множества их шинглов существенно пересекались.

Для каждого шингла вычисляются контрольные суммы с помощью статических хэш-функций. Поскольку число шинглов для каждого документа было примерно равно длине этого документа в словах, было предложено ограничиться 84 значениями [2]. Эти 84 шингла разбиваются на супершинглы: 6 групп по 14 шинглов в каждой. Затем каждый документ представляется всевозможными попарными сочетаниями из 6 супершинглов – всего 15 сочетаний, или мегашинглов. Два документа сходны по содержанию, если у них совпадает хотя бы один мегашингл.

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

Для решения данной проблемы был предложен другой популярный метод, основанный на использовании меры TF-IDF [3]. TF-IDF – статистическая мера, используемая для оценки важности слова в контексте документа, являющегося частью коллекции документов. Вес некоторого слова пропорционален количеству употребления этого слова в документе, и обратно пропорционален частоте употребления слова в других документах коллекции.

TF (term frequency) – отношение числа вхождения некоторого слова к общему количеству слов документа. Таким образом, оценивается важность слова t в пределах отдельного документа:


где nt – число вхождений слова t в документ d; length(d) – общее число слов в документе d.

IDF (inverse document frequency) – инверсия частоты, с которой некоторое слово встречается в документах коллекции. Учёт IDF уменьшает вес широкоупотребительных слов. Для каждого уникального слова t в пределах конкретной коллекции документов существует только одно значение IDF:

Для задачи выявления нечетких дубликатов с помощью меры TF-IDF вычисляются веса для каждого слова документа. После этого 6 слов с наибольшим значением веса сортируются в алфавитном порядке и сцепляются в строку. В качестве сигнатуры документа вычисляется контрольная сумма CRC32 полученной строки. Два документа считаются похожими, если у них совпадают сигнатуры.

Описанный выше метод способен выявлять дубликаты с небольшими изменениями, однако точность данного метода существенно ниже по сравнению с методом шинглов.

Принципиально другим подходом при выявлении схожих документов является использование векторной модели представления текста, предложенной впервые Джерардом Салтоном в 1994 году [4]. Идея данной модели заключается в представлении документа в виде вектора в n-мерном евклидовом пространстве, причем размерность документа определяется числом термов во всей коллекции документов:


Мера близости должна равняться единице в случае, если документы Xj и Xl – дубликаты, и стремиться к нулю, если Xj и Xl – взаимно уникальные ресурсы. Два документа Xj и Xl являются полными дубликатами, если мера их близости равна единице, и нечеткими дубликатами, если мера их близости превосходит экспериментально (или экспертно) установленный порог  
Алгоритм, основанный на векторном представлении текстов, учитывает недостатки сигнатурных методов и позволяет увеличить показатель полноты при сохранении максимально возможного показателя точности. Алгоритм выявления дубликатов web-страниц может быть использован в системах антиплагиата для проверки текстовых документов на наличие заимствований из открытых источников в сети Интернет. Алгоритм также может быть полезен при автоматической агрегации новостей.

 

 

Список литературы 

 

1. A. Broder, S. Glassman, M. Manasse and G. Zweig. Syntactic clustering of the Web. Proc. of the 6th International World Wide Web Conference, April 1997.

2. D. Fetterly, M. Manasse, M. Najork. A Large-Scale Study of the Evolution of Web Pages, WWW2003, May 20- 24, 2003, Budapest, Hungary.

3. S.-T. Park, D. Pennock, C. Lee Giles, R. Krovetz, Analysis of Lexical Signatures for Finding Lost or Related Documents, SIGIR’02, August 11-15, 2002, Tampere, Finland.

 4. G. Salton, J. Allan, and C. Buckley. Automatic structuring and retrieval of large text files. Communications of the ACM, 37(2), February 1994.