Оглавление
Введение 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]. Инструменты, основанные на этом подходе, предоставляют широкий спектр возможностей, от помощи с рефакторингом, до анализа недостатков глобальной архитектуры.
Однако, что касается более частной задачи поиска повторов в документации, данной теме уделяется не слишком много внимания, а если она и затрагивается, то лишь поверхностно. Существующие инструменты для работы с исходным кодом полагаются на достаточно специфичные особенности, такие как жесткая структура программы, семантика языков и т.п. [12, 39, 21]. Такие методы плохо подходят для работы с документацией из-за того, что она содержит не только фрагменты исходного кода, но и фрагменты на естественном языке.
Для решения задачи поиска повторов в документации был создан исследовательский прототип — Dupilcate Finder Toolkit [40], основной целью которого является работа с документацией. Данный инструмент представляет собой университетскую разработку, которая делалась многими людьми на протяжении большого временного промежутка, из-за чего проект состоит из множества составных частей, что сильно усложняет поддержку и дальнейшее развитие.
Особенно стоит отметить проблемы с компонентами, непосредственно отвечающими за поиск повторов [6, 41, 38]: они написаны на разных языках, некоторые из них являются внешними закрытыми разработками, они не разделяют потоков данных, повторяют некоторые этапы анализа несколько раз и в целом работают изолированно друг от друга. Для улучшения работы с пакетом было бы разумно разработать единую компоненту, целиком реализующую весь необходимый функционал.
1. Постановка задачи
Целью данной работы является разработка и реализация унифицированной подсистемы поиска точных и неточных повторов для Duplicate Finder Toolkit и ее интеграция с заменой существующих компонент. Для достижения этой цели в рамках работы были сформулированы следующие задачи.
1. Анализ предметной области — поиск повторов в текстах различных видов.
2. Определение проблем поиска повторов в DuplicateFinder и требований к новому механизму.
3. Проектирование конвейера механизма поиска повторов.
4. Разработка алгоритмов точного и неточного поиска.
5. Реализация инструмента и его интеграция в DuplicateFinder.
6. Проведение тестирования разработанного инструмента.
В ходе данной работы были получены следующие результаты.
1. Проанализированы основные подходы и средства, которые используются в существующих инструментах для поиска повторов: синтаксические и суффиксные деревья, нейронные сети, обработка естественного языка, алгоритмы хеширования, N-граммы.
2. Выявлены следующие основные требования к новому механизму поиска: объединение точного и неточного поиска, унификация процесса поиска, высокая степень настраиваемости.
3. Спроектирован конвейер для механизма поиска, состоящий из трех основных этапов: предобработка текста, применение алгоритмов поиска повторов, балансировка групп повторов.
4. Разработаны алгоритмы для точного и неточного поиска повторов на основе использованных в Duplicate Finder инструментов.
5. Выполнена реализация инструмента на языке Python с использованием пакета NLTK для предобработки текста, исходный код выложен на GitHub и доступен по ссылке https://github.com/IceWind2/TextDuplicateSearch; проведена интеграция с Duplicate Finder.
6. Проведено тестирование инструмента на корпусе документов, по результатам работы собрана статистика и проведен ее анализ.
