Введение 4
Глава 1. Постановка задачи 6
Глава 2. Предварительные сведения 8
2.1 Структуры данных как способ представления текстовой информации .. 8
2.2 Классические задачи информационного поиска 11
Глава 3. Суффиксные деревья как способ представления текста 17
3.1 Краткая история, основные результаты, открытые проблемы 17
3.2. Основные понятия и определения 20
3.3. Построение суффиксного дерева 23
Глава 4. Алгоритмы построения суффксных деревьев 28
4.1 Адаптированный алгоритм Уккокена 28
4.2 Отладочная версия построения суффиксных деревьев 28
4.3 Оценка времени работы 30
4.4 Преимущества алгоритма Уккокена 30
Глава 5. Описание приложения 31
5.1. Средства реализации 31
5.2 Использование видео контента цифровой коллекции 31
Заключение 33
Список литературы: 34
Приложение
На сегодняшний день основная часть информации поступает, редактируется и хранится в электронном виде. Вследствие этого объем данных во всемирной паутине постоянно увеличивается, люди тратят огромное количество времени на её фильтрацию.
Зачастую информация в интернете недостоверна и никак не структурирована, а любая статья, публикация, работа может быть копирована и выложена под своим именем любым пользователем. Таким образом, одной из главных проблем является проверка на плагиат текстовых документов в цифровых коллекциях, библиотеках, интернет сайтах и ресурсах.
Проблема машинной обработки текстовой информации очень актуальна, но не стоит забывать об обработке видео и аудио контента. Ведь этот способ представления информации несколько эффективнее.
В данной работе рассматриваются методы сравнения текстовых документов, видео и аудио файлов, приведено несколько вариантов решений проблем, заявленных в начале.
В первой главе представлена постановка самой задачи, которая разделена на несколько подзадач и её математическая модель.
В главе «Предварительные сведения» сформулированы основные определения и тезисы, которые понадобятся для изучения дальнейшего материала. Разделами данной главы являются:
1. Структуры данных как способ представления текстовой информации. Здесь раскрываются такие понятия как «структуры данных», «поисковые структуры данных», их классификация, примерами таких объектов являются: деревья, массивы, списки.
2. Классические задачи информационного поиска. Дана формулировка следующих задач:
• Сравнение двух строк
• Поиск подстроки в строке
Далее приведены определения строки, алфавита, суффикса, префикса, отношения порядка.
В третьей главе исчерпывающе объясняется такая структура данных, как суффиксное дерево. Описан наивный алгоритм построения деревьев суффиксов, приводятся примеры. Затем рассматриваются алгоритмы построения суффиксных деревьев.
Четвертая глава посвящена реализации адаптированных и модифицированных под поставленную нами задачу алгоритмов Уккокена. Этот раздел состоит из 4 подразделов:
1. Модифицированный алгоритм Уккокена
2. Отладочная версия построения суффиксных деревьев
3. Время работы алгоритма
4. Преимущества алгоритма Уккокена
В пятой главе приведено подробное описание работы программы.
В заключении описываются полученные результаты данной бакалаврской работы.
Результатами данной работы являются:
1. Нахождение решения проблемы поиска документов по аналогии.
2. Изучение методов сравнения документов
3. Выявление двух схожих цифровых документов
5. Реализация программного кода
5. Выявление плюсов и минусов программы
В рамках данной работы были приведены такие понятия как «структуры данных», «поисковые структуры данных», «суффиксые деревья», «строки», изучены их области применения. Предоставлено решение проблемы машинной обработки текстовой информации для выявления плагиата. Разработана программа для поиска и выявления дубликатов текстовых, аудио и видео файлов. В основе реализованной программы лежит построение суффиксного дерева.
