Диссертация (1149623), страница 14
Текст из файла (страница 14)
Делается следующее. Множество 3 разбивается на максимальные, транзитивно замкнутые по пересечению, подмножества. Для каждого такого подмножества выбирается фрагмент 3 с наименьшим значениемd (3 , ), а в случае наличия нескольких таких — фрагмент с наибольшей длиной, то есть наилучший из перекрывающихся определяется с использованиемопределённой выше функции Compare (3.2.1). Остальные фрагменты из множества 3 удаляются.Оптимизация 4 применяется на фазе 3 и производит расширение всех текстовых фрагментов 3 до целых слов.
Другими словами, начало и конец текстовогофрагмента могут нарушать границу слова, и в этом случае границы текстовогофрагмента соответственно «раздвигаются» с тем, чтобы включить в себя этислова целиком.После реализации оптимизаций алгоритм был проверен на тех же тестах, чтои до оптимизации. Результаты представлены на рис. 3.4.1 и 3.4.2.75Рис. 3.4.1. Результаты оптимизации алгоритма поискапо образцу: время поиска в среднем по документам700Размер выдачи600500400До оптимизации300После оптимизации20010002030405060708090100Размер образца (в символах)Рис. 3.4.2.
Результаты оптимизации алгоритма поискапо образцу: размер выдачи в среднем по документамОптимизация сократила время поиска в среднем до 14 секунд, то есть в 31,75раз. Максимальное время поиска составило две минуты18. Отметим, что при по-Дальнейшее ускорение программной реализации алгоритма возможно при помощи распараллеливания фаз 1 и 2.1876иске по образцам размером более 300 символов время работы алгоритма не увеличивалось, т.к. настолько длинные фрагменты текста не повторялись многократно. Средний размер выдачи до оптимизации составлял 231, а после оптимизации стал равен 44, то есть сократился в 5,25 раз. Для образца, по которому алгоритм без оптимизации выдавал 13056 повторов (это пример обсуждался выше),после оптимизации алгоритм выдаёт 1012 повторов. В ходе экспериментов былиполучены следующие результаты (ниже приводятся данные анализа совокупнойвыдачи по всем тестам для алгоритма с оптимизациями).1.
У 60,8% выдачи присутствует по 1–2 «лишних» токенов в начале или вконце. У 0,1% выдачи в случае отличий повторов от образца близко кначалу или концу повторов, начало и конец были потеряны. Эти проблемылегко решаются пользователем при редактировании результатов работыалгоритма.2. При поиске по коротким образцам (3–4 токена) в отдельных случаяхнайденные повторы встречались в контексте, отличающемся от контекстаисходного образца. Такие фрагменты можно назвать сематическими ложными срабатываниями, но наша методика не претендует на автоматический отсев таких случаев: осмысленность повторов достигается точностьювыбора образца, а также возможностью пользователя удалить неосмысленные фрагменты из выдачи «вручную».3. Ни для одного фактически присутствующего повтора не выдавалось по нескольку вариантов, все результаты перекрывались с повторами более (всреднем существенно более), чем на 3/4 длины образца (при (0,87) ≈0,73||, то есть результаты оказались лучше теоретической оценки).Таким образом, после применения оптимизации алгоритм удовлетворил требованиям, сформулированным выше, как по времени поиска, так и по размеру/составу выдачи.
Итак, можно сделать вывод о готовности алгоритма и методики для практического использования.Покажем теперь, что представленные выше оптимизации сохраняют полноту.Вначале докажем два свойства редакционного расстояния d .77Утверждение 3.4.1. Если 1 , 2 , , — строки, причём || = || = 1 (строки изодного символа), то |d (1 , ∘ 2 ) − d (1 , 2 ∘ )| ≤ 2.19Таким образом, применительно к алгоритму, если сдвинуть окно на одинсимвол, то для нового положения окна ′ изменение редакционного расстоянияне превысит 2: |d (, ) − d (, ′ )| ≤ 2.Доказательство.
Для произвольной строки очевидно, что d (, ∘ ) =d (, ∘ ) = 1, т.к. добавление одного символа в начало или в конец одной изстрок соответствует всего одной операции редактирования.Покажем теперь, что для любых строк 1 и 2 справедливо |d (1 , ∘ 2 ) −d (1 , 2 )| ≤ 1. Поскольку расстояние d обладает метрическими свойствами,для него выполняется неравенство треугольника, то есть d (1 , ∘ 2 ) ≤d (1 , 2 ) + d (2 , ∘ 2 ) = d (1 , 2 ) + 1. Следовательно, d (1 , ∘ 2 ) −d (1 , 2 ) ≤ 1. Также неравенство треугольника для d позволяет утверждатьd (1 , ∘ 2 )−d (1 , 2 ) ≤ (d (1 , 2 ) + d (2 , ∘ 2 )) − d (1 , 2 ) =d (2 , ∘ 2 ) = 1,тоесть|d (1 , ∘ 2 ) − d (1 , 2 )| ≤ 1.Аналогично|d (1 , 2 ) − d (1 , 2 ∘ )| ≤ 1.Поскольку редакционное расстояние — целое неотрицательное число, то дляразности его значений также выполняется неравенство треугольника, следовательно: |d (1 , ∘ 2 ) − d (1 , 2 ∘ )| ≤ |d (1 , ∘ 2 ) − d (1 , 2 )| +|d (1 , 2 ) − d (1 , 2 ∘ )| ≤ 1 + 1 = 2.
■Утверждение 3.4.2. Пусть имеется два текстовых фрагмента 1 , 2 ∈ . Еслипри этом |b(1 ) − b(2 )| < и |1 | = |2 |, то для любой строки справедливо: |d (, 1 ) − d (, 2 )| < 2.Доказательство. Пусть b(1 ) < b(2 ). Будем сдвигать 1 вправо посимвольно, пока он не совпадёт с 2 . Пусть у нас имеется два соседних положения1 : и +1 , то есть b( ) + 1 = b( +1 ). Тогда очевидно, что существуютстроки и : || = || = 1 и str( ) ∘ = ∘ str( +1 ). Тогда, согласно19Здесь и далее при помощи 1 ∘ 2 будем обозначать результат конкатенации строк 1 и 2 .78утв. 3.4.1, |d (, ) − d (, +1 )| ≤ 2. В итоге мы можем утверждать, что понеравенству треугольника для разности целых чисел справедливо |d (, 1 ) −b( )−b(1 )d (, 2 )| ≤ ∑=12|d (, ) − d (, +1 )| < 2,т.к.|b(1 ) −b(2 )| < .Аналогично утверждение доказывается для случая b(1 ) > b(2 ).В случае b(1 ) = b(2 ) фрагменты совпадают, и справедливость утверждения очевидна.
■Теорема 3.4.1. В результате применения оптимизаций 1, 2, 4 сохраняется свойство полноты алгоритма.Доказательство. Рассмотрим оптимизацию 1. На первой фазе (сканирование)мы имеем положение окна , для которого в случае d (, ) > + 1 следующее положение сканирующего окна вычисляется как смещениевправо на = (d (, ) − )/2 символов.Покажем, что для ∀ ′ : | ′ | = || ∧ b() < b( ′ ) < b() + справедливоd ( ′ , ) > , то есть по описанию фазы 1 ′ нельзя поместить в 1 .
Из этогоутверждения будет следовать, что при скачке на символов вправо мы не потеряем ни одного элемента 1 .Действительно, b() < b( ′ ) < b() + ⇒ |b() − b( ′ )| < . Тогда, согласно утверждению 3.4.2, справедливо d (, ) − d (, ′ ) < 2. Но поскольку = (d (, ) − )/2, то выполняется d (, ) − d (, ′ ) <d (, ) − . Следовательно, d ( ′ , ) > , т.е.
по построению фазы 1фрагмент ′ не может быть элементом 1 .Доказательство полноты для оптимизации 2 аналогично доказательству дляоптимизации 1.Рассмотрим оптимизацию 4. Ее использование лишь расширяет фрагменты вфинальной выдаче, и это действие не может повлиять на полноту результата.
■Замечание 3.4.1. Возможны ситуации, когда оптимизация 3 нарушает критерий полноты. Например, если текст документа — «abc abc abc abc», образец —79«abc abc» то при любом в результате оптимизации 3 алгоритм выдаст единственное вхождение образца в текст, в то время как образец входит в текст документа дважды (согласно определению 2.1.11 неточные повторы не пересекаются). Тем не менее, результаты апробации показывают, что потеря значимыхэлементов в выдачах алгоритма на практике происходит только в случаях наличия близко расположенных повторов, при этом даже в этих случаях это происходит очень редко.80Глава 4. Метод улучшения документации на основе неточных повторовВ этой главе описывается метод улучшения документации на основе неточныхповторов.
Данный метод позволяет работать с документацией любого характера,но наибольшего эффекта позволяет достичь при работе со справочной документацией (API-документами, руководствами пользователя и т.д.). Документы этоговида помогают уже знакомому с предметом читателю установить конкретныефакты и не предназначены для чтения целиком [114]. Описывая наборы однотипных сущностей, таких как функции, классы, элементы графического интерфейса и т.д., справочная документация должна быть как можно более однородной.
Вследствие этого она неизбежно включает в себя много повторов. На практике технический писатель обычно имеет дело с документами, которые требуютулучшений в смысле однородности. Для этого ему(ей) приходится выявлять неточные повторы, анализировать их и вносить в документацию правки, повышаяеё ясность и чёткость, целостность и однозначность.4.1. Описание методаПоскольку само ПО часто меняется (появляется новая функциональность, изменяется интерфейс пользователя, исправляются ошибки и т.д.), то его документация также требует соответствующих обновлений.
В то же время, документациятребует изменений, не связанных с изменениями программного обеспечения:необходимо исправлять ошибки, реструктурировать документацию и приводитьеё к единообразному виду, изменять её в связи с внедрением новых инструментов и технологий работы с документацией и т.д. В качестве отрицательного примера можно привести документацию ядра ОС Linux, которую в данный моментактивно улучшают и конвертируют в новые форматы [51]. Ниже мы определимметод улучшения документации на основе неточных повторов и покажем, какимобразом он может быть применён на практике.811ДокументацияАвтоматическийпоиск повторов2Анализ повтороввручнуюИсправления вдокументацииРекомендациипо написаниюдокументацииУлучшеннаядокументация3Повторноеиспользование,рефакторингОсмысленныепереиспользуемыефрагменты текстаРис.
4.1.1. Схема метода улучшения документацииОпределение 4.1.1. Управление повторами в документации — это процессобнаружения и анализа повторов с целью исправления ошибок и достиженияединообразия документации, в ходе которого могут применяться техники повторного использования.Предлагаемый метод улучшения документации основывается на управленииповторами и состоит из несколько фаз — см. рис. 4.1.1.Первая фаза — автоматическое обнаружение повторов, как точных, так и неточных.
Здесь применяются подходы и техники, описанные в предыдущих главах.Вторая фаза — «ручной» анализ повторов и внесение изменений в документацию. С одной стороны, автоматизированный поиск повторов выдаёт значительную долю ложноположительных несодержательных срабатываний [89]. С другой стороны, даже обнаруженные содержательные повторы зачастую не являются корректными: они нарушают структуру документа и не обладают смысловой замкнутостью. Для того, чтобы решить эти проблемы, к анализу в интерактивном режиме привлекается пользователь. С другой стороны, повторы, обнаруженные автоматически, должны быть проанализированы вручную для того,чтобы внести в документацию правки, исправляющие ошибки и повышающие её82единообразие.
Найденные повторы содержат много информации, полезной длярешения этих задач. После того, как документация исправляется и унифицируется, повторный поиск обнаруживает ещё большее количество повторов. На выходе второй фазы мы имеем набор осмысленных групп повторов.Третья фаза — использование найденных повторов. Прежде всего, это автоматизированный рефакторинг для документации в формате DocBook, переиспользование текста на основе найденных повторов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
