Автореферат (1149621), страница 3
Текст из файла (страница 3)
. . , ), составленного из точных 1 , . . . , , соответствующий интервал выглядит так: [1 − , + ], где = 0,15 ∗ ∑=1 | | − ∑−1=1 dist ( , +1 )./∗ — Входные данные/∗ — Результат1 ← ∅2 Initiate()3 repeat4 ← ∅5for each ∈ ∪ 6 ← NearBy()7if ≠ ∅8′ ← GetClosest(, )9Remove(, ′) /* Удаление и ′ из и S10if Before(, ′)11 ← ∪ {⟨, ′ ⟩}12else13 ← ∪ {⟨ ′ , ⟩}14Join(, )15 until = ∅16 ← ∪ Листинг 1.
Алгоритм компоновкинеточных повторов/∗ , , — Входные данные/∗ — Результат1 1 ← ∅ /* начало фазы 1 (сканирование)2 for ∀ 1 : 1 ∈ ∧ |1 | = 3if d (1 , ) ≤ 4add 1 to 15 2 ← ∅ /* начало фазы 2 («усушка»)6 for ∈ 172′ ← 8for ∈ 9for ∀2 : 2 ⊆ ∧ |2 | = 10if Compare(2 , 2′ , )112′ ← 212add 2′ to 213 3 ← Unique(2 ) /* начало фазы 3 (фильтрация)14 for 3 ∈ 315if ∃3′ ∈ 3 : ⊂ 3′16remove 3 from 317 ← 3Листинг 2. Алгоритм поиска пообразцуТеорема 1. Алгоритм компоновки неточных повторов является корректным относительно определения 2, то есть его результаты соответствуют данному определению.11Доказательство опирается на формальное описание функции NearBy, выдающей дляпроизвольной группы повторов список ближайших к ней. Наилучший кандидат используется для компоновки соответствующей неточной группы.
Понятие близостигрупп повторов также формально определяется в диссертации.Алгоритм не обладает полнотой, поскольку скомпоновать исходные точные повторы в неточные можно многими альтернативными способами. Кроме того, исходноемножество точных повторов также не является полным.Далее предложен ряд оптимизаций, уменьшающих объем выдачи алгоритма.В главе 3 представлена методика интерактивного поиска неточных повторов, реализующая семантический поиск посредством вовлечения пользователя в процесс (тоесть семантику задаёт и контролирует пользователь); в методику входит предложенный автором диссертации алгоритм поиска по образцу, сформулирован критерий полноты и доказана полнота предложенного алгоритма.Определение 4.
Пусть для некоторого документа у нас имеется группа неточныхповторов с точностью в смысле определения 3, и пусть имеется — текстовыйфрагмент документа . Если ∈ , то будем говорить, что является группой неточных повторов фрагмента с точностью .Критерий полноты для нашего алгоритма определим следующим образом. Пустьдля произвольного документа , для любого его текстового фрагмента , а также для — некоторой выдачи алгоритма и любой группы неточных повторов фрагмента с точностью выполнено следующее условие:∀ ∈ ∃ ∈ : | ∩ | ≥||21(3 − ).Смысл данного критерия применительно к алгоритму поиска по образцу заключается в том, что если этот критерий выполнен для любой выдачи алгоритма , то для любого неточного повтора образца , содержащегося в документе , множество R будетсодержать текстовый фрагмент, который существенно пересекает данный повтор.
Таким образом, этот неточный повтор оказывается покрыт выдачей, и пользователь, просматривая результаты работы алгоритма, сможет, при желании, выполнить редактирование границ соответствующего элемента выдачи с тем, чтобы данный повтор былвключен в результирующую выдачу полностью. На практике наилучшие результаты12достигаются для ≥ 0,77, т.к. в этом случае критерий полноты дает нижнюю оценку||2, то есть все элементы «цепляют» неточные повторы минимум на половину длиныобразца. Но следует отметить, что результаты экспериментов показывают бо́льшее пересечение выдачи алгоритма и неточных повторов в документе.Алгоритм поиска по образцу на фазе 1 использует определение редакционного расстояния по наибольшей общей подпоследовательности (монография J.
Leskovec с коллегами «Leskovec, J. Mining of Massive Datasets», 2014 год). Спецификация алгоритмапредставлена на листинге 2.Теорема 2. Алгоритм поиска по образцу обладает полнотой, то есть любая его выдача (множество R) удовлетворяет критерию полноты.Доказательство ведётся по основным фазам алгоритма: показывается, что каждая изних не нарушает полноты.
Доказательство также опирается на ряд дополнительныхсвойств неточных повторов, сформулированных и доказанных в тексте диссертации.Далее приводятся четыре оптимизации алгоритма, предназначенные для увеличениябыстродействия и уменьшения объёма выдачи. Для трёх из них доказывается, что онине нарушают полноты.В главе 4 представлен метод улучшения документации на основе неточных повторов, включая автоматизированный рефакторинг документации в формате DocBook.Общая схема метода представлена на рис. 1.ДокументацияИсправлениядокументацииРекомендациипо написаниюдокументацииУлучшеннаядокументацияАнализповторовАвтоматическийпоиск повторовПовторноеиспользование,рефакторингПовторно используемые фрагментытекстаРис.
1. Схема метода улучшения документации ПОна основе поиска неточных повторовГлава 5 посвящена реализации предложенных подходов, а также экспериментам нареальной документации ПО. Представлен программный инструмент Duplicate Finer,13разработанный автором диссертационной работы. Инструмент работает в двух режимах: автоматическом (см. рис. 2) и интерактивном (см.
рис. 3). Первый режим позволяет сделать экспресс оценку наличия повторов в документации на основе алгоритмакомпоновки неточных повторов. Второй режим позволяет учесть семантику повторовчерез интерактивное взаимодействие с пользователем (то есть пользователь задаётшаблон поиска, «замыкая» его семантически); данный режим использует алгоритмпоиска по образцу. Инструмент работает с документацией в формате DocBook и«плоским»текстом.Практически,любойдругойформатконвертируетсявDocBook/«плоский» текст с помощью известной утилиты Pandoc.Рис. 2. Пример отображенияРис.
3. Пример тепловой карты инеточного повтораокна просмотра найденных повторов(автоматический режим)(интерактивный режим)В заключении формулируются итоги диссертационного исследования.1. Предложенаформальнаямодельнеточныхповтороввпрограммнойдокументации, разработан алгоритм поиска неточных повторов в документацииПО на основе компоновки точных повторов, найденных с помощью методапоиска точных клонов ПО. Доказана корректность алгоритма.2. Создана методика интерактивного поиска неточных повторов, позволяющаяучитывать заданную экспертом семантику повторов. Создан алгоритм поиска пообразцу, доказана полнота данного алгоритма. Выполнены оптимизацииалгоритмадляувеличениябыстродействияложноположительных срабатываний.14иуменьшенияколичества3. Создан метод улучшения документации ПО на основе неточных повторов, включая автоматизированный рефакторинг документации в формате DocBook.В качестве рекомендаций для использования полученных результатов в промышленности, образовании и научных исследованиях указывается, что предложенныеалгоритмы могут быть реализованы в составе более сложных целевых сервисов поразработке промышленной документации ПО.
Модульная архитектура реализациипредложенных алгоритмов допускает замену отдельных элементов (алгоритма вычисления редакционного расстояния и др.), а также эффективное распараллеливание.Предложенная в работе методика может быть уточнена в соответствии с особенностями процесса разработки документации в конкретной компании и эффективно применена при сопровождении больших пакетов долгоживущей документации, а также длявыработки корпоративного стандарта документации. Предложенные средства разработки могут быть применены на практике — как непосредственно, так и в составе более сложных средств разработки и поддержки документации ПО.Сформулированы также следующие перспективы дальнейшей разработки представленной в работе тематики: разработка алгоритмов автоматического поиска неточных повторов, учитывающих структуру документа, автоматизированное извлечение из документации иерархии объектов, которые документация описывает (с использованием машинного обучения); классификация повторов в зависимости от типа документации, дальнейшее совершенствование инструментов поиска неточных повторов.СПИСОК ПУБЛИКАЦИЙ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИСтатьи из «Перечня российских рецензируемых научных журналов, в которыхдолжны быть опубликованы основные научные результаты диссертаций на соискание ученых степеней доктора и кандидата наук», сформированного согласнотребованиям, установленным Министерством образования и науки РоссийскойФедерации1.
Луцив, Д.В. Обнаружение неточно повторяющегося текста в документации программного обеспечения / Л.Д. Кантеев, Ю.О. Костюков, Д.В. Луцив,Д.В. Кознов, М.Н. Смирнов // Труды Института системного программированияРАН. — 2017. — № 4. — С. 303–314.152. Луцив, Д.В. Задачи поиска нечётких повторов при организации повторного использования документации / Д.В. Луцив, Д.В.
Кознов, Х.А. Басит, А.Н. Терехов// Программирование. — 2016. — № 4. — С. 39–49.3. Луцив, Д.В. Метод поиска повторяющихся фрагментов текста в технической документации / Д.В. Луцив, Д.В. Кознов, Х.А. Басит, О.Е. Ли, М.Н. Смирнов,К.Ю. Романовский // Научно-технический вестник информационных технологий, механики и оптики. — 2014. — 4 (92).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
