Содержание к диссертации
Введение
Глава 1. Проблема обнаружения схожих документов . 13
1.1. Задача распознавания схожих документов 15
1.2. Определение понятия схожих документов 17
1.3. Источники схожих документов в Интернете 19
1.4. Основные метрики подобия документов 20
1.5. Методы обнаружения схожих документов 22
1.6. Методы кластеризации 31
1.7. Предварительная обработка документа 33
1.8. Постановка задачи 34
Глава 2. Моделирование системы оценки схожести документов на уровне блоков 36
2.1. Модель представления web-документа 36
2.2. Метод выделения блоков из web-документа 39
2.3. Метод оценки схожести блоков 41
2.4. Подходы к формализации нечеткости знаний о схожести документов 44
2.5. Метод оценки схожести web-документов 45
2.6. Выводы 56
Глава 3. Алгоритмизация процедуры оценки схожести web-до кументов на уровне блоков 57
3.1. Алгоритмы разбиения web-страниц на блоки 57
3.2. Алгоритмы создания единого отпечатка на основе локальных параметров документа 74
3.3. Выводы 87
Глава 4. Программная реализация метода оценки схожести web-документов 89
4.1. Структура программного обеспечения 89
4.2. Программная платформа 92
4.3. Программная реализация 92
4.4. Графический интерфейс 95
4.5. Последовательность работы с программой 101
4.6. Тестирование программы 103
4.7. Результаты практической апробации метода оценки схожести web-документов на уровне составляющих их блоков 103
4.8. Выводы 111
Заключение 113
Литература
- Определение понятия схожих документов
- Подходы к формализации нечеткости знаний о схожести документов
- Алгоритмы создания единого отпечатка на основе локальных параметров документа
- Программная реализация
Введение к работе
Актуальность работы. Экспоненциальный рост объемов информации, наблюдающийся в последние годы, обуславливает бурное развитие различных методов информационного поиска, под которым понимается выявление в некотором множестве документов, удовлетворяющих заранее определенному условию поиска. Необходимость поиска нужной информации в гигантских массивах данных вызывает потребность в поисковых машинах, создание которых требует решения множества специфических задач.
Одной из таких задач является задача определения схожести различных web-документов между собой. Известно, что более 30% всего содержимого Интернета является дубликатами уже существующих страниц. Выявление дубликатов позволяет решить следующие задачи:
• устранение повторяющихся документов в списках, выдаваемых поисковой машиной по запросу. В базах данных крупнейших поисковых машин имеется значительное количество записей-дубликатов. Успешное определение дубля документа, уже имеющегося в базе, позволяет сэкономить место и улучшить качество поиска;
• сжатие данных, достигаемое путем кластеризации документов-дубликатов, позволяет значительно уменьшить размер массивов документов. Применение подобной техники к индексу поисковой машины позволяет исключить до 30% документов, и как следствие, увеличить скорость работы с данным индексом;
распознавание массовых несанционированных рассылок электронной почты (спама), доля которых составляет более 90% всего потока электронной почты. Детектирование схожих документов, которыми являют ся подобные рассылки, позволяет эффективно находить и уничтожать огромные объемы нежелательной корреспонденции;
• автоматическая классификация. При условии качественной классификации документов возникает возможность более простой навигации по большим массивам документов (например, по результатам поиска), а также потенциал для оптимизации работы с непредсказуемыми по содержимому информационными потоками;
• нахождение похожих по содержанию документов. Функция нахождения по запросу документов, подобных заданному, позволяет определять их версионность, а также обнаруживать цитирования и плагиат.
Цель работы. Целью диссертационной работы является разработка математического и программного обеспечения для повышения эффективности обнаружения схожих документов за счет разработки метода оценки сходства web-документов на основе их локальных параметров с использованием предварительного разбиения на структурно-семантические блоки.
Основная задача формулируется как повышение качества распознавания схожих web-доку ментов путем оценки схожести блоков, составляющих web-документы, и применении алгоритмов создания отпечатков на основе локальных параметров документов.
Для достижения цели работы необходимо решение следующих задач исследования:
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 приложений.
Содержание работы. В первой главе проводится анализ современных методов обнаружения схожих текстов в целом и их применения к области web-документов в частности. Выделяются основные метрики подобия и метрики оценки эффективности.
Во второй главе рассматривается задача выявления схожести web-доку ментов, используя информацию о схожести их структурно-семантических блоков. На основании модели представления web-документа предлагается метод выделения блоков из web-доку ментов. На основе стандартной метрики перекрытия описывается метод оценки схожести блоков и предлагается метод оценки схожести web-документов на уровне составляющих их блоков.
В третьей главе проводится алгоритмизация процедуры оценки схожести web-документов на уровне блоков, для чего предлагается алгоритм разбиения web-документа на структурно-семантические блоки. Кроме того, проводится исследование алгоритмов, использующих локальные параметры документов для создания их отпечатков и даются рекомендации по их использованию.
В четвертой главе описывается структура программной платформы, позволяющая экспериментально проверить эффективность вышеописанных моделей и алгоритмов. Приводится общее описание разработанного программного комплекса «Модуль оценки сходства web-документов на уровне бло ков», рассматривается его графический интерфейс и функциональные возможности. Проводится экспериментальная проверка метода оценки схожести web-документов на основе блоков и алгоритма выделения структурно-семантический блоков из web-доку ментов.
В заключении формулируются научные и практические результаты диссертационного исследования.
Прилагается список использованных литературных источников.
Определение понятия схожих документов
Сообщается, что более 30% [54] (а по некоторым данным и 40%) всего содержимого Интернета является дубликатами уже существующих страниц. К примеру, существует более 320 сайтов-зеркал документации к Linux Document Project2. В связи с этим, во избежание появления дубликатов документов в выдаче поисковой машины, в процессе пополнения ее индекса необходимо уметь определять схожесть рассматриваемого документа с уже имеющимся в базе.
Корректное определение схожих документов применительно к web-поиску преследует многочисленные цели [84]: сжатие данных. Путем кластеризации документов-дубликатов можно значительно уменьшить размер больших массивов документов. Еще большего сжатия можно достигнуть, объединяя не только дубликаты, но и просто схожие документы. К примеру, применение подобной техники к индексу поисковой машины позволяет исключить до 30% документов, и как следствие, увеличить скорость работы с данным индексом; улучшение ранжирования. В соответствии с [77], в выдачах крупнейших поисковых машин имеется 5.5% записей-дубликатов. Фильтрация в вы 2http://www.tldp.org/mirrors.html даче схожих документов позволяет повысить информативность поиска для пользователя; автоматическая классификация. При условии качественной классификации документов возникает возможность более простой навигации по коллекциям документов (например, по результатам поиска), а также потенциал для оптимизации работы с непредсказуемыми по содержимому информационными потоками; распознавание массовых почтовых рассылок (спама). На сегодняшний день доля спама в Интернет-трафике составляет более 35%. Более 90% потока электронной почты, проходящей через почтовые серверы, является спамом. Детектирование схожих документов, которыми как раз и являются подобные рассылки, позволяет эффективно находить и уничтожать огромные объемы нежелательной корреспонденции. распознавание плагиата. Проверка документа на наличие заимствований из различных сетевых источников позволяет с высоким уровнем достоверности определять степень оригинальности документа; нахождение похожих по содержанию документов. Функция нахождения по запросу документов, подобных заданному, позволяет находить подобные друг другу документы. В перспективе возможно построение дерева версий документа, отслеживая параллельное развитие из одного первоначально источника.
Применение техники обнаружения схожих документов не ограничивается вышеописанными целями. Она также может применяться в задачах краулин-га (web-crawling), обнаружении ссылочного спама (web-spam), определении авторства текста по стилю его написания и в других областях.
Кроме того, эта задача тесно связана с задачей кластеризации документов [65]. Целью в данном случае является разбиение заданной выборки документов на непересекающиеся подмножества (кластеры) таким образом, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно различались.
Под выражением «схожие документы» можно понимать множество ве щей. С одной стороны, документы с незначительными различиями, например, с различным оформлением, несомненно, будут являться схожими. С другой стороны, существуют тексты, написанные совершенно различным языком, незначительно пересекающиеся даже по используемым словам, но имеющие очень большую семантическую схожесть. Такие документы также можно на звать схожими. Кроме того, между двумя вышеописанными крайностями су ществует множество серединных положений. Поэтому без четкого опреде ления того, что именно можно назвать схожими документами дальнейшее обсуждение вести бессмысленно. :
Собственно понятие нечеткости можно интерпретировать по разному [5]. Схема, отображающая виды и формы нечеткости, приведена на рис. 1.1.
Из-за неоднозначности определения понятия схожих документов (также называемых почти-дубликатами) оно, в зависимости от необходимости, по-разному трактуется различными авторами. Как показано в [85], существует «парадокс измерения»: пытаясь дать объективную оценку, исследователи в ходе работы делают много субъективных допущений. В результате, незначительные расхождения в определениях «дубликатов» и умолчание части параметров экспериментов авторами приводят к серьезным расхождениям результатов, и зачастую сложно определить ценность и место проведенных исследований.
Из-за отсутствия эталонной меры для оценки результатов определение качества сравнения на сегодняшний день весьма затруднительно. На данный момент специальные методики оценки качества определения степени подобия документов отсутствуют, и в ближайшее время их появление не предвидится [49]. Различными авторами создаются различные определения подобия, и, соответственно, разные меры схожести [67]. В связи с этим в настоящее время формирование методик и средств для оценки качества сравнения информации представляет собой открытую проблему.
В нижеследующем тексте будут использованы несколько понятий. Под документом в большинстве случаев будет иметься ввиду типичный web-документ, полученный из Интернета (включающий в себя html-код, элементы разметки, заголовки и т.п.). Документом-дубликатом (или просто дубликатом) будет называться идентичная оригиналу копия документа. Схожими
документами (или почти-дубликатами) будут называться документы, имеющие одно и то же содержание, за исключением отдельных, относительно небольших, различий. Термины «схожесть» и «сходство» употребляются как синонимы, если не указано обратное.
Подходы к формализации нечеткости знаний о схожести документов
Понятие схожих документов, как было показано в главе 1, само по себе подразумевает нечеткость. Схожесть документов можно считать абсолютной только в том случае, если они полностью совпадают между собой. Во всех остальных случаях численное выражение схожести находится в интервале [0,1). Вне зависимости от выбранной метрики схожести документы считаются почти-дубликатами, если схожесть превышает некоторый, заранее заданный порог.
Кроме того, нечеткость проявляется и в степени достоверности оценки схожести. Поскольку прямое попарное сравнение документов в условиях больших их объемов проводить не представляется возможным из-за недостатков машинных ресурсов, все существующие реализации методов выявления схожести документов работают на основе некой хеш-функции. Добиваясь таким образом значительного уменьшения вычислительной сложности сравнения, они жертвуют точностью и полнотой, поскольку так или иначе значительная часть документа отбрасывается в процессе преобразования.
Таким образом, очевидна потребность выражать имеющиеся знания о схожести документов через нечеткие знания.
В соответствии с [32], основные подходы к моделированию нечеткости можно систематизировать с помощью следующих критериев: общий подход к представлению нечеткости (нечеткие множества, вероятностные множества и пр.); область определения функции принадлежности (стандартные нечеткие множества, нечеткие числа и пр.); область значений функции принадлежности ([0, 1]-нечеткие множества, [-1, +1]-нечеткие множества, интервальнозначные нечеткие множества и пр.); тип соответствия между область определения и область значений функции принадлежности (взаимооднозначное, невзаимооднозначное и пр.).
В рассматриваемом случае необходимости в использовании расширенных трактовок нечеткости не обнаружилось, поэтому использовался математический аппарат стандартных нечетких множеств.
В пользу использования нечеткой логики против теории вероятностей говорят следующие соображения. Нечеткая логика описывает иной род неопределенности - не вероятность некоторого исхода, как теория вероятности, а неопределенность имеющегося результата. С понятием схожести документов, рассматриваемых в данной работе, это соотносится лучше.
На данный момент мы имеем совокупность (D, В, 5, М), представляющую множества web-документов, блоков и отпечатков соответственно и матрицу схожести блоков. Имеются следующие соответствия: 1. deD. 2. fb:d-+ BW,BW = {bi,b2,...,bn},n 0. 3. fa : b — Si, Bb = {si, s2,..., sm}, m 0. 4. M = [mjj],rajj = Sim(bi, bj). Необходимо построить метод, позволяющий оценить степень сходства документов d Є D. Иными словами, необходимо разработать метрику сходства пары документов Sirrid(di, dj). Введем дополнительные обозначения: h(b) = \Sb\ - количество отпечатков блока Ь. n(d) = \Bd\ - количество блоков документа d. 1(b) = Length(b) - длина блока b (символов). 1(d) — Length(d) - длина документа d (символов). Очевидны следующие свойства: і. т = тЬ«н). 2. V6 E,0 /(6) l(db). Отсюда понятно, что в случае, когда 1(d) — l(bd), множество Bd состоит из одного элемента, идентичного d.
Полученный набор нечетких множеств /idf(6) отражает совокупную информацию о схожести имеющихся в каждом документе d Є D блоков Ъ Є Bd. Применяя различные операции нечетких множеств над этим набором, можно получать разнообразную информацию о схожести отдельных документов и блоков. Рассмотрим основные операции.
Согласно [27], степень равенства двух нечетких множеств d;, dj определяется через операцию эквивалентности А - В = MIN(MAX(l - А, В), МАХ{1 - В, А)) (2.18) выражением следующего вида: Sim(dhdj) = f](fidi(b) - / (6)) -. (2.19) ЬеВ Выражение (2.19) может использоваться в качестве метрики блочной схожести - оно выдает значение в интервале [0, 1] и в целом отражает степень совпадения блоков документов. Степень включения двух нечетких множеств d(, dj определяется через операцию импликации А - В = МАХ(1 - А, В) (2.20) выражением следующего вида: Sims(dh dj) = P{/2di{b) -» // (6)) (2.21) ЬеВ Степень включения отражает в интервале [0, 1] нечеткую величину включения блоков документа di в документ dj.
Алгоритмы создания единого отпечатка на основе локальных параметров документа
В предыдущем параграфе предложен алгоритм, решающий задачу выделения структурно-семантических блоков из web-документа. Однако возмож if ны ситуации, когда вместо фиксированного числа блоков одинакового уровня детальности, получаемых на выходе, хотелось бы получать иерархическую структуру, содержащей все степени детальности разбиения на блоки. \
В этом случае имеет смысл построение дерева детальности: структуры, содержащей на верхнем уровне всю страницу целиком, а на более низких последовательно уменьшающую размер блоков, увеличивая их число.
Идея построения дерева детальности почерпнута из работы [31], в которой проводилось снижение детальности отсегментированного изображения на основе построения иерархического дерева детальности сегментов. Изображение представлялось в виде графа, в котором веса ребер определялись степенью различимости сегментов. Путем многократного решения задачи о минимальном разрезе графа он разделялся и строилось иерархическое дерево детальности.
В нашем случае аналогичным представлением служит ациклический ориентированный графа, полученный из DOM-дерева, узлами которого служат HTML-теги. Поскольку в силу особенностей web-страниц данный граф является разреженным и своей детальностью значительно превышает необходимую детальность блоков, необходимо провести снижение числа исходных узлов путем их слияния.
Отсутствие циклов заметно упрощает алгоритм, позволяя избежать проблемы выбора стока и истока, просто последовательно выделяя и отрезая поддерево, имеющее наибольший вес. С другой стороны, из-за наличия различных по своему действию тегов появляется сложность в необходимости учитывать класс тега для более корректного выделения логических блоков.
Первые два этапа построения дерева детальности аналогичны описанным выше в случае выделения блоков: на первом этапе из HTML-страницы формируется DOM-дерево, на втором - проводится его упрощение путем отбрасывания неиспользуемых тегов. Далее используется процедура, представленная здесь в виде псевдокода: ProcessTreeCu, q) II поиск узла дерева с макс, весом n = FindNodeWithMaxWeight(u) // условие завершения if (п.weight minWeight) return; II извлечение поддерева u2 = ExtractSubTree(u, n) II добавление узлов в дерево дет. qchild = q.addChildNodeO qchild.push(u, q) qchild.push(u2, q) II рекурсивный вызов процедуры // для оставшихся поддеревьев ProcessTreeCu, qchild) ProcessTree(u2, qchild) Здесь и - корень оригинального DOM-дерева, q - корень дерева детальности.
Общий смысл процедуры состоит в последовательном отсечении от оригинального дерева наиболее «тяжелых» поддеревьев.
Условие завершения работы процедуры может быть двух видов. Во-первых, она может работать до тех пор, пока все поддеревья не будут разбиты на отдельные узлы. Это позволяет максимально детализировать блоки, но в ряде случаев может быть излишним. Время работы в этом варианте в худшем случае пропорционально высоте G.
Второй вариант предусматривает выход из цикла по достижении определенной доли извлеченного текста относительно общей длины документа (в приведенной выше процедуре для этого используется заранее заданная константа minWeight).
Функция веса узла строится из тех же соображений, что и в случае алгоритма выделения блоков.
Еще одной требующей рассмотрения задачей является задача формирования устойчивого отпечатка документа.
В главе 1 был рассмотрен ряд классических методов детектирования схожих документов. Отличительной чертой большинства из них является со здание нескольких отпечатков одного документа. В лексических методах это обычно достигается рандомизацией набора термов, описывающих документ, в синтаксических - выбором различных участков документа для анализа.
Наличие множества отпечатков одного документа, безусловно, увеличивает качество сравнения и предоставляет дополнительные возможности по оценке уровня сходства документов. С другой стороны, когда речь идет о миллионах документов, значительную роль-играет быстродействие применяемых алгоритмов. В этом случае логичным способом ускорения сравнения становится переход от множества отпечатков, идентифицирующих документ, к одному «универсальному».
Это приводит к заметному «огрублению» результатов, так как степень схожести определить уже не удается. Однако выигрыш в скорости и генерации отпечатков, и выполнения сравнения может быть приоритетнее.
Важным свойством методов, ставящих в соответствие каждому документу единственный отпечаток, является «бинарность» их суждений. В самом деле, документы будут считаться схожими только в том случае, если их отпечатки совпадают. В противном случае, никакой связи между документами обнаружено не будет. При уменьшении величины порога, выше которого документы считаются дубликатами, количество документов, очевидно, увеличивается. Таким образом, невозможно сохранить высокие значения точности и полноты для всего диапазона: достижение высокой полноты вызывает снижение точности, и наоборот.
Программная реализация
Полученная в результате проектирования приложения диаграмма классов приведена на рис. 4.3.
В процессе проектирования набора классов мы исходили из реальных сущностей, используемых приложением. Основное множество классов можно разбить на три категории.
Первая категория классов отвечает за создание и обработку отпечатков коллекций web-доку ментов. Иерархическая структура «коллекция web-документов - web-документ - блоки web-документа - отпечатки блока» нашла свое отражение в классах FileList, File и FileBlock соответственно (отпечатки блока хранились в массиве, принадлежащем нужному экземпляру класса FileBlock). Статический класс ShingleFactory предоставляет методы генерации отпечатка нужным алгоритмом на основе поданного текстового блока. 1http://www.sun.com Класс ShingleCollector предоставляет удобные интерфейсы для поиска одинаковых отпечатков, а также выяснения принадлежности отпечатков к блокам и наборот.
Вторая категория классов предназначена для разбиения web-документов на блоки. Для этого был разработан ряд классов, наследующих базовый функционал классов библиотеки HTMLParser. Класс VisitorRemover позволяет удалять из дерева тегов задаваемые условием узлы; класс VisitorCalculator служит для расчета весов узлов дерева; класс ShingleExtractor преобразовывает дерево тегов к текстовому виду, выделяя непосредственный контент web-документа. Статический управляющий класс PageProcessor осуществляет обработку заданной web-страницы.
Третья категория классов включает в себя служебные классы, служащие для работы с графическим интерфейсом пользователя, а также использование дополнительных сторонних библиотек, описанных ниже.
Подробное описание классов и их назначения приведено в приложении Е.
В качестве средства построения DOM-дерева из HTML-страницы использовалась открытая библиотека HTMLParser2. Эта библиотека предоставляет широкие возможности по обработке, просмотру и редактированию HTML-кода, а так же сравнительно легко расширяема собственными функциями.
Для расчета степени близости web-страниц различными стандартными метриками использовалась библиотека Simmetrics3.
В качестве интерпретатора вводимых пользователем формульных выражений применялась библиотека JFormula4.
Для программной реализации генетических алгоритмов в задаче выделения блоков использовалась открытая библиотека JGAP5.
Вычислительный алгоритм решения задачи разбиения web-документа на блоки реализован на основе алгоритма А1, описанного в главе 3.
Разработанное в итоге приложение обладает графическим пользовательским интерфейсом, выполняет функции вычислительного решения задачи, а так же обладает функциями импорта исходных данных и вывода результатов решения.
В качестве входных данных используются web-страницы, представленные в виде HTML-файлов на произвольном носителе информации. Несколько web-страниц может быть представлено в виде тестовой коллекции. Кроме этого, входными параметрами являются настройки алгоритмов.
Разработанное программное обеспечение предназначено для использования на IBM - совместимых ЭВМ с операционной системой Windows 98 и более поздних версий. Для функционирования программы необходимо, чтобы в операционной системе была установлена свободно распространяемая библиотека Java SE 1.5 или выше. Программа не имеет выраженных требований
к объему установленного ОЗУ: объем используемой программой памяти зависит от размерности решаемой задачи.
Похожие диссертации на Разработка математического обеспечения оценки схожести WEB-документов на основе структурно-семантического разбиения
