Введение 4
1. Постановка задачи 6
2. Обзор предметной области 7
2.1. Поиск повтров в различных сферах 7
2.2. Поиск повторов в документации 9
3. Требования к механизму поиска 11
3.1. Анализ Duplicate Finder 11
3.2. Определение требований 13
4. Проектирование механизма поиска 14
4.1. Схема конвейера 14
4.2. Предобработка текста 15
4.3. Поиск точных повторов 17
4.4. Поиск неточных повторов 19
4.4.1. Алгоритм на основе редакционного расстояния . . 20
4.4.2. Алгоритм на основе N-грамм 23
4.5. Балансировка групп повторов 25
5. Особенности реализации 28
5.1. Используемые технологии 28
5.2. Архитектура 28
6. Тестирование 30
Заключение 36
Список литературы 37
Документация является неотъемлемой частью большинства крупных проектов. При этом с ростом и развитием продукта она становится все объемнее и запутаннее: на первых этапах жизненного цикла проекта документация может отсутствовать совсем, однако чем дольше проект находится в фазе реализации, тем больше функционала и особенностей нужно документировать. Неудивительно, что со временем на поддержку документации будет тратится все больше сил и времени, что затрудняет сопровождение проекта.
В целом документацию можно разделить на два типа: описательную и справочную [27]. Описательная документация нужна для общего ознакомления пользователя с продуктом: она не содержит много деталей работы продукта или технических подробностей, и в основном представлена естественным языком. Справочная, наоборот, ориентирована на пользователей, которые уже разбираются в предметной области, и просто хотят найти какую-либо специфичную информацию. Поэтому, справочная документация обычно является сводкой существующего функционала: список методов, интерфейсов и т.п., и часто представлена исходным кодом. На практике, в одном документе могут быть фрагменты обоих типов, то есть документация является сочетанием естественного языка и исходного кода.
Одним из наиболее влиятельных факторов усложнения ведения документации является наличие большого количества повторов. Они не только могут сильно раздувать общий объем, но также из-за них усложняется сохранение целостности — одно и то же изменения приходится вносить несколько раз в разные части документации, что легко может привести к ошибкам и пропускам. Исследования также показывают, что повторы могут существовать практически в любом документе, и их наличие не зависит от конкретики продукта [10, 28]. Кроме того, в этих работах подтверждается, что повторы действительно оказывают негативное влияние на общее качество документации.
Сам по себе поиск повторов практически всегда является некоторой подзадачей для достижения более осмысленной цели, поэтому он применяется в совершенно различных областях [1]. Например, в сфере разработки ПО наибольшее внимание уделяется поиску клонов в исходном коде [33]. Инструменты, основанные на этом подходе, предоставляют широкий спектр возможностей, от помощи с рефакторингом, до анализа недостатков глобальной архитектуры...
В ходе данной работы были получены следующие результаты.
1. Проанализированы основные подходы и средства, которые используются в существующих инструментах для поиска повторов: синтаксические и суффиксные деревья, нейронные сети, обработка естественного языка, алгоритмы хеширования, N-граммы.
2. Выявлены следующие основные требования к новому механизму поиска: объединение точного и неточного поиска, унификация процесса поиска, высокая степень настраиваемости.
3. Спроектирован конвейер для механизма поиска, состоящий из трех основных этапов: предобработка текста, применение алгоритмов поиска повторов, балансировка групп повторов.
4. Разработаны алгоритмы для точного и неточного поиска повторов на основе использованных в Duplicate Finder инструментов.
5. Выполнена реализация инструмента на языке Python с использованием пакета NLTK для предобработки текста, исходный код выложен на GitHub и доступен по ссылке https://github.com/ IceWind2/TextDuplicateSearch; проведена интеграция с Duplicate Finder.
6. Проведено тестирование инструмента на корпусе документов, по результатам работы собрана статистика и проведен ее анализ.
