Диссертация (1149623), страница 8
Текст из файла (страница 8)
Два сходных фрагмента документации37Единое описание этих фрагментов при помощи языка DRL представлено налистинге 1.6.2.<infelement id="refresh_news">When module instance receives rfresh_newscall, it updates its data from<nest id="SourceType" /> feeds it is <nest id="SubscrType" /> to and pushesnew articles to the main storage.</infelement>Листинг 1.6.2. Единая спецификация двух сходных фрагментовВ этом описании в тех местах, где оба фрагмента различаются, вставлены формальные параметры.
При использовании этого описания надо заменить формальные параметры на фактические, как это показано на листинге 1.6.3.<infelemref infelemid="refresh_news"><replace-nest nestid="SourceType">RSS and Atom</replace-nest><replace-nest nestid="SubscrType">configured to listen</replace-nest></infelemref>…<infelemref infelemid="refresh_news"><replace-nest nestid="SourceType">Twitter</replace-nest><replace-nest nestid="SubscrType">subscribed</replace-nest></infelemref>Листинг 1.6.3. Повторное использование сходных фрагментовД.
Кознов и К. Романовский [8] описывают процесс разработки документациисемейства программных продуктов с применением рефакторинга12. Для документации семейств программных продуктов (software product lines) [13] ониопределяют рефакторинг как выделение общих активов из документации продукта и соответствующее изменение этой документации так, чтобы её фактиче-Рефакторинг программного обеспечения определяется М. Фаулером и К. Беком, как процессизменения программной системы, выполняемый таким образом, что внешнее поведение системы не изменяется, но при этом улучшается её внутренняя структура [65].1238ское содержание осталось неизменным.
Понятие рефакторинга важно для данного диссертационного исследования, поскольку позволяет найти формальноеприменение найденным в документации повторам. В рамках технологии DocLineбыл реализован первый прототип рефакторинга на основе автоматическинайденных повторах [23].Инструмент Clone MinerClone Miner [35] является инструментом поиска клонов в исходном коде программного обеспечения, основанным на токенах, а не на анализе синтаксического дерева программы, подобно другим клон-детекторам.
Инструмент реализован на языке C++ и использует основанный на суффиксных массивах [31] алгоритм поиска повторяющихся фрагментов текста.Clone Miner предоставляет удобный интерфейс командной строки, данные обобнаруженных точных повторах выдаются в текстовом файле. Инструмент поддерживает анализ русскоязычных текстов. Эти свойства позволяют легко интегрировать Clone Miner c другими программными средствами и эффективно использовать его в исследовательских целях.Утилита PandocPandoc [113] является инструментом для конвертации документов из однихформатов в другие. Утилита поддерживает 26 входных форматов и 47 выходных.Большинство поддерживаемых Pandoc форматов является легковесными языками разметки, но также он поддерживает форматы ROFF, HTML, DocBook, LaTeX, Microsoft Word, OpenOffice/LibreOffice Writer, EPub и т.д.
Форматированиерезультатов конвертации может настраиваться с помощью пользовательскихшаблонов. Кроме основного инструмента — конвертора — в программный пакеттакже входит генератор списков литературы, сходный с BibTeX и BibLaTeX.Утилита Pandoc предоставляет интерфейс командной строки, позволяющийзадавать большое количество опций конвертации, благодаря чему её удобно интегрировать с другим программным обеспечением.39Редакционное расстояниеПри работе с неточными текстовыми повторами актуальна задача определениястепени совпадения повторяющегося текста. Существуют различные определения степени близости (схожести) текстовых строк. Одним из них является редакционное расстояние между двумя строками, определяемое как минимальное количество операций редактирования, позволяющих получить одну строку из другой [72].
Существуют различные определения редакционного расстояния, отличающиеся набором операций редактирования. Расстояние Левенштейна [14] использует следующие операции: вставка символа, удаление символа замена одного символа на другой. Расстояние Дамерау-Левенштейна [54] в дополнение кпредыдущим трём операциям использует операцию взаимного перемещениядвух символов строки. Расстояние Хемминга [74] определяется для двух строкодинаковой длины с применением единственной операции — замены одногосимвола на другой. Расстояние по наибольшей общей подпоследовательностисимволов [41, 72, 97] использует операции вставки и удаления символа и, согласно [41], может быть вычислено следующей простой формулой:d(1 , 2 ) = |1 | + |2 | − 2|LCS(1 , 2 )|,где | | — длина строки в символах, а |LCS(1 , 2 )| — длина наибольшей подпоследовательности символов, встречающаяся в обеих строках.Если применять редакционное расстояние при поиске неточных повторов сотен символов, то потребуется вычислять его десятки и даже сотни тысяч раз.
Рассмотрим сложность вычисления различных видов редакционных расстояний.Сложность вычисления расстояний Левенштейна, Дамерау-Левенштейна, атакже расстояния по наибольшей общей подпоследовательности символов длястрок 1 и 2 при помощи известных алгоритмов [41, 143, 144] оценивается как(|1 | × |2 |) в худшем случае. Для расстояний Левенштейна и по наибольшей40общей подпоследовательности символов также показано, что более производительные алгоритмы в принципе не могут быть реализованы [29, 33]13.
Сложностьвычисления расстояния Хеммнига оценивается как (|1 |) = (|2 |), однакорасстояние Хемминга не позволяет работать со строками разной длины и не рассматривает операции вставки и удаления, что существенно для задач данного исследования. На основе экспериментов автора исследования с разными расстояниями оказалось, что данная сложность существенно влияет на быстродействиеалгоритмов поиска неточных повторов и требует оптимизации. Следует минимизировать количество и длины строк, расстояние между которыми требуетсявычислять, запоминать уже вычисленные значения расстояния, при возможности— вычислять их, опираясь на значения, уже вычисленные для других строк.
Вдальнейшем в данном исследовании использовано расстояния по наибольшейобщей подпоследовательности символов в силу удобства при выполнении доказательств.В [72] показано, что редакционное расстояние по наибольшей общей подпоследовательности (1 , 2 ) обладает метрическими свойствами: (1) d(, ) = 0,(2) ∀1 ≠ 2 : (1 , 2 ) = (2 , 1 ) > 0, и, наконец, (3) d(1 , 3 ) ≤ d(1 , 2 ) +d(2 , 3 ).Алгоритмы вычисления редакционного расстояния реализованы в различныхпрограммных библиотеках. Например, доступны библиотеки для языка Python,позволяющие вычислять расстояния Левенштейна [119] и Дамерау-Левенштейна [117].
Для C и C++ реализована библиотека вычисления расстояния понаибольшей общей подпоследовательности [134]. В данной работе для вычисления редакционного расстояния используется алгоритм нахождения наибольшейобщей подпоследовательности [123], реализованный в библиотеке difflib [118].Данная библиотека входит в стандартную поставку Python, а её части, критичныеПри допущении, что верна гипотеза об экспоненциальном времени, утверждающая, что задача выполнимости булевых формул не может быть решена за субэкспоненциальное время вхудшем случае [79].1341с точки зрения производительности, реализованы на языке C, что обеспечиваетвысокую скорость работы.Интервальное деревоИнтервальное дерево (interval tree) — это структура данных, которая позволяет для некоторого интервала числовой оси быстро находить в некоторомнаборе интервалов те, которые с ним пересекаются.
Первоначально интервальные деревья были созданы для решения задач вычислительной геометрии[42, 63, 116].Интервальное строится дерево следующим образом. Пусть у нас имеетсянабор из интервалов в натуральных числах, 1 — минимум, — максимумконцов всех интервалов, а — это середина интервала [1 , ]. Интервалы разделяются на три группы: целиком расположенные слева от , полностью расположенные справа от и содержащие . Текущий узел интервального деревахранит последнюю группу интервалов, а также ссылки на левый и правый дочерние узлы, которые хранят интервалы слева и справа от соответственно. Длякаждого дочернего узла процедура построения повторяется. Детальное описаниеалгоритмов построения и редактирования интервального дерева можно найти в[42, 116]. Там же описан алгоритм поиска по интервальному дереву.
Его средняявычислительная сложность оценивается как ( + log ), где — это количество интервалов в наборе, — количество интервалов, которые пересекаются сданным.В данном исследовании используется программная реализация интервальногодерева, выполненная Х.-Л. Халбертом (C.-L. Halbert) на языке Python [73].1.7. ВыводыНа основании сделанного обзора сделаем следующие выводы.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
