Введение .................................................................................................................. 3
Постановка задачи .................................................................................................. 4
Глава 1. Обзор методов поиска дубликатов документов ................................... 5
1.1. Синтаксические методы ........................................................................ 6
1.1.1. Алгоритмы sif и Koala ..................................................................... 6
1.1.2. Метод «шинглов» ............................................................................ 8
1.1.3. Long Sent............................................................................................ 9
1.2. Лексические методы .............................................................................. 9
1.2.1. Методы на основе меры TF-IDF .................................................... 9
1.2.2. Heavy Sent ....................................................................................... 12
1.2.3. I-Match ............................................................................................. 12
1.2.4. Метод описательных слов ............................................................ 13
Глава 2. Оценка эффективности методов поиска дубликатов документов ... 15
2.1. Основные метрики .................................................................................. 16
2.2. Оценка эффективности рассмотренных методов ................................ 17
Глава 3. Модифицированный метод .................................................................. 20
3.1. Описание модифицированного метода ................................................. 21
3.3. Анализ результатов.................................................................................. 23
Заключение ........................................................................................................... 26
Список литературы
Современное развитие информационных технологий и сети Интернет
предоставило широким кругам пользователей легкий и быстрый доступ к
огромным массивам самой разнообразной информации. Это вызвало бурный
рост количества дублированного и заимствованного материала, ведь теперь
для создания нового совсем не обязательно действительно что-то
придумывать. В связи с этим крайне остро встал вопрос нахождения
различного рода заимствований в научных статьях и прочих работах.
Проблема выявления оригинальности текста является одной из наиболее
сложных и трудоемких задач анализа данных. Чаще всего она возникает в
процессе установления нарушений авторских прав (проблема плагиата), но
существуют и другие области, для которых данный вопрос актуален:
кластеризация документов по содержанию, удаление избыточной информации
в архивах поисковых систем для улучшения их качества, фильтрация
поискового спама, и ряд других.
Однако колоссальный объем обрабатываемой информации является
основной загвоздкой решения задачи поиска дубликатов. Попарное прямое
сравнение текстов документов займет слишком много времени и потребует
значительных вычислений, поэтому постепенно создавались различные
методы, позволяющие снизить алгоритмическую сложность.
Различают понятия четких и нечетких дубликатов документов.
Четкий дубликат – точная копия текста. Также четким дубликатом будет
считаться документ, полностью содержащий в себе другой документ.
Нечеткий дубликат – частично измененный текст, содержание которого
отличается незначительно, т. е. может содержать в себе отрывки из другого
документа, или не отличается вовсе, т. е. отличается от источника лишь
заменой некоторых слов на их синонимы.
В рамках данной курсовой работы были получены следующие
результаты:
1. Изложены наиболее популярные и эффективные с вычислительной
точки зрения алгоритмы решения проблемы поиска дубликатов.
2. Предоставлены оценки эффективности рассмотренных методов.
3. Описан модифицированный вариант метода и проанализированы
полученные результаты.
