Диссертация (1149623), страница 9

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 9)

Проблема разработки и сопровождения документации ПО является актуальной, соответственно, востребованы новые исследование, создание новых методов и средств.422. Задача поиска и анализа повторов в документации ПО является актуальной, очем свидетельствует ряд исследований на протяжении последних десяти лет[76, 89, 111, 110, 112, 121, 145, 150]. В то же время данные работы не образуют явно выделенную область исследований, ограничиваясь case-studies дляразличных видов документов, отсутствует единая терминология, нет перекрёстных цитирований.

Наконец, хоть в некоторых работах и указывается наважность поиска и анализа неточных повторов [89, 111, 112], однако реальных шагов в этом направлении до сих пор не было сделано.3. Задача поиска неточных повторов в текстах не является новой. Данная задачарассматривается и решается в различных областях — в информационном поиске, в рамках обнаружения клонов в ПО, при поиске плагиата и т.д. Тем неменее следует отметить, что затруднительно применение имеющихся в этихобластях методов «as is» к задаче описка неточных повторов в документацииПО из-за специфики вышеупомянутых областей (например, работа с большими объёмами данных в информационном поиске, анализ дерева разборапрограммы в алгоритмах поиска клонов), а также в силу следующих особенностей документации ПО: небольшие (до 3 Мб) документы, необходимостьпринимать во внимание структуру документа (включая синтаксическую корректность XML-фрагментов для последующего повторного использования),осмысленность (meaningfulness) повторов, гарантия полноты выдачи при поиске.4.

Тем не менее, необходимо использовать готовые базовые средства поиска,чтобы облегчить решение задачи поиска повторов в документации и получитьвозможность сосредоточиться на вопросах применения найденных повторовпри разработке и сопровождения документации ПО. В качестве таких базовыхсредств, вслед за многими другими исследованиями повторов в документацииПО [76, 89, 110, 111, 145, 150], предлагается использовать методы поиска клонов в ПО, основанные на анализе текста (т.н.

token-based подход). В частности,выбран алгоритм и соответствующий программный инструмент CloneMiner [35].435. На данный момент существует несколько способов применения найденныхповтороввдокументацииПО—этоповторноеиспользова-ние [23, 76, 111, 112] и верхнеуровневый анализ качества документации[89, 150]. В то же время очевидно, что повторы могут использоваться в формировании шаблонов и рекомендаций для разработки документации, в частности, справочной документации, способствуя единообразию, унификации ицелостности текстов. В данном направлении в настоящий момент отсутствуютсоответствующие исследования.44Глава 2.

Алгоритм компоновки неточных повторов2.1. Модель неточных повторовЗадачей данного раздела является дать формальное определение неточного повтора. Рассмотрим документ как последовательность символов. Любой символдокумента имеет координату, соответствующую смещению символа от началадокумента, и эта координата является числом из интервала [1, length()], гдеlength() — это количество символов в .Определение 2.1.1.

Определим текстовый фрагмент документа как вхождение в документ некоторой строки символов. Таким образом, каждому текстовому фрагменту документа соответствует целочисленный интервал [, ], где — это координата первого символа фрагмента, — координата последнего.Будем обозначать как ∈ тот факт, что у нас имеется некоторый текстовыйфрагмент документа .Обозначим множество всех текстовых фрагментов документа как ∗ , множество всех целочисленных интервалов, входящих в интервал [1, length()] как , множество всех возможных символьных строк длины не больше length()как .Введём следующие обозначения.[]: ∗ → — функция, которая по текстовому фрагменту выдает егоинтервал.b(): D∗ → [1, length(D)] — функция, которая по текстовому фрагменту выдаёт начало его интервала.e(): D∗ → [1, length(D)] — функция, которая по текстовому фрагменту выдаёт конец его интервала.str(): ∗ → — функция, которая по текстовому фрагменту выдаетего текст.: → ∗ — функция, которая по интервалу выдает соответствующийему текстовый фрагмент.45|[, ]|: → [0, length()] — функция, которая по интервалу [] = [, ]выдает его длину, вычисляемую как |[]| = − + 1.

Для сокращениязаписи вместо |[]| будем писать ||.Для любых 1 , 2 ∈ их пересечение 1 ∩ 2 будем рассматривать какпересечение соответствующих интервалов [1 ] ∩ [2 ], под 1 ⊂ 2 будемподразумевать [1 ] ⊂ [2 ], под 1 ⊆ 2 — [1 ] ⊆ [2 ], под 1 \2 — разность [1 ] \ [2 ].Определим двухместный предикат Before на множестве ∗ × ∗ , которыйявляется истинным для двух текстовых фрагментов 1 , 2 документа тогда и только тогда, когда e(1 ) < b(2 ).Определение 2.1.2.

Пусть является набором текстовых фрагментов документа таких, что ∀1 , 2 ∈ ((str(1 ) = str(2 )) ∧ (1 ∩ 2 = ∅)). Такиефрагменты назовём точными повторами, а — группой точных повторовили точной группой. Посредством # будем обозначать количество элементовв .Определение 2.1.3. Для упорядоченного набора точных групп 1 , … , будемговорить, что этот набор образует вариативную группу ⟨1 , … ⟩, если выполняются следующие условия.1. #1 = ⋯ = # .2. Текстовые фрагменты, имеющие в разных группах одни и те же порядковые номера, следуют в исходном тексте в одном и том же порядке:∀ ∈ ∀ ∈ (( < ) ⇔ Before( , )), и∀ ∈ {1, … , − 1} Before( , 1+1 ).При этом будем писать, что для любой группа из этого набора справедливо ∈ .Замечание2.1.1.

Изусловия 2определения2.1.3следует,что∀ ∈ , ∀ ∈ ( ≠ ⇒ ∩ = ∅).46Замечание 2.1.2. Если = ⟨1 , … ⟩ и ′ = ⟨′1 , … ′ ⟩ являются вариативными группами, то ⟨, ′⟩ = ⟨1 , … , ′1 , … ′ ⟩ также является вариативной группой в том случае, если она удовлетворяет определению 2.1.3.Определение 2.1.4. Расстояние между текстовыми фрагментами. Длялюбых 1 , 2 ∈ определим расстояние следующим образом:0,1 ∩ 2 ≠ ∅,dist(1 , 2 ) = {b(2 ) − e(1 ) + 1, Before(1 , 2 ),b(1 ) − e(2 ) + 1, Before(2 , 1 ).(2.1.1)Определение 2.1.5.

Расстояние между точными группами 1 и 2 при условии, что #1 = #2 определим так:dist(1 , 2 ) =maxdist(1 , 2 )∈{1,…,#1 }(2.1.2)Определение 2.1.6. Расстояние между вариативными группами 1 и 2 ,при условии, что существуют 1 ∈ 1 , 2 ∈ 2 такие, что #1 = #2 , определим следующим образом:dist(1 , 2 ) =max1 ∈1 ,2 ∈2dist(1 , 2 )(2.1.3)Определение 2.1.7. Длина точной группы определяется следующим образом: length() = ∑#=1| | где ∈ .Определение 2.1.8.

Длина вариативной группы = ⟨1 , … , ⟩ определяется следующим образом:length() = ∑ length( )(2.1.4)=1Определение 2.1.9. Группа неточных повторов — это вариативная группа = ⟨1 , … , ⟩ такая, что ∀ ∈ {1, … , #1 } справедливо следующее:−1∑ dist( , +1) ≤ 0,15 ∗ ∑ | |.=1(2.1.5)=1Данное определение является формализацией понятия неточного повторав [37], где утверждается, что вариативная часть неточных повторов одной и той47же информации (delta) не должна превышать 15% их неизменной части (архетипа, archetype).Замечание 2.1.3.

Точная группа может быть рассмотрена как группа неточныхповторов, сформированных единственной группой ⟨⟩.Определение 2.1.10. Рассмотрим группу неточных повторов = ⟨1 , 2 ⟩,где 1 и 2 — точные группы. Будем считать, что содержит единственнуюточку расширения, а фрагменты текста, расположенные в интервалах [e(1 ) +1, b(2 ) − 1], назовём значениями точки расширения. В общем случае группанеточных повторов ⟨1 , … , ⟩ имеет − 1 точек расширения.Данное выше определение неточных повторов хорошо подходит к ситуации,когда неточные повторы строятся из точных. Однако могут использоваться идругие подходы к поиску. Кроме того, данное определение не предполагает вариаций текста на краю текстового фрагмента (левом и/или правом) – вариация(то есть точка расширения — см. определение 2.1.10) обязательно располагаетсямежду двумя фрагментами архетипа. Наконец, в этом определении зафиксировано отношение размера вариации к размеру архетипа.

Для того, чтобы снять всеэти ограничения, предложено следующее определение.Определение 2.1.11. Группа неточных повторов с мерой близости k. Пустьу нас имеется набор текстовых фрагментов 1 , … , документа . Будем называть этот набор группой неточных повторов с мерой близости (далее — группой неточных повторов), если выполнены следующие условия:1. ∀ Before ( , +1 )2. Существует упорядоченный набор строк 1 , … , такой, что имеетсявхождение этого набора в каждый текстовый фрагмент, то есть∀ ∈ {1, … , }∀ ∈ {1, … , } ⊂ str( ) ⋀ ∀ ′ ″ ∈ {1, … , } ( ′ < ″ ⇒ Before( ′ , ′′ )), где — вхождение в .3.

Число таково, что1√3< ≤ 1, и для него выполнено следующее условие:48∀ ∈ {1, … , }∑=1 | || |≥(2.1.1)Набор строк ⟨1 , … , ⟩ назовём архетипом данной группы неточных повторови будем обозначать .Замечание 2.1.1. Важно отметить, что нас не интересуют фрагменты с небольшой долей похожести (то есть когда близко к 0) — такие повторы, в основном,оказываются случайными, то есть, попадая в одну группу, они не имеют общейсемантики. Исходя из наших экспериментов, целесообразно рассматривать случай, когда > 1/2.

Значение1√3ненамного больше, чем ½ и удобно для после-дующих доказательств14.Замечание 2.1.2. Очевидно, что при > 1/2 не может быть больше одноговхождения архетипа в каждый текстовый фрагмент.Определение 2.1.12. Пусть у нас имеется группа неточных повторов с архетипом ⟨1 , … , ⟩. Тогда будем говорить, что данная группа имеет, как минимум,N − 1 точек расширения, которые являются формальными параметрами группыи располагаются в «разрывах» архетипа.

На место каждой точки расширенияможно вставить вариативный текст — значение точки расширения. Кроме того,группа неточных повторов может иметь одну или две дополнительные точки расширения, расположенные в начале/конце фрагмента и соседствующие с архетипом только с одной стороны (в этом заключается отличие данного определенияот определения 2.1.11).Приведём пример группы неточных повторов.

Характеристики

Список файлов диссертации