Диссертация (1149623), страница 11
Текст из файла (страница 11)
При этом основная проблема алгоритма заключается в том, что он не учитывает семантику повторов — например, даже включая в повторы осмысленный текст, алгоритм может добавлять кнему посторонние текстовые фрагменты. В связи с тем, что данное ограничениеявляется принципиальным (у автора диссертационной работы имеется скепсисотносительно возможности адекватного решения данной проблемы полностьюавтоматическим путём), было принято решение использовать предложенный алгоритм для первичного анализа документации на предмет наличия и состава неточных повторов с тем, чтобы принять организационные решения по дальнейшему сопровождению и доработке этой документации.
Но даже при таком ограничении на использование алгоритм должен удовлетворять дополнительномуусловию — обеспечить выдачу, обозримую для анализа человеком. «Обозримость для человека» является субъективным критерием, но выдачи для одногодокумента в несколько тысяч групп повторов, среди которых не более 15% являются существенными, делают алгоритм неприменимым на практике. В данномслучае мы готовы жертвовать полнотой (пусть алгоритм чего-то не найдёт) с тем,чтобы результаты его работы были обозримы. После анализа результатов работыалгоритма на документах из табл.
1.5.2 были сформулированы следующие численные эвристики:55 величина выдачи должна составлять не более нескольких сотен групп повторов для описательных документов и не более двух тысяч для справочных документов.Для того, чтобы выполнить это требование, были сформулированы следующие правила оптимизации.1. Исключить из выдачи точные группы, повторы которых пересекаются сповторами неточных групп. Если мы имеем две пересекающиеся точныегруппы, то надо исключить группу с наименьшей суммарной длиной повторов.2. Исключить из выдачи точные группы, включающие по два текстовыхфрагмента при условии, что эти текстовые фрагменты содержат не более 6слов.Первое правило достаточно очевидно, рассмотрим второе правило.
Оно мотивировано тем, что бо́льшая часть выдачи алгоритма приходится именно нагруппы из двух элементов с небольшой длиной текстовых фрагментов. При этомбольшинство таких групп попадает в один из следующих случаев: группа состоит из коротких фрагментов текста, нарушающих структуру документа: конец одного предложения и начало следующего (например, «isused. Fill in the»), несколько последних ячеек таблиц и фрагмент текста,непосредственно следующего за таблицей, подпись к рисунку (или заключительную часть подписи) и фрагмент текста сразу после подписи и т.д.; группа включает речевые обороты следующего вида: «doesn't need to be»,«you want to use the»; группа состоит из специальных терминов, например, «ALSA ver.0.5.x»,«USB 2.0 high speed»; такие группы были бы осмысленны, если бы содержали больше элементов.Исключение таких групп из выдачи алгоритма сделает её существенноменьше, в то время как содержательной информации в таких группах немного, иона полезна лишь при детальном анализе повторов.56Предложенные правила оптимизации были реализованы.
В табл. 2.3.1 показано количество групп в выдаче алгоритма до и после оптимизации.Табл. 2.3.1. Результаты оптимизации№Документ1 DocBook definitive guide2 Subversion Book3 Zend Framework V1 guide4 Linux Kernel Documentation5 GNU Core Utils Manual6 Postgre SQL Manual7 The GIMP user manual8 Blender reference manual9 LibLDAP Manual10 Eclipse SWT Reference11 Python Requests12 Qt Quick Reference13 Документ 114 Документ 215 Документ 316 Документ 417 Документ 518 Документ 619 Документ 7В среднемГрупп в выдачеДоПослеоптимизации оптимизации1500382421910546058179612933934683172524389597800202665872221152714539177059332829640814420873117413941721577727145431471686Реализованные оптимизации увеличили время работы алгоритма в среднем на2,5 секунды, то есть оставили его приемлемым.Несмотря на то, что представленный алгоритм обладает приемлемыми характеристиками, он игнорирует семантику выделяемых повторов, что оказываетсяважным для практических применений.57Глава 3.
Методика интерактивного поиска неточных повторовВ данной главе излагается методика интерактивного поиска, которая предложена для решения вопроса о поиске семантически осмысленных неточных повторов. Основная идея методики заключается в решении данного вопроса с помощью интерактивности, то есть на основе взаимодействия с пользователем. Таким образом, при анализе документации пользователю предлагается принять решение о том, какая информация является семантически значимой: пользовательформирует образец для поиска, и специальный алгоритм находит все неточныеповторы данного образца в документе.
Далее пользователь редактирует полученную выдачу, выбирает новый образец и так далее.3.1. Описание методикиСхема методики представлена на рис. 3.1.1.ДокументацияГенерация картыповторовВыбор образца дляпоискаГруппы неточныхповторовФормированиегруппы неточныхповторовПоиск неточныхповторовРис. 3.1.1. Методика интерактивного поиска неточных повторовНа первом шаге («Генерация карты повторов») для выбранного документастроится карта повторов. Для этого с помощью Clone Miner в документе ищутсявсе точные повторы длиной не менее пяти токенов15.
Затем для каждого токена вдокументе вычисляется максимальная мощность группы повторов, в которую онвходит (для токена, не входящего ни в одну точную группу, элементы которойОпытным путём было установлено, что минимальное значение длины точного повтора впять токенов как правило позволяет достичь наибольшей наглядности карты повторов.1558состоят не менее чем из пяти токенов, это значение оказывается равным нулю).Далее, каждой группе повторов ставится в соответствие трехкомпонентныйвектор: =#∗ Red + (1 −#) ∗ White, где = max # — максималь∀ная мощность групп точных повторов (не менее чем с пятью токенами), Red =[1, 0, 0], White = [1, 1, 1].
В цветовой модели RGB16 вектора Red и White соответствуют красному и белому цвету. Известно, что с помощью выпуклой линейной комбинации для пары векторов, соответствующих паре цветов в моделиRGB, строится смешанный цвет [64]. Таким образом, меняя коэффициенты выпуклой комбинации от 0 (# = 0) до 1 (# = ), получаем набор векторов, соответствующий палитре оттенков красного цвета от белого до чистого красного[1, 0, 0]. Соответственно, группы с большой мощностью получают более красный цвет, с меньшей — менее красный. В соответствии с этим каждому токенув документе присваивается цвет.
Таким образом, весь документ оказывается«раскрашенным» в красный цвет разной насыщенности в зависимости от того,насколько часто те или иные фрагменты повторяются. Описанный способ визуализации называется тепловой картой (heat map) [136]. Пример тепловой картыдля документа PostgreSQL Manual из табл. 1.5.1 представлен на рис. 3.1.2.Рис.
3.1.2. Пример тепловой карты для документа PostgreSQL ManualRGB — аддитивная цветовая модель, используемая при выводе изображений на экраны современных электронных устройств [64]. Единица в соответствующей компоненте означаетмаксимальную интенсивность красного, зелёного или синего цвета, ноль — минимальной.1659Рис. 3.1.3. Карта повторов в тексте документаРис. 3.1.4.
Пример выбранного пользователем фрагмента для поискаНа втором шаге («Выбор образца для поиска») пользователь находит на тепловой карте (визуально, вручную) самое насыщенное повторами место (оно оказывается самым красным) и увеличивает его, получая карту повторов. На этойкарте, в отличие от тепловой карты, уже имеется текст. Для самой нижней яркокрасной области с рис. 3.1.2 получаем текст, изображённый на рис. 3.1.3. Затемпользователь выбирает на карте повторов некоторый фрагмент текста в качествеобразца для поиска, как показано на рис. 3.1.4.Следует отметить, что выбранный фрагмент обладает семантической замкнутостью, то есть полностью описывает самостоятельный факт, связанный с СУБДPostgreSQL: для того, чтобы пользователь мог сменить владельца таблицы базыданных, ему требуется обладать специфическими правами или быть администратором.
Подобным образом пользователь может оформить в качестве образца дляпоиска целостное описание некоторой программной сущности, атрибута, свойства, шага в процессе и т.д., причём включить в образец те фрагменты такого60описания, которые имеют белый цвет на карте повторов. Эти «белые пятна» могут быть вариациями данного образца — в неточных повторах образца им можетсоответствовать другой текст, который был изменён при copy/paste данногофрагмента при разработке документа.Далее пользователь запускает для выделенного фрагмента (рис. 3.1.4) алгоритм поиска по образцу (рис.
3.1.1, «Поиск неточных повторов»). Результатомработы алгоритма является набор текстовых фрагментов, похожих на выделенный образец с выбранной мерой близости (число от1√3до 1). После этого поль-зователь переходит к следующему шагу.На этом шаге («Формирование группы неточных повторов») пользователь редактирует полученную выборку. Прежде всего, он удаляет из неё те элементы,которые похожи на образец только синтаксически, но не семантически. Такаяситуация часто происходит, если взято достаточно далёким от 1. Кроме этогопользователь может корректировать границы фрагментов.Так, например, на основании образца, выделенного на рис. 3.1.4 синим цветом,наш алгоритм нашёл неточный повтор, представленный на листинге 3.1.1. (полный список повторов данного образца представлен в Приложении):alter the owner, you must also be a direct or indirect member of the new owning role,and that role must have CREATE privilege on the materialized view's schema.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
