Автореферат (1149621), страница 2
Текст из файла (страница 2)
Bassett). В качестве базового средства поиска повторов был применен метод поискаклонов в ПО, использована структура данных под названием интервальное дерево(interval tree) для быстрого поиска пересекающихся целочисленных интервалов, атакже редакционное расстояние между строками для вычисления степени сходстватестовых фрагментов. Применена известная метафора тепловой карты (heat map) длявизуализации информации о найденных повторах.
В качестве средств программнойреализации использовались языки Python и Java.6Положения, выносимые на защиту.1. Предложенаформальнаямодельнеточныхповтороввпрограммнойдокументации, разработан алгоритм поиска неточных повторов в документацииПО на основе компоновки точных повторов, найденных с помощью методапоиска точных клонов ПО. Доказана корректность алгоритма.2.
Создана методика интерактивного поиска неточных повторов, позволяющаяучитывать заданную экспертом семантику повторов. Создан алгоритм поиска пообразцу, доказана полнота данного алгоритма.3. Создан метод улучшения документации на основе неточных повторов, включаяавтоматизированный рефакторинг документации в формате DocBook.Научная новизна представленных результатов заключается в следующем.1.
Предложенная формальная модель неточных повторов является новой: в нейделаетсяакцентнасинтаксическойструктуреповторов,уточняетсяиформализуется концепция повторно используемого контента, предложеннаяP. Bassett. M. Nosál и J. Porubän дают определение неточного повтора, но оноявляется неформальным и оставляет в стороне синтаксическую структуруповтора. В работах E. Juergens с коллегами и M. Oumaziz с коллегами лишьговорится о необходимости поиска неточных повторов, но не предлагаетсясоответствующих формальных моделей.2.
Предложенные алгоритмы поиска неточных повторов в документации ПО новы,основываются на формальной модели повторов, что позволяет формальнодоказывать их свойства. В свою очередь, существующие алгоритмы поисканеточных клонов ПО не могут быть применены для решения данной задачи, таккак они производят поиск по синтаксическому дереву программы, а тексты наестественных языках не могут быть эффективно проанализированы такимспособом. Алгоритмы из области информационного поиска, решая аналогичнуюзадачу, созданы для другой модели использования, решая такие вопросы какранжирование результатов при представлении больших выдач, решениепроблемы производительности на больших коллекциях документов, определениесходства/различия документов целиком (а не поиск повторяющихся фрагментов)и т.д.73.
Предложенный метод улучшения документации на основе неточных повторовявляется новым. Выдвинута идея использовать повторы для унификациидокументации и не считать их плагиатом или ненужной избыточностью.Существующиеинженерныеподходыкиспользованиюповторовограничиваются повторным использованием (M. Nosál и J. Porubän, M. Oumaziz)и верхнеуровневым анализом качества документации (A.
Wingkvist).Теоретическая и практическая значимость работы. Полученные результатыобобщают исследования в области поиска повторов в документации ПО, впервыепредлагая формальные определения и алгоритмы. При этом использовались современные методы поиска, такие как поиск клонов в ПО.Практическая значимость работы заключается в создании метода улучшения документации на основе неточных повторов, а также в реализации предложенных алгоритмов в рамках программного инструмента Duplicate Finder, исходные коды которого, атакже примеры использования, выложены в свободный доступ: https://github.com/spbuse/pldoctoolkit/blob/master/doc-clone-miner.Достоверность результатов работы подтверждается формальными доказательствамибазовых свойств предложенных алгоритмов, а также инженерными экспериментами надокументах реальных программных продуктов.Результаты исследования были доложены на следующих научных конференциях исеминарах: 10th International Andrei Ershov Memorial Conference on Perspectives of System Informatics (PSI, 26 августа 2015 года, Казань), Spring/Summer Young Researchers’Colloquium on Software Engineering (SYRCoSE, 31 марта 2017 года, Иннополис), 5th International Conference on Actual Problems of System and Software Engineering (APSSE,15 ноября 2017 года, Москва), семинар в ИПМ им.
М.В. Келдыша РАН (05 декабря2017 года, Москва), семинар в СПбГТУ (08 декабря 2017 года, Санкт-Петербург).Дополнительной апробацией результатов является поддержка исследований, представленных в диссертации, грантом РФФИ №16-01-00304 «Управление повторами приразработке и сопровождении документации программного обеспечения».Публикации по теме диссертации.
Все результаты диссертации опубликованы в 8ми печатных работах, из них 5 зарегистрированы в РИНЦ, 3 статьи изданы в журналахиз «Перечня российских рецензируемых научных журналов, в которых должны быть8опубликованы основные научные результаты диссертаций на соискание учёных степеней доктора и кандидата наук», 3 статьи опубликованы в изданиях, входящих в базыцитирования Scopus и Web of Science.Работы [1–6, 8] написаны в соавторстве. Личный вклад автора в данных публикациях заключается в следующем. В работе [1] автор разработал алгоритма поиска неточных повторов, соавторы реализовали алгоритм и выполнили необходимые эксперименты.
В работах [2, 3] автор разработал и реализовал алгоритм поиска неточных повторов на основе поиска клонов, соавторы участвовали в создании идеи алгоритма,разработке процесса и настройки инструмента поиска клонов. В работах [4, 5] авторупринадлежит идея доработки алгоритма поиска неточных повторов на основе клонов,реализация этих доработок. Соавторы занимались экспериментами. В работе [6] авторразработал методику применения поиска неточных повторов для улучшения документации, соавторы участвовали в разработке идеи методики, сделали обзор литературы ивыполнили эксперименты.
В работе [8] автору принадлежат идеи визуальных метафор,предложенные для отображения результатов иерархического сравнения документов,соавторы предложили концепцию создания целевых сервисов на базе поиска повторовдля разработки и сопровождения офисной документации.Объем и структура работы. Диссертация состоит из введения, пяти глав, заключения и приложения. Полный объем диссертации — 122 страницы текста с 16 рисункамии 5 таблицами. Список литературы содержит 153 наименования.СОДЕРЖАНИЕ РАБОТЫВо введении описывается проблематика и делается постановка задачи диссертационного исследованияВ главе 1 представлен обзор исследований в данной области и делаются выводы онеобходимости проведения данного исследования.В главе 2 представлена формальная модель неточных повторов.
Ниже приводятсяосновные определения из этой модели.Определение 1. Определим двухместный предикат Before на множестве ∗ × ∗ ,( ∗— множество всех текстовых фрагментов документа ), который является истинным для двух текстовых фрагментов 1 , 2 ∈ тогда и только тогда, когда 1 < 2 ,где [1 ] = [1 , 1], [2 ] = [ 2, 2 ], а 1, 1 и 2 , 2 являются началами и концами от9резков, содержащих текстовые фрагменты 1 и 2 (отрезки являются частью числовойоси от 1 до длины документа в символах). При этом операция [ ] выдает отрезок потекстовому фрагменту.Определение 2.
Рассмотрим упорядоченный набор точных групп ⟨1, … , ⟩ некоторого документа (точная группа — это упорядоченное множество точных повторов, то есть вхождений в документ идентичного фрагмента текста), и каждая группаимеет одинаковое количество элементов: #1 = ⋯ = # . Также пусть текстовыефрагменты, имеющие в разных точных группах одни и те же порядковые номера, следуют в исходном тексте в одном и том же порядке, то есть ∀ ∈ ∀ ∈ (( <) ⇔ Before( , )).Крометого,пусть∀ ∈ {1, … , − 1} будетистинно:Before( , 1+1). Наконец, пусть ∀ ∈ {1, … , #1 } справедливо следующее:−1∑ dist( , +1) ≤ 0,15 ∗ ∑ | |.=1=1Тогда будем говорить, что набор точных групп ⟨1, … , ⟩ порождает группу неточных повторов.Константа 0,15 в этом определении взята из работы (Bassett, 1996).
Данное определение используется в алгоритме компоновки неточных повторов (листинг 1). Следуетотметить, что определение 2 фиксирует константу сходства (хотя наши экспериментыпоказали, что она слишком жёсткая и что на практике её удобно варьировать), а такжене допускает вариаций по краям неточного повтора и в явном виде ориентируется накомпоновку неточных повторов из точных. Ниже представлено обобщённое определение неточного повтора, свободное от этих ограничений.Определение 3. Пусть у нас имеется набор текстовых фрагментов 1, … , документа . Пусть также истинно: ∀ Before ( , +1), и существует упорядоченныйнабор строк 1, … , такой, что имеется вхождение этого набора в каждый текстовыйфрагмент ,тоесть ∀ ∈ {1, … , } ∀ ∈ {1, … , }( ⊂ str( )) ⋀ ∀ ′ ″ ∈{1, … , } ( ′ < ″ ⇒ Before(′ , ′′ )), где — вхождение в . Пусть также для некоторого : 0< ≤ 1 выполнено следующее:∀ ∈ {1, … , } :∑=1 | || |10≥ .Тогда будем говорить, что этот набор текстовых фрагментов 1, … , являетсягруппой неточных повторов с мерой близости k.В представленном исследовании используется более узкий диапазон значений ,что подробно обсуждается в тексте диссертационной работы.Утверждение 1.
Группа неточных повторов в смысле определения 2 является также группой неточных повторов в смысле определения 3. Обратное не верно, даже еслив определении 2 варьировать константу 0,15 так же, как в определении 3.Алгоритм компоновки неточных повторов, реализованный на основе определения2, представлен на листинге 1. Массовой операцией алгоритма является поиск для некоторых интервала и множества интервалов такого подмножества, в котором каждыйинтервал пересекается с данным.Для этой цели используется интервальное дерево;для неточного повтора = (1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
