автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Разработка математического обеспечения оценки схожести WEB-документов на основе структурно-семантического разбиения

На правах рукописи

КОСИНОВ Дмитрий Иванович

РАЗРАБОТКА МАТЕМАТИЧЕСКОГО ОБЕСПЕЧЕНИЯ ОЦЕНКИ СХОЖЕСТИ WEB-ДОКУ МЕНТОВ НА ОСНОВЕ СТРУКТУРНО-СЕМАНТИЧЕСКОГО РАЗБИЕНИЯ

Специальность: 05.13.11 — Математическое и программное

обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Воронеж - 2008

003457407

Работа выполнена в ГОУ ВПО «Воронежский государственный университет»

Научный руководитель

кандидат физико-математических наук, доцент

Тюкачев Николай Аркадьевич

Официальные оппоненты: доктор технических наук, профессор

Матвеев Михаил Григорьевич;

кандидат технических наук, доцент Голуб Владимир Александрович

Ведущая организация

ГОУ ВПО «Воронежский государственный архитектурно-строительный университет»

Защита состоится 25 декабря 2008 г. в Ю00 часов на заседании диссертационного совета Д.212.037.01 ГОУ ВПО «Воронежский государственный технический университет» по адресу: 394026, г. Воронеж, Московский просп., 14.

С диссертацией можно ознакомиться в научной библиотеке ГОУ ВПО «Воронежский государственный технический университет».

Автореферат разослан «14 » ноября 2008 г.

Ученый секретарь диссертационного совета

Л,

^Аа

■о

Питолин В.М.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования. Экспоненциальный рост объемов информации, наблюдающийся в последние годы, обуславливает бурное развитие различных методов информационного поиска, под которым понимается выявление в некотором множестве документов, удовлетворяющих заранее определенному условию. Необходимость поиска нужной информации в гигантских массивах данных вызывает потребность в поисковых машинах, создание которых требует решения множества специфических задач.

Одной из таких задач является задача определения схожести различных угеЬ-документов между собой. Известно, что более 30% всего содержимого Интернета является дубликатами уже существующих страниц. Существует большое число методов, позволяющих с различной степенью уверенности детектировать схожие шеЬ-документы, однако их эффективность в условиях насыщенных различной информацией \veb-страниц современного Интернета позволяет желать лучшего. Кроме того, большинство реально действующих разработок носят коммерческий характер, в связи с чем принцип их работы авторами не раскрывается.

Выявление дубликатов позволяет решить следующие задачи:

• устранение повторяющихся документов в списках, выдаваемых поисковой машиной по запросу;

• сжатие данных, достигаемое путем кластеризации документов-дубликатов, позволяет значительно уменьшить размер массивов документов;

• распознавание массовых несанционированных рассылок электронной почты (спама), доля которых составляет более 90% всего потока электронной почты;

• нахождение похожих по содержанию документов, позволяющее в том числе находить цитирования и плагиат;

• автоматическая классификация документов, позволяющая упростить обработку больших массивов информации (например; ре-зультататов поиска).

Работа выполнена в рамках одного из основных научных направлений ГОУ ВПО «Воронежский государственный университет»: «Математическое моделирование, программное и информационное обеспечение, методы вычислительной и прикладной математики и их применение к фундаментальным исследованиям в естественных науках».

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

Для достижения поставленной цели необходимо решить следующие задачи:

1. Провести анализ современных методов обнаружения схожих текстов, их применения к области web-документов, выделить основные метрики подобия и метрики оценки эффективности.

2. Разработать математическую модель оценки сходства документов на уровне составляющих их блоков. Создать метод оценки схожести web-документов на основе их структурно-семантических блоков.

3. Разработать алгоритм выделения структурно-семантических блоков из web-доку ментов. Оценить эффективность алгоритмов создания устойчивых отпечатков документов на основе их локальных параметров.

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

Методы исследования. Методы исследования основаны на использовании аппарата теории графов, нечетких множеств, теории вероятностей и математической статистики, объектно-ориентированного программ ирования.

Научная новизна результатов исследования. В работе получены следующие результаты, характеризующиеся научной новизной:

• математическая модель для оценки схожести документов, отличающаяся наличием промежуточного звена в цепи «документ-блок-отпечаток» и позволяющая определять пересечения текста документов на уровне их блоков;

• метод оценки сходства web-документов, позволяющий улучшить качество распознавания схожих документов за счет учета параметров составляющих их структурно-семантических блоков;

• алгоритм разделения web-документа на структурно-семантические блоки, отличающийся использованием иерархической структу-

ры web-документа и позволяющий определять семантические сегменты документа на ее основе;

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

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

Разработанный алгоритм выделения структурно-семантических блоков из web-документов позволяет разделять страницы на логические сегменты, предоставляя возможность их отдельной обработки.

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

Исследование поддержано исследовательским грантом компании Яндекс в рамках конкурса «Интернет-Математика 2007»1.

Апробация работы. Основные результаты диссертационного исследования докладывались на VIII Международной конференции «Информатика: проблемы, методология, технологии» (Воронеж, 2008), VII Международной научно-технической конференции «Кибернетика и высокие технологии XXI века» (Воронеж, 2006), IV Международной научно-практической конференции «Прогрессивные технологии развития» (Тамбов, 2007), научно-технических конференциях профессорско-преподавательского состава, сотрудников, аспирантов и студентов ГОУ ВПО «Воронежский государственный университет» (2006-2008).

Публикации. По материалам диссертации опубликовано 11 научных работ, в том числе 1 - в издании, рекомендованном ВАК РФ.

В работах, опубликованных в соавторстве и приведенных в конце автореферата, лично соискателю принадлежат: алгоритм выделения логических блоков из web-страницы [1], классификация web-страниц на основе нечетких параметров [8], процедура выбора набора признаков,

1 http: / / company.yandex.ry/grant

определяющих документ [9J, экспериментальная оценка возможности применения данных о классе структурированности документа в задаче поиска подобных [10], адаптация классификационного генетического алгоритма к задаче выделения признаков [11].

Структура и объём работы. Диссертационная работа состоит из введения, четырех глав и заключения, списка литературы из 85 наименований и 7 приложений. Работа изложена па 146 страницах, включает 3 таблицы и 30 рисунков.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы диссертации, сформулированы цели и задачи исследования, приведено краткое содержание каждого раздела, представлены основные научные результаты, выносимые на защиту, и обоснована их новизна.

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

В работе показано, что оценка качества работы поисковых систем и методов оценки подобия текстовых документов осложняется субъективным характером выражений «релевантность» и «почти-дубликат». Указывается, что периодически в экспертных оценках релевантности документов наблюдается очень существенные различия: измеренные между экспертами точность и полнота составляют около 65%.

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

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

Во второй главе описывается решение задачи выявления схожести web-документов на основе использования информации о схожести их блоков.

Процедура определения схожести является трехэтагшой: разбиение документов на блоки, создание отпечатков блоков, поиск схожих

документов на основе совпадения отпечатков. Общая схема, отражащая процесс оценки схожести, приведена на рис. 1.

Web-документы d eD

i Алгоритм создания локальных отпечатков

Отпечатки ssS

Коэффициент Да^са

Нечеткие множества схожести для документов

Метрика схожести документов

Рис. 1. Процесс оценки схожести web-документов на основе блоков

Первый этап подразумевает преобразование исходного web-документа Д„ в множество блоков Ви, посредством функции /ь.

fb:Dw -> В», Bw = {61,62, Ъп}, п > 0. (1)

Информационной структурой /, на которую отображается документ Dw, является упорядоченная последовательность знаков конечной длины I, представленная в виде строки. Информационным содержанием If является текстовое содержимое web-документа, непосредственно отображаемое браузером на экране (далее называемое контентом).

Используя определенную стандартом Document Object Model возможность представления web-документов в виде дерева, информационная структура документа I взаимнооднозначно отображается на граф Т = (S,U), где S = {s} - множество узлов, U — {и} - множество соединяющих узлы дуг. Таким образом DOM-дерево представляется в виде ациклического графа, имеющего множество уровней S = {S^S1, ...,SN~l,SN\ с корнем в узле Sf. Каждый уровень содержит упорядоченное множество узлов 5'n = {S£}. Каждому узлу дерева 5" (п < Лг) поставлена в соответствие информационная структура I(S").

В работе предложен метод разбиения web-доку ментов на блоки, который заключается в последовательном выделении поддеревьев ис-

ходного дерева Т, опираясь на значения определенной весовой функции узла, состоящий из следующих шагов:

1. Обработка web-документа Dw и формирование графа Т =

(SM).

2. Удаление не оказывающих влияния на информационное содержание узлов, то есть узлов |//(s)| = 0, где s € S.

3. Расчет значения весовой функции W(s) для каждого узла s €

S.

4. Выделение блока b во множество Bw путем вырезания поддерева T(s) с корнем в узле s, имеющим максимальное значение весовой функции Max{W(s)).

5. В случае, если информационное содержание оставшихся узлов графа \If{T)\ > 0, возврат к шагу 3.

В ходе ряда экспериментов было выяснено, что основная часть контента (значимового текстового содержимого) web-страниц содержится, как правило, на нижних уровнях DOM-дерева. Учитывая обусловленные стандартом HTML, а также сложившиеся исторически особенности построения web-страниц, можно утверждать, что находящиеся на нижних уровнях элементы текста, структурированные исходя из логики построения HTML-иерархии, могут служить хорошим приближением к исходно требуемым семантическим фрагментам web-документа.

Таким образом, возникает задача построения весовой функции узла s графа Т, адекватно отражающей величину информационного содержания поддерева узла s в соответствии с глубиной дерева N.

Преположим, что вес W узла s прямо пропорционален длине контента поддерева этого узла T(s), уровню тг и обратно пропорционален длине контента поддерева родительского для s узла sp.

Исходя из этих соображений и после проведения ряда экспериментальный проверок, весовая функция узла U'(.s) была определена следующим образом:

= ¿ * bg(¿ * ki)\og(d * к2 + кз)

p + ki ' U

где I = L(Ij{T(s))) - длина контента поддерева с корнем в s, р = L(If(T(sp))) - длина контента поддерева с корнем в sp, d £ [1, Ar¡ -глубина узла (уровень вложенности), /ci_4 - коэффициенты.

После выделения блоков документа Dw во множество Вш необходимо оценить степень схожести контента If блоков между собой, построив функцию Sim(bi,bj).

Формально методы оценки сходства объектов на основе отпечатков отображают множество объектов П посредством функции создания отпечатка /5 в пространство Як, где /с - длина отпечатка: /3 : Я —> я = {0.1 При этом для пары объектов А и В выполняется условие /а(А) ± МВ) =>А£В.

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

с (и и\ ^ ПЯ,-! „ч

5гт(6г'^) = |5Шя] (3)

Блоки будут считаться дубликатами, если численное выражение их схожести выше некого порога рь € [0,1]: 5'ггп(Ьг, Ь3) > рь-

Получив метрику схожести пары блоков, можно определить матрицу попарной схожести блоков:

А/ = [т0-], = 5г?п(Ьг, Ь3), г,] € [1, |В|] (4)

Схожесть шеЬ-документов можно описать через схожесть их блоков путем введения нечеткого подмножества Ъг множества В, определяемого как множество упорядоченных пар {(Ь, ць< (Ь))}-УЬ € В.

Функция принадлежности (Ь) описывается как степень схожести пары блоков (6^,6).

= £гт(Ьг,Ь),Ь 6 В (5)

Определив нечеткое подмножество для всех блоков Ъ € В, г < |В|, объединение всех нечетких подмножеств блоков каждого документа описывается как:

\в\

ИЬ (Ь) = и (Ь), ы е Ва, ,г< \Э\ (6)

3 = 1

Полученный набор нечетких множеств ¿г^ (6) отражает совокупную информацию о схожести имеющихся в каждом документе с? 6 О блоков Ь е В^. Степень равенства двух нечетких множеств (1г, ¿} определяется через операцию эквивалентности

А «-» В = МШ{МАХ{\ - А..В),МАХ{ 1 - В, А)) (7)

выражением следующего вида:

5гт(сгг,^) = Р) (щЛЬ) +-+ цсгД&)) ьев

Выражение (8) может использоваться в качестве метрики блочной схожести - оно выдает значение в интервале [0, 1] и в целом отражает степень совпадения блоков документов.

Таблица 1

Таблица сопряженности

истинные пары ложные пары

найденные пары а Ь

не найденные пары с й

Для определения эффективности разработанного метода определения схожести \уеЬ-документов на уровне составляющих их блоков осуществляется оценка показателей качества обнаружения. Стандартным подходом для оценки эффективности методов определения схожести документов является разбиение выборки на четыре непересекающихся множества и представление в виде таблицы сопряженности размером 2x2.

В качестве метрик оценки качества использовались стандартные для подобных задач метрики точности Р, полноты Я и Ф-меры Г как гармонического среднего полноты и точности:

Р =

а + Ь

К

а

а + с

2РЯ Р + К

(9)

В качестве критерия проверки значимости связи между идеальной и полученной экспериментально выборками использовался хи-квадрат Пирсона.

В третьей главе рассматриваются разработанные алгоритмы, необходимые для использования метода оценки схожести документов на уровне блоков.

Вводится понятие структурно-семантического блока - по возможности логически и семантически целостного сегмента \¥еЬ-страницы, построенного с точки зрения и с использованием ее иерархической структуры.

Задача выделения блоков со значащей информацией является разновидностью задач анализа структуры НТМЬ-страниц и соотносится со многими другими задачами - от создания аннотаций к документам до отслеживания изменений.

Алгоритм выделения блоков (рис. 2) разработан на основе метода выделения блоков, описанного выше. Результатом выполнения алгоритма является набор выделенных из заданной шеЬ-страницы структурно-семантических блоков.

Весовая функция (2) строилась из вышеописанных соображений. Подбор коэффициентов осуществлялся с использованием генетических алгоритмов (см. табл. 2). На рис. 3, 4 приведены процесс работы и результаты работы алгоритма.

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

Таблица 2

Значения коэффициентов для различного числа блоков

Число блоков к! к2 к.з /Ипезэ югопд

2-4 0,21 1,08 7,80 1 0,88 5

3-7 0,15 1,93 4,07 1 0,89 4

8-12 0,50 1,94 0,26 1 0,49 11

Поскольку наличие нескольких блоков у каждого документа само по себе подразумевает множественность получаемых отпечатков до-

Формирование ООМ-дереба из НТМ1_-страницы

Фильтрация узлов дерева

Расчет весов узлов дерева

Поиск узла л | с максимальным \

весом !

I

Выделение блока (поддерева с корнем в п)

Остался ли контент? -

.1...

КОНЕЦ

Рис. 2. Укрупненная схема алгоритма выделения блоков

<ВС0¥>0*2 1-1351 V» =7.69 - <ТД81£> 0*31.« 1351

- ; ТР 0-4 I- 3" Л'-0. 15 ^

- <1051 0=51=11 ¥У=1.2'

- <:А > I* I * V;

Университет

- <Т0> 0-51=11 Л'-1.2'

- <А> 0=61-11 ,66

Образование

- сТОэ О«51»5У/=0,3$

- <А> 0-61-5

Наука

- <Г0> 0*51=1 ОЙ» =1.1»

-

Сообщество

- «гТР> 0«Н 1«1255 ША

> < ТО^ 0-51.-60 V/—Э.34'

- < то > 0=51= 1049 у;= 10.1

♦ • <Т А31.Е > 0=6 I-1049 V/- \ 3.5 + <Т0>0~51=1"6 '«7=1 26 + ;ТК> 0=4 1=20 #-0.07 + |-ЛЙ> 0=41=9^—3 02

-у;•>_С;-:^»;-*;

СУ^-У/ * ■СЛ'Ч

Со.

Рис. 3. Процесс работы алгоритма выделения блоков

Рис. 4. Результат работы алгоритма выделения блоков

i кумента, дополнительно изучена возможность применения локальных j параметров текста для создания устойчивых отпечатков текстов в усло-' виях единственности отпечатка на каждый текст. Проведен сравнительный анализ ряда разработанных алгоритмов, основанных на использовании локальных свойств текстов. В частности, затронуты следующие параметры: количество спецсимволов в тексте документа, длины (абсолютные и усредненные) различных элементов текста, наборы высоко- и низкочастотных термов.

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

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

Пользовательский интерфейс

Модуль работы с тест, коллекциями

Расчет схожести

Работа со страницами

Модуль работы со страницами

Разбиение на блоки

Работа с блоками

i * к *

Библиотека SimMetrics Библиотека HTMLParcer Библиотека JGAP > Библиотека i JFormula

Рис. 5. Структурная схема разработанного программного модуля

Рис. б. Общий вид окна выделения блоков из web-документов

Программный модуль позволяет решать широкий спектр задач, связанных с поиском схожих документов и разбиением страниц на блоки. Структурная схема приложения приведена на рис. 5. Разработанное в итоге приложение обладает графическим пользовательским интерфейсом (рис. 6, 7), выполняет функции вычислительного решения задачи, а также обладает функциями импорта исходных данных и вывода результатов решения. Для проведения тестирования работы приложения и оценки качества получаемых результатов был разработан и реализован план тестирования приложения.

Используя описанное приложение, была произведена экспериментальная проверка метода оценки схожести здйЬ-документов на уровне составляющих их блоков. В качестве тестовой коллекции использовался набор из 2000 web-страниц домена Narod.ru. Перед проведением экспериментальной проверки были получены пары документов, коэффициент сходства которых после удаления тегов составлял не менее 50%.

Параметры разбиения web-документов на блоки там, где таковое разбиение применялось; коэффициенты весовой функции проставлялись с учетом желаемого количества в 3-7 блоков tía страниц, число

[

Рис. 7. Общий вид окна поиска схожих \\геЬ-документов

цщнглов на блок пропорционально отношению длины блока к общей длине документа, но не менее одного на блок и не более 10 на весь документ.

На первом этапе изучался эффект, полученный в результате разбиения на блоки, при использовании точного хеша документа.. Было проведено два тестовых пробега: « МБ5» - получение точного МБ5-хеш§ от текста документа, «Блоки + МВ5» - получение точного МО5-хеша от текстов блоков, на которые был разбит документ. Эксперименты показали серьезное (около 30%) увеличение показателя полноты за счет незначительного снижения точности распознавания {рис. 8).

На втором этапе изучалось влияние применения поблочного создания отпечатков на эффективность двух алгоритмов: алгоритм шин-глирования и алгоритм «Спецсимволы». Было проведено четыре тестовых пробега (рис. 9).

Применение к алгоритму «Спецсимволы» предварительного разбиения на блоки вызвало увеличение Ф-меры модифицированного ал го-ритма на порогах 80%-95% примерно на 17%; что является весьма существенной прибавкой к качеству распознавания. Учитывая, что наиболее

Рис. 8. Графики зависимости точности, полноты и Ф-меры от величины порога для первого этапа

интересной является величина порога в 90%, поскольку она примерно соответствует человеческой оценке «дубликат»/«не дубликат», показатель Ф-меры на этом пороге в 80% можно считать достаточно высоким. В применении разбиения на блоки к методу шинглирования отмечено незначительное (в пределах 3-5%) ухудшение показателей для модифицированного разбиением на блоки алгоритма. На порогах от 85% и менее показатель Ф-меры у этого алгоритма начинает превышать оригинальный на 5-10%. Детальный анализ показал, что число пересечений множеств шинглов различных страниц в модифицированном алгоритме увеличилось на 11%. Значительная часть этого прироста обусловлена совпадением навигационных частей страниц, уверенно выделяемых в процессе разбиения страниц на блоки. Отдельное шинглирование этих идентичных блоков дало совпадения их шинглов более чем для 95% страниц.

Таким образом, было отмечено увеличение качества распознавания схожих \уеЬ-документов при использовании предварительного разбиения их на структурно-семантические блоки. Показана высокая эффективность структурно-семантического разбиения в плане выделения навигационной части страниц, поскольку подобные навигационные блоки практически всегда выделяются разработчиками страниц в отдельную структурную единицу БОМ-дерева.

1,00 0,95 0,90 0,85 1,00 0,95 0,90 0,85 1.00 0,95 0,90 0,85

Порог Порог Порог

""^"•"Спецсимволы ~О— Блоки + Спецсимволы И Шинглы —О— Блоки + Шинглы

- Рис. 9. Графики зависимости точности, полноты и Ф-меры от величины порога для второго этапа

В заключении сформулированы научные и практические результаты диссертационного исследования.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

Проведенные в рамках диссертации исследования позволили получить следующие результаты, имеющие практическое и научное значение: '

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

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

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

4. Спроектирована структура и реализовано программное обеспечение, реализующее предложенные в работе метод оценки схожести

web-документов на уровне содержащихся в них блоков и алгоритм выделения структурно-семантических блоков web-документов.

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

Основные результаты диссертационного исследования опубликованы в следующих работах:

Публикации в изданиях, рекомендованных ВАК РФ

1. Косинов Д.И., Тюкачев H.A. Выделение логических блоков из web-страниц // Вестник Воронежского государственного технического университета. - 2008. Т. 4. № 4. - С. 97-101.

Статьи и материалы конференций

2. Косинов Д.И. Методы формирования информационных запросов к поисковой системе // Современные проблемы прикладной математики и математического моделирования: материалы конф. — Воронеж: ВГТА, 2005. - С. 123.

3. Косинов Д.И. Особенности поиска обсуждений в информационно-поисковых системах // Информатика: проблемы, методология, технологии : материалы VI Регион, науч.-метод. конф. Воронеж: ВГУ,

2006.- С. 203-206.

4. Косинов Д.И. Эффективные методы выявления документов-дубликатов // Кибернетика и высокие технологии 21 века : VII Меж-дунар. науч.-техн. конф. Воронеж, 2006. Т. 2. — С. 686-690.

5. Косинов Д.И. Использование статистической информации при выявлении схожих документов // Интернет-математика 2007: сб. работ участников конкурса науч. проектов по информ. поиску. — Екатеринбург, 2007. - С. 84-90.

6. Косинов Д.И. Некоторые методы уточнения сходства документов в интернет-поиске // Информатика: проблемы, методология, технологии : материалы VII Регион, науч.-метод. конф. Воронеж: ВГУ,

2007.- С. 205-207.

I 7. Косинов Д.И. Локальные параметры текстов и проблема опре-

I деления почти-дубликатов // Вестник Воронежского государственно-1 го университета. Сер. Системный анализ и информационные технологии.- 2008. Т. 1,- С. 83-85.

8. Косинов Д.И., Апрелов Б.А. Модификация алгоритмов детектирования схожих документов с помощью аппарата нечетких множеств // Прогрессивные технологии развития: сб. материалов IV Междунар. науч.-практ. конф, Тамбов: Издательство ТАМБОВ-ПРИНТ, 2007.- С. 147-148.

9. Косинов Д.И., Апрелов Б.А. Применение методов отбора признаков при решении задачи классификации документов // Современные проблемы прикладной математики и математического моделирования : материалы II Междунар. науч. конф. — Воронеж, 2007. — С. 17-18.

10. Косинов Д.И., Апрелов Б.А. Использование информации о классе документа в задаче поиска подобных // Информатика : проблемы, методология, технологии : материалы VIII Междунар. науч.-метод. конф. - Воронеж, 2008. Т. 1,- С. 288-291.

11. Косинов Д.И., Апрелов Б.А. Оптимизация алгоритма решения задачи выделения характеристик документов с использованием классификационного генетического алгоритма // Информатика: проблемы, методология, технологии : материалы VIII Междунар. науч.-метод. конф. - Воронеж, 2008. Т. 1.- С. 11-13.

Подписано в печать 20.11.2008. Формат 60x84/16. Бумага для множительных аппаратов. Усл. печ. л. 1,0. Тираж 90 экз. Заказ Воо. ГОУ ВПО «Воронежский государственный технический университет» 394026 Воронеж, Московский просп., 14

Введение

Глава 1. Проблема обнаружения схожих документов

1.1. Задача распознавания схожих документов

1.2. Определение понятия схожих документов

1.3. Источники схожих документов в Интернете

1.4. Основные метрики подобия документов.

1.5. Методы обнаружения схожих документов

1.6. Методы кластеризации

1.7. Предварительная обработка документа.

1.8. Постановка задачи.

Глава 2. Моделирование системы оценки схожести документов на уровне блоков.

2.1. Модель представления web-документа

2.2. Метод выделения блоков из web-документа

2.3. Метод оценки схожести блоков.

2.4. Подходы к формализации нечеткости знаний о схожести документов

2.5. Метод оценки схожести web-доку ментов

2.6. Выводы.

Глава 3. Алгоритмизация процедуры оценки схожести web-документов на уровне блоков

3.1. Алгоритмы разбиения web-страниц на блоки.

3.2. Алгоритмы создания единого отпечатка на основе локальных параметров документа

3.3. Выводы.

Глава 4. Программная реализация метода оценки схожести \veb-документов.

4.1. Структура программного обеспечения

4.2. Программная платформа.

4.3. Программная реализация.

4.4. Графический интерфейс

4.5. Последовательность работы с программой

4.6. Тестирование программы.

4.7. Результаты практической апробации метода оценки схожести шеЬ-доку ментов на уровне составляющих их блоков.

4.8. Выводы.

Актуальность работы. Экспоненциальный рост объемов информации, наблюдающийся в последние годы, обуславливает бурное развитие различных методов информационного поиска, под которым понимается выявление в некотором множестве документов, удовлетворяющих заранее определенному условию поиска. Необходимость поиска нужной информации в гигантских массивах данных вызывает потребность в поисковых машинах, создание которых требует решения множества специфических задач.

Одной из таких задач является задача определения схожести различных -^еЬ-документов между собой. Известно, что более 30% всего содержимого Интернета является дубликатами уже существующих страниц. Выявление дубликатов позволяет решить следующие задачи:

• устранение повторяющихся документов в списках, выдаваемых поисковой машиной по запросу. В базах данных крупнейших поисковых машин имеется значительное количество записей-дубликатов. Успешное определение дубля документа, уже имеющегося в базе, позволяет сэкономить место и улучшить качество поиска;

• сжатие данных, достигаемое путем кластеризации документов-дубликатов, позволяет значительно уменьшить размер массивов документов. Применение подобной техники к индексу поисковой машины позволяет исключить до 30% документов, и как следствие, увеличить скорость работы с данным индексом;

• распознавание массовых несанционированных рассылок электронной почты (спама), доля которых составляет более 90% всего потока электронной почты. Детектирование схожих документов, которыми являются подобные рассылки, позволяет эффективно находить и уничтожать огромные объемы нежелательной корреспонденции;

• автоматическая классификация. При условии качественной классификации документов возникает возможность более простой навигации по большим массивам документов (например, по результатам поиска), а также потенциал для оптимизации pá6oTbi с непредсказуемыми по содержимому информационными потоками;

• нахождение похожих по содержанию документов. Функция нахождения по запросу документов, подобных заданному, позволяет определять их версионность, а также обнаруживать цитирования и плагиат.

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

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

Для достижения цели работы необходимо решение следующих1 задач исследования:

1. Провести анализ современных методов обнаружения схожих текстов, их применения к области web-документов, выделить основные метрики подобия и метрики оценки эффективности.

2. Разработать математическую модель оценки сходства документов на уровне составляющих их блоков. Создать метод оценки схожести web-документов на основе их структурно-семантических блоков.

3. Разработать алгоритм выделения структурно-семантических блоков из web-документов. Оценить эффективность алгоритмов создания устойчивых отпечатков документов на основе их локальных параметров.

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

Методы исследования. Методы исследования основаны на использовании аппарата теории графов, нечетких множеств, теории вероятностей и математической статистики, объектно-ориентированного программирования.

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

• математическая модель для оценки схожести документов, отличающаяся наличием промежуточного звена в цепи «документ-блок-отпечаток» и позволяющая определять пересечения текста документов на уровне их блоков;

• метод оценки сходства web-доку ментов, позволяющий улучшить качество распознавания схожих документов за счет учета параметров составляющих их структурно-семантических блоков;

• алгоритм разделения web-документа на структурно-семантические блоки, отличающийся использованием иерархической структуры web-документа и позволяющий определять семантические сегменты документа на ее основе;

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

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

Разработанный алгоритм выделения структурно-семантических блоков из web-документов позволяет выделять логические сегменты страницы, предоставляя возможность их отдельной обработки.

Рекомендации по построению локальных отпечатков документов позволяют улучшить качество распознавания схожих дубликатов в уже имеющихся системах.

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

Полученные в диссертации результаты дают основу для дальнейших теоретических и практических работ в области определения схожести документов на уровне блоков и создания отпечатков на основе локальных параметров документов.

Исследование поддержано исследовательским грантом компании Яндекс в рамках конкурса «Интернет-Математика 2007»1.

Апробация работы. Основные результаты диссертационного исследования докладывались на VIII международной конференции «Информатика: проблемы, методология, технологии» (Воронеж, 2008), VII международной научно-технической конференции «Кибернетика и высокие технологии XXI века» (Воронеж, 2006), IV международной научно-практической конференции «Прогрессивные технологии развития» (Тамбов, 2007), научно-технических конференциях профессорско-преподавательского состава, сотрудников, аспирантов и студентов ГОУ ВПО «Воронежский государственный университет» (2006-2008).

Публикации. По материалам диссертации опубликовано 11 научных работ, в том числе 1 в изданиях, рекомендованных ВАК РФ.

В работах, опубликованных в соавторстве, лично соискателю принадлежат: классификация web-страниц на основе нечетких параметров [19], процедура выбора набора признаков, определяющих документ [20], экспериментальная оценка возможности применения данных о классе структурированности документа в задаче поиска подобных [21], адаптация классификацион

1http://company.yandex.ry/grant ного генетического алгоритма к задаче выделения признаков [22], алгоритм выделения логических блоков из web-страницы [23].

Структура и объем диссертации. Диссертационная работа изложена на 146 страницах, включает 3 таблицы и 29 рисунков. Состоит из введения, четырех глав и заключения, списка литературы из 85 наименований и 7 приложений.

4.8. Выводы

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

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

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

Заключение

Проведенные в рамках диссертации теоретические исследования позволили получить следующие результаты, имеющие практическое и научное значение:

1. Предложена модель, позволяющая оценивать схожесть документов, используя информацию о схожести их блоков, что позволяет проводить более глубокий анализ подобия.

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

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

4. Проведен сравнительный анализ ряда алгоритмов создания устойчивых отпечатков документов на основе их локальных параметров, даны рекомендации по использованию этих алгоритмов.

5. Спроектирована структура программного обеспечения, реализующего предложенные в работе метод оценки схожести web-документов на уровне содержащихся в них блоков и алгоритм выделения структурно-семантических блоков web-доку ментов.

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

1. Агеев М., Куралепок И., Некрестьянов И. Официальные метрики ромип 2006. — 2006.http://romip.narod.ru/romip2006/appendixametrics. pdf.

2. Агеев M., Вершинников И., Доброе Б. Извлечение значимой информации из web-страниц для задач информационного поиска // Материалы конференции Интернет-Математика 2005. — 2005.

3. Бодякин В. И., Чистяков А. А. Ассоциативные информационные структуры и модели памяти. — 2004.

4. Боровков А. А. Математическая статистика. — М.: Наука, 1984. — С. 472.

5. Вятченин Д. А. Нечеткие методы автоматической классификации.— УП Технопринт, 2004.

6. Гаршин Д. Моделирование и выбор оптимальных технологических цепочек на базе территориально-распределенных производственных систем // дисс. к.т.н. — 2007.

7. Губин М. Модели и методы представления текстового документа в системах информационного поиска // дисс. к.ф.-м.н. — 2005.

8. Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования. — М.: Физматлит, 2003.— С. 432.

9. Зеленков Ю., Сегалович И. Сравнительный анализ методов определения нечетких дубликатов для web-документов // Труды 9ой Всероссийской научной конференции Электронные библиотеки: перспективные методы и технологии, электронные коллекции. — 2007.

10. Кириченко К., Герасимов М. Обзор методов кластеризации текстовых документов // Материалы международной конференции Диалог2001. — 2001. http://www.dialog-21.ru/Archive/2001/volume2/226.htm.

11. Кнут Д. Искусство программирования, том 1. Основные алгоритмы.— Вильяме, 2006.

12. Косинов Д. Методы формирования информационных запросов к поисковой системе // Современные проблемы прикладной математики и математического моделирования: Материалы конференции. — Воронеж: ВГ-ТА, 2005. С. 123.

13. Косинов Д. Особенности поиска обсуждений в информационно-поисковых системах // Информатика: проблемы, методология, технологии : материалы 6-ой регион, науч.-метод. конф.— Воронеж: ВГУ, 2006. С. 203-206.

14. Косинов Д. Эффективные методы выявления документов-дубликатов // Кибернетика и высокие технологии 21 века : 7 Международ, науч.-техн. конф., 16-18 мая 2006 г. Т. 2. - Воронеж: 2006. - С. 686-690.

15. Косинов Д. Использование статистической информации при выявлении схожих документов // Интернет-математика 2007: сб. работ участников конкурса науч. проектов по информ. поиску.— Екатеринбург: 2007.— С. 84-90.

16. Косинов Д. Некоторые методы уточнения сходства документов в интернет-поиске // Информатика: проблемы, методология, технологии : материалы 7-ой регион, науч.-метод. конф., 8-9 февр. 2007 г. — Воронеж: ВГУ, 2007. С. 205-207.

17. Косинов Д. Локальные параметры текстов и проблема определения почти-дубликатов // Вестник Воронежского государственного университета. Серия: Системный анализ и информационные технологии. — Т. 1. — 2008. С. 83-85.

18. Косипов Д., Тюкачев Н. Выделение логических блоков из web-страниц // Вестник Воронежского государственного технического университета. 2008. - Т. 4, № 4. - С. 97-101.

19. Левенштейн В. Двоичные коды с исправлением выпадений, вставок и замещений символов // Доклады Академий Наук СССР 163.4:845-848. — 1965.

20. Леоненков А. В. Нечеткое моделирование в среде MATLAB и fuzzyTECH.- Спб.: БХВ-Петербург, 2005.

21. Мелихов А. Н., Верштейн Л. С., Коровин С. Я. Ситуационные советующие системы с нечеткой логикой. — М.: Наука Физматлит, 1990.

22. Митюшкин Ю. ИМокин Б, И., Ротштейн A. Soft Computing: идентификация закономерностей нечёткими базами знаний. — Винница: УШВЕРСУМ-Вшниця, 2002.

23. Некрестьянов И. Тематико-ориентированные методы информационного поиска // дисс. к.т.н,— 2000.

24. Некрестъянов И., Павлова Е. Обнаружение структурного подобия html-документов // Труды четвертой всероссийской конференция RCDL'2002, том 2, стр. 38-54, Дубна, Россия, 2002. — 2002.

25. Непомнящий П., Юрин Д. Построение иерархического дерева детальности изображения через поиск минимальных разрезов графа // Труды 13-ой Международной Конференции по Графике и Компьютерному Зрению. — 2003.

26. Нечеткие гибридные системы. Теория и практика / И. 3. Батырщин, А. О. Недосекин, А. А. Стецко и др. — М.: Физматлит, 2007. — С. 208.

27. Обзор автоматических детекторов плагиата в программах / Ю. Лифшиц, Д. Антипов, О. Ефтифеева и др. — 2006. http://detector.spb.su/pub/ Sandbox/ReviewAlgorithms/survey.pdf.

28. Сабанин В. Р., Смирнов Н. И., Репин А. И. Модифицированный генетический алгоритм для задач оптимизации в управлении // Exponenta Pro. Математика в прилоэюениях. — 2004. — № 3-4.

29. Солодухин А. Классификация текстов'на основе приближенных оценок вероятностей классов // Вестник ВГУ. Серия: Системный анализ и информационные технологии. — 2006.

30. Тарасова А. Модификация алгоритма кластеризации с-средних на основе использования объемных прототипов и слияния схожих кластеров // Вестник ВГУ. Серия: Системный анализ и информационные технологии. — 2006.

31. Устенко А. С. Основы математического моделирования и алгоритмизации. — М., 2000.

32. Цыганов Н., Циканин М. Исследование методов поиска дубликатов веб-документов с учетом запроса пользователя // Интернет-математика 2007: сб. работ участников конкурса науч. проектов по информ. поиску. Екатеринбург: 2007. - С. 211-222.

33. Штовба С. Д. Введение в теорию нечетких множеств и нечеткую логику. 2003.

34. Эффективный способ обнаружения дубликатов web документов с использованием инвертированного индекса / С. Ильинский, М. Кузьмин, А. Мелков, И. Сегалович. — 2004. http://webmastera.org/files/File/ secur/FindClonDoc.pdf.

35. Ярушкина Н. Г. Нечеткие нейронные сети в когнитивном моделировании и традиционных задачах искуственного интеллекта. — 2005.

36. Baeza-Yates R. A., Ribeiro-Neto В. A. Modern Information Retrieval.— ACM Press / Addison-Wesley, 1999. http://citeseer.ist.psu.edu/ baeza-yates99modern.html.

37. Bar-Yossef Z., Rajagopalan S. Template detection via data mining and its applications // WWW '02: Proceedings of the 11th international conference on World Wide Web. New York, NY, USA: ACM, 2002. - Pp. 580-591.

38. Bayardo R. J., Ma Y., Srikant R. Scaling up all pairs similarity search // WWW '07: Proceedings of the 16th international conference on World Wide Web. New York, NY, USA: ACM, 2007,- Pp. 131-140.

39. Brin S., Davis J., Garcia-Molina H. Copy detection mechanisms for digital documents // SIGMOD '95: Proceedings of the 1995 ACM SIGMOD international conference on Management of data. — New York, NY, USA: ACM Press, 1995. Pp. 398-409.

40. Chakrabarti S. Mining the Web: Discovering Knowledge from Hypertext Data. — Morgan-Kauffman, 2002. http://www.cse.iitb.ac.in/~soumen/ mining-the-web/.

41. Collection statistics for fast duplicate document detection / A. Chowdhury, O. Frieder, D. Grossman, M. C. McCabe // ACM Trans. Inf. Syst. — 2002. -Vol. 20, no. 2.-Pp. 171-191.

42. Crovella M. E., Taqqu M. S., Bestavros A. Heavy-tailed probability distributions in the world wide web. — 1998. — Pp. 3-25.

43. Dom-based content extraction of html documents // WWW '03: Proceedings of the 12th international conference on World Wide Web. — New York, NY, USA: ACM, 2003. Pp. 207-214.

44. Dugas R. Www unplugged: An html to wml transcoding proxy. — 2003.

45. Efficient retrieval of partial documents // TREC-2: Proceedings of the second conference on Text retrieval conference.— Elmsford, NY, USA: Pergamon Press, Inc., 1995. Pp. 361-377.

46. Fetterly D., Manasse M., Najork M. the evolution of clusters of near-duplicate web pages.— 2003. http://citeseer.ist.psu.edu/ fetterly03evolution.html.

47. Fuller M., Zobel J. Conflation-based comparison of stemming algorithms // Proc. of the Third Australian Document Computing Symposium, Sydney, Australia.— 1998. http://citeseer.ist.psu.edu/ fuller98conflationbased.html.

48. Graves S. Automatic extraction of generic web page components, http : // stp.ling.uu.se/exarb/arch/2004graves.pdf.

49. Gupta S. Context-based content extraction of html documents: Ph.D. thesis. New York, NY, USA: Columbia University, 2006. — Adviser-Gail E. Kaiser.

50. Haas S. W., Grams E. S. Readers, authors, and page structure: A discussion of four questions arising from a content analysis of web pages / / J A SIS. — 2000. Vol. 51, no. 2. - Pp. 181-192.

51. Harman D. What we have learned, and not learned, from tree // In: BCS IRSG '2000 Proceedings, 2000, pp 2-20 http://irsg.eu.org/irsg2000online/papers/harman.htm. — 2000.

52. Heintze N. Scalable document fingerprinting // 1996 USENIX Workshop on Electronic Commerce. — 1996. — November, http : //citeseer. ist. psu. edu/heintze96scalable.html.

53. Hoad T., Zobel J. Methods for identifying versioned and plagiarised documents // Journal of the American Society of Information Science and Technology. 2003. - Vol. 54, no. 3. - Pp. 203-215.

54. Hodge V. J., Austin J. An evaluation of phonetic spell checkers, http:// citeseer.ist.psu.edu/463597.html.

55. Holland J. H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence. — Cambridge, MA, USA: MIT Press, 1992.

56. Jain A. K., Murty M. N., Flynn P. J. Data clustering: a review // ACM Computing Surveys. 1999. - Vol. 31, no. 3. - Pp. 264-323.

57. Lin D. An information-theoretic definition of similarity // ICML '98: Proceedings of the Fifteenth International Conference on Machine Learning. — San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1998.— Pp. 296-304.

58. Manber U. Finding similar files in a large, file system // WTEC'94: Proceedings of the USENIX Winter 1994 Technical Conference on USENIX Winter 1994 Technical Conference. — Berkeley, CA, USA: USENIX Association, 1994. Pp. 2-2.

59. Mifflin H. The psycho-biology of language. — 1935.

60. Mooers C. Application of Random Codes to the Gathering of Statistical Information: Ph.D. thesis. — .Cambridge: MIT, 1948.

61. Pivoted document length normalization: Tech. rep. / A. Singhal, C. Buckley, M. Mitra, G. Salton. Ithaca, NY, USA: 1995.

62. Ponte J. M., Croft W. B. Text segmentation by topic // European Conference on Digital Libraries. — 1997. — Pp. 113-125.

63. Porter M. F. An algorithm for suffix stripping. 1997. - Pp. 313-316.

64. Purpura S., Hillard D. Automated classification of congressional legislation // dg.o '06: Proceedings of the 2006 international conference on Digital government research. New York, NY, USA: ACM, 2006. — Pp. 219-225.

65. Salton G., Allan J., Singhal A. Automatic text decomposition and structuring // Information Processing and Management — 1996. — Vol. 32, no. 2.— Pp. 127-138. http://citeseer.ist.psu.edu/article/ salton94automatic.html.

66. Salton G., Wong A., Yang C. S. A vector space model for automatic indexing // Commun. A CM. 1975. - Vol. 18, no. 11. — Pp. 613-620.

67. Shaozhi Ye Ruihua Song. Ji-Rong Wen W.-Y. M. A query-dependent duplicate detection approach for large scale search engines // APWeb. — 2004. — Pp. 48-58.

68. Syntactic clustering of the web // Selected papers from the sixth international conference on World Wide Web. — Essex, UK: Elsevier Science Publishers Ltd., 1997.-Pp. 1157-1166.

69. S. Park D.M. Pennock R. K. Analysis of lexical signatures for finding lost or related documents // Proceedings of the 25th annual international ACM125

70. SIGIR conference on Research and development in information retrieval. — 2002.-Pp. 11-18.

71. Tree-Report W. Web document retrieval using passage retrieval, connectivity information, and automatic link, http://citeseer.ist.psu.edu/673713. html.

72. Van Rijsbergen C. J. Information Retrieval, 2nd edition. — Dept. of Computer Science, University of Glasgow, 1979. http://citeseer.ist.psu.edu/ vanrij sbergen79information.html.

73. W3C. Document object model (dom) level 2 html specification, http: //www. w3.org/TR/D0M-Level-2-HTML/.

74. W. Pugh M. H. Detecting duplicate and near-duplicate files / / United States Patent 6658423 (December 2, 2003). 2003.

75. Ye S., Wen J.-R., Ma W.-Y. A systematic study of parameter correlations in large scale duplicate document detection // PAKDD. — 2006. — Pp. 275-284.

76. Zobel J., Bernstein Y. The case of the duplicate documents: Measurement, search, and science // Proceedings of the APWeb Asia Pacific Web Conference / Ed. by X. Zhao, J. Li, H. Shen et al. — China: 2006. Pp. 26-39. — LNCS 3841.