Диссертация (1149623), страница 10
Текст из файла (страница 10)
На листинге 2.1.1 представленшаблон для описания фрагмента функциональности графического редактора посозданию новой диаграммы, которому соответствует описания пяти однотипныхредакторов (данный пример взят из руководства пользователя промышленной14Значение 15% в определении 2.1.9 группы неточных повторов соответствует = 0,87 и попадает в интервал1√3< ≤ 1.49системы визуального моделирования). Функциональность по созданию новойдиаграммы у всех редакторов одинаковая с точностью до названий диаграмм ипапок. В местах различий в данном шаблоне находятся точки расширения, представленные открывающими/закрывающими треугольниками с номером точкирасширения.В папке Объекты нужно выбрать бизнес-решение, которое предполагается моделировать.
Для него правой кнопкой мыши нужно вызвать всплывающее меню,в нем выбрать пункт Детализации, как показано на рис. ◀1◀ ▶1▶. Далее в окнеСвойства в разделе Детализации необходимо нажать на кнопку Новый, как показано на рис. ◀2◀ ▶2▶. После этого в появившемся окне Мастер детализациинеобходимо выбрать тип модели ◀3◀ ▶3▶ бизнес-решения, как показано на рис.◀4◀ ▶4▶, нажать кнопку Далее.
После этого, в появившемся окне следует выбратьпапку для сохранения ◀5◀ ▶5▶ бизнес-решения. Внимание! В качестве папки длясохранения нужно выбрать папку Модели, в ней папку вашего бизнес-решения,далее ◀6◀ ▶6▶, а в ней папку ◀7◀ ▶7▶.Листинг 2.1.1. Описание функциональности по созданию диаграммНа листинге 2.1.2 представлено описание процесса создания новой диаграммыопределённого типа (диаграммы бизнес-решения).
Это описание создано на базешаблона из листинга 2.1.1, в точки расширения которого вставлены соответствующие значения, выделенные жирным. Таким образом, Листинг 2.1.1 задаётгруппу неточных повторов с семью точками расширения, количество элементовв этой группе — 5, мера близости этой группы равна 0,83.В папке Объекты нужно выбрать бизнес-решение, которое предполагается моделировать. Для него правой кнопкой мыши нужно вызвать всплывающееменю, в нем выбрать пункт Детализации, как показано на рис. 7. Далее в окнеСвойства в разделе Детализации необходимо нажать на кнопку Новый, как показано на рис.
8. После этого в появившемся окне Мастер детализации необходимо выбрать тип модели диаграмма бизнес-решения, как показано на рис. 9,нажать кнопку Далее. После этого, в появившемся окне следует выбрать папкудля сохранения диаграммы бизнес-решения. Внимание! В качестве папки длясохранения нужно выбрать папку Модели, в ней папку вашего бизнес-решения,далее Функционально-компонентная архитектура, а в ней папку Архитектура бизнес-решения.Листинг 2.1.2. Пример описания создания диаграммыдля конкретного графического редактора50Утверждение 2.1.1.
Пусть у нас имеется группа неточных повторов в смыслеопределения 2.1.9. Тогда она будет также группой неточных повторов в смыслеопределения 2.1.11.Доказательство этого утверждения очевидно. Обратное утверждение не выполняется, поскольку, неточная группа повторов в смысле определения 2.1.11может начинаться и или заканчиваться вариативным текстом, а в смысле определения 2.1.9 — нет, кроме того, константа может быть слишком мала, чтобысоответствовать константе 15% из определения 2.1.9.2.2. Описание алгоритма и доказательство его корректностиДадим несколько дополнительных определений.Определение 2.2.1.
Рассмотрим две группы неточных повторов =⟨1 , … , ⟩ и ′ = ⟨′1 , … , ′ ⟩. Предположим, что они могут образовать вариативную группу ⟨1 , … , , ′1 , … , ′ ⟩ или ⟨1 , … , , ′1 , … , ′ ⟩, которая такжеявляется группой неточных повторов.
В этом случае будем называть и ′ соседними группами.Определение 2.2.2. Соседние повторы — это текстовые фрагменты, принадлежащие соседним группам.Следуя замечанию 2.1.3, определение 2.2.2 применимо как к точным, так и кнеточным повторам.Далее представлен алгоритм, который ищет по множеству точных групп документа (множество ) множество групп неточных повторов (множество). Алгоритм использует интервальное дерево [42, 116]. Множество создаётся с помощью Clone Miner. Основная идея алгоритма — находить и соединять соседние группы из и добавлять получающиеся группы неточныхповторов в .
Спецификация алгоритма представлена на листинге 2.2.1.51/∗ — Входные данные/∗ — Результат1 ← ∅2 Initiate()3 repeat4 ← ∅5for each ∈ ∪ 6 ← NearBy()7if ≠ ∅8′ ← GetClosest(, )9Remove(, ′) /* Удаление и ′ из и S10if Before(, ′)11 ← ∪ {⟨, ′ ⟩}12else13 ← ∪ {⟨ ′ , ⟩}14Join(, )15 until = ∅16 ← ∪ Листинг 2.2.1. Алгоритм компоновки неточных повторовПри помощи функции Initiate() строится исходное интервальное дерево длямножества (строка 2). Основаная часть алгоритма является циклом, в котором производится выбор новых групп неточных повторов (строки 3–15).
Циклповторяется, пока на очередном шаге множество новых найденных групп неточных повторов не окажется пустым (строка 15). Внутри этого цикла алгоритм перебирает все группы из ∪ , и для каждой из них функцияNearBy возвращает множество близкорасположенных к ней групп (строки 5, 6), которые затем используются для конструирования нtточных групп.Ниже эта функция описана детально.
Также доказывается её корректность, тоесть тот факт, что она действительно возвращает группы, соседние с . Затем из выбирается ближайшая к группа ′ (строка 8) и создаётся вариативная группы ⟨, ′⟩ или ⟨′, ⟩, которая добавляется в (строки 10–14). Поскольку ′ и объединяются, и, таким образом, прекращают самостоятельное52существование, они удаляются из множеств и при помощи функцииRemove (строка 9). Затем функция Join добавляет к (строка 14).Функции Remove и Join также выполняют некоторые вспомогательные действия, описанные ниже.
В самом конце множество объединяется с множеством и представляется в виде итога работы алгоритма. Данное объединение выполняется для того, чтобы итоговый результат содержал не только группынеточных повторов, но также и те точные группы, которые не были использованы для комбинации неточных повторов (строка 16). Опишем функции, которые используются в алгоритме.Функция Initiate() строит интервальное дерево по точным повторам, найденным Clone Miner (детали построения интервального дерева можно найтив [42, 116]). Мы строим интервальное дерево из расширенных интервалов, которые получаются из точных следующим образом.
Мы расширяем на 15% интервалы, соответствующие точным повторам: если [, ] является исходным интервалом, то расширенный интервал выглядит так: [ − 0,15 ∗ ( − + 1), +0,15 ∗ ( − + 1)]. Расширенный интервал, соответствующий точному повтору, обозначим ↕ . В узле интервального дерева сохраняется также ссылка нагруппу точных повторов, которой он принадлежит.Функция Remove удаляет группы из множеств, а все их интервалы — из интервального дерева. Реализованный в этой функции алгоритм удаления из интервального дерева описан в [42, 116].Функция Join, в дополнение к описанным выше действиям, добавляет в интервальное дерево интервалы для вновь созданной группы неточных повторов =⟨1 , … , ⟩. При этом использован описанный в [42, 116] стандартный алгоритмвставки.
Расширенные интервалы, добавляемые в дерево, для каждого неточногоповтора = (1 , . . . , ) выглядит следующим образом: [b(1 ) − , e( ) +−1 ], где = 0,15 ∗ ∑=1 | | − ∑=1 dist( , +1 ). Расширенный интервал, со-зданныйнаосновенеточногоповтора,такжебудемобозначать ↕ .53Функция NearBy для некотрой группы (своего аргумента) выбирает соседние с ней группы. В связи с этим для каждого текстового фрагмента из ищетсянабор интервалов, пересекающихся с интервалом этого текстового фрагмента.При этом те текстовые фрагменты, которые соответствуют этим интервалам,оказываются соседними по отношению к данному, то есть для них выполненоусловие (2.1.5). Поиск выполняется при помощи алгоритма поиска по интервальному дереву [42, 116].
Сначала cтроится множество групп 1 , являющихся претендентами на то, чтобы быть группами, соседними с :1 = {′|(′ ∈ ∪ ) ∧∃ ∈ , ′ ∈ ′: ↕ ∩↕ ′ ≠ ∅.(2.2.2)То есть множество 1 сосоит из тех групп, в которых хотя бы один повторнаходится близко к какому-нибудь повтору из . Затем из этих групп выбираются только те, которые могут составить вариативную группу с ; эти группыпомещаются в множество 2 :2 = {′|′ ∈ 1 ∧ (⟨, ′⟩или⟨ ′ , ⟩ — вариативнаягруппа)}.(2.2.3)Наконец, строится множество 3 (результат работы функции ), кудапомещаются только те группы из 2 , в которых все элементы близки к соответствующим элементам :3 = {′|′ ∈ 2 ∧∀ ∈ {1, … , #}: ↕ ∩↕ ′ ≠ ∅}(2.2.4)Теорема 2.2.1.
Предложенный алгоритм обнаруживает группы неточных повторов, которые соответствуют определению 2.1.9.Доказательство. По построению функции NearBy легко показать, что длягруппы — своего аргумента — она возвращает множество соседних с нейгрупп (см. определение 2.2.1). То есть каждая из этих групп может вместе с сформировать неточную группу, и далее алгоритм выбирает из этого множестваближайшую к группу и конструирует новую неточную группу.
Корректностьвсех промежуточных множеств, а также других используемых функций напрямую следует из способа их построения. ■542.3. Эксперименты и оптимизацииБыли проведены эксперименты с документами из табл. 1.5.2. Экспериментыпроводились на компьютере с процессором Intel Core i7 2600 (тактовая частота3,4 ГГц, кэш 8 Мб) и 16 Гб ОЗУ.На рассмотренных документах алгоритм работал в среднем 73 секунды, илишь для одного крупного документа объёмом более 2 Мб время его работы оказалось больше 5 минут. Эти результаты оказываются приемлемыми для практического применения.С другой стороны, было установлено, что алгоритм выдаёт очень много ложноположительных срабатываний (около 85%).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
