Диссертация (1149623), страница 12
Текст из файла (страница 12)
(Theserestrictions enforce that altering the owner doesn't do anything you couldn't do by dropping and recreating the materialized view. However, a superuser can alter ownership ofany view anyway.)Листинг 3.1.1. Неточный повтор, найденный по образцуПользователь расширил начало этого повтора, получив текстовый фрагмент,представленный на листинге 3.1.2.To 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.
(Theserestrictions enforce that altering the owner doesn't do anything you couldn't do by droppingand recreating the materialized view. However, a superuser can alter ownership of anyview anyway.)Листинг 3.1.2. Откорректированный пользователем неточный повтор61Аналогично можно сдвинуть и правую границу фрагмента. Полные результаты поиска по образцу и результаты их коррекции пользователем приведены вПриложении. Всего в документе PostgreSQL Manual для данного образца содержатся 13 неточных повторов. Они отличаются тем, что в них описываются привилегии, необходимые для манипуляции с различными сущностями схемы базыданных: таблицами, представлениями, хранимыми функциями и т.д.
Так фрагмент текста на листинге 3.1.1 отличается от образца с рис. 3.1.4 тем, что в нёмтокен «table» заменён на токен «view», то есть последний фрагмент описываетте же самые требования к правам, и содержит такие же оговорки, что и в предыдущем фрагменте, но уже применительно к смене владельца представления, а нетаблицы.3.2. Алгоритм поиска по образцуВ этом разделе описывается созданный алгоритм поиска по образцу, применяемый в представленной методике. Дадим в начале несколько определений.Определение 3.2.1. Неточные повторы текстового фрагмента. Пусть унас имеется некоторый текстовый фрагмент документа , то есть ∈ .
Пустьимеется также ∈ . Будем говорить, что является неточным повтором сточностью , если и вместе образуют группу неточных повторов с точностью в смысле определения 2.1.11. Будем говорить о нескольких неточных повторах фрагмента с точностью , если все эти текстовые фрагменты вместе с образовывают группу неточных повторов с точностью . Будем говорить, чтогруппа является группой неточных повторов некоторого фрагмента с точностью , если ∈ и является группой неточных повторов с точностью .Определение 3.2.2. Будем далее в этой работе понимать под редакционнымрасстоянием между двумя строками минимальное суммарное количество вставок и удалений символов, позволяющее преобразовать первую строку во вторую[41, 97]. Пусть 1 и 2 являются некоторыми строками символов.
Будем обозначать редакционное расстояние между ними как d (1 , 2 ) (индекс обозначаетоперации удаления и вставки — delete и insert). Редакционное расстояние для62текстовыхфрагментов1 , 2 ∈ определимкакd (1 , 2 )=d (str(1 ), str(2 )).Нам требуется создать алгоритм, который ищет в документе неточные повторы некоторого выделенного текстового фрагмента (далее — образца).
Приэтом важно, чтобы были найдены все неточные повторы с некоторой точностью. Допустимо, чтобы алгоритм выдавал дополнительно некоторое количество ложноположительных срабатываний. Предполагается, что пользователь может легко скорректировать результат, поскольку в документации программногообеспечения группы неточных повторов относительно невелики: исходя из экспериментов, выполненных автором диссертационного исследования на реальных промышленных документах, количество элементов в семантически осмысленных группах обычно не превосходит 10 и редко превосходит 50.
То есть общее количество элементов, выдаваемое пользователю для анализа, исчисляетсядесятками, а не сотнями и тысячами.Спецификация алгоритма приведена на листинге 3.2.1. На вход алгоритм получает документ , текстовый фрагмент этого документа — образец для поиска, константу — меру близости неточных повторов:1√3< ≤ 1. Результатомалгоритма является множество текстовых фрагментов , которое содержит неточные повторы фрагмента в документе .63/∗ , , — Входные данные/∗ — Результат1 1 ← ∅/* начало фазы 1 (сканирование)2 for ∀ 1 : 1 ∈ ∧ |1 | = 3if d (1 , ) ≤ 4add 1 to 15 2 ← ∅/* начало фазы 2 («усушка»)6 for ∈ 172′ ← 8for ∈ 9for ∀2 : 2 ⊆ ∧ |2 | = 10if Compare(2 , 2′ , )112′ ← 212add 2′ to 213 3 ← Unique(2 )/* начало фазы 3 (фильтрация)14 for 3 ∈ 315if ∃3′ ∈ 3 : ⊂ 3′16remove 3 from 317 ← 3Листинг 3.2.1.
Алгоритм поиска по образцуАлгоритм разбит на следующие фазы. На фазе 1 (сканирование) текст документа сканируется окном длины =||с шагом в один символ17; текстовыйфрагмент, соответствующий текущему положению окна, сравнивается с образцом по редакционному расстоянию, и если они близки, то этот фрагмент сохраняется в множестве 1 . На фазе 2 («усушка») производится поиск наибольший фрагмент текста внутри каждого элемента из множества 1 , максимальнопохожего на образец . Таким образом происходит «усушка» элементов из 1 ,то есть у них уменьшается длина.
Это целесообразно, поскольку окно имеет максимально возможный размер, который может иметь неточный повтор фрагментаЗдесь и далее не выполняется округление до целого, поскольку все рассуждения и доказательства могут быть легко повторены с учётом этого замечания, а явное обозначение округления загромождает формулы.1764 (см. утв. 3.3.1), то есть все элементы множества 1 имеют максимально возможный размер. Результатом работы этой фазы является множество 2 . Нафазе 3 (фильтрация) из множества 2 удаляются одинаковые элементы (онипоявляются на предыдущей фазе в силу того, что в 1 могут попадать текстовыефрагменты, отличающиеся друг от друга на сдвиг окна в несколько символов), атакже удаляются элементы, полностью входящие в другие элементы 2 .
Итогом этой фазы является множество 3 , которое оказывается результатом действия алгоритма, то есть множеством .Опишем теперь функции, использованные в представленном на листинге 3.2.1алгоритме. Функция Compare используется на фазе 2 для того, чтобы выяснить,какой из двух фрагментов текста является максимально близким к образцу всмысле редакционного расстояния; если оба текстовых фрагмента имеют равноередакционное расстояние от образца, то они сравниваются по количеству символов (то есть нас интересуют максимально большие повторы):true,если d (1 , ) < d (2 , )если d (1 , ) > d (2 , )Compare (1 , 2 , ) = { false,|1 | > |2 |, если d (1 , ) = d (2 , ).(3.2.1)Функция Unique получает набор текстовых фрагментов и делает так, чтобыкаждый фрагмент входил в набор ровно один раз.Опишем фазы алгоритма детально.Фаза 1 (сканирование). При обходе документа фрагмент текста , соответствующий текущему положению окна, добавляется в множество 1 , если длянего справедливо следующее утверждение:1d (, ) ≤ || ( + 1) (1 − 2 )(3.2.2)1Введём следующее обозначение: = || ( + 1) (1 − 2 ).
Выбор длиныокна и значения будут обоснованы ниже.65Фаза 2 («усушка»). Интервал, по которому производится «усушка» для ∈1 , определен следующим образом: = {||, … ,||}. Перебор элементов проис-ходит так. Вначале рассматриваются все фрагменты, содержащиеся в и имеющие длину ||: «прижатый» к началу , отстоящий от начала на одинсимвол и т.д. до тех пор, пока такие текстовые фрагменты будут содержаться в .
Затем увеличиваем длину рассматриваемых фрагментов на единицу и повторяем процедуру. Действуем так до тех пор, пока длина рассматриваемых фрагментов не достигнет||. Из получившегося множества выбирается тот фрагмент′ , для которого расстояние d (str(′ ), str()) будет минимальным, а приналичии нескольких таких — обладающий наибольшей длиной (функцияCompare). В итоге для каждого элемента ∈ 1 находим один элемент ′ ,которым заменяем в множестве 1 .
Таким образом строится множество2 , которое и является результатом работы фазы 2.Фаза 3 (фильтрация). На этом шаге происходит фильтрация множества 2 ,Это делается следующим образом.1. ∀2 , 2 ∈ 2 , если [2 ] = [2 ], то из 2 удаляется один из них, то есть в2 остаются только уникальные элементы.2. Из 2 удаляются все фрагменты текста, отрезки которых находятся внутриотрезков каких-либо других фрагментов, то есть ∀2 ∈ 2 ∃2 ∈ 2 , такой, что 2 ⊂ 2 .Результатом фазы 3 является множество найденных фрагментов текста документа 3 .
Результатом работы всего алгоритма является множество , котороесовпадает с множеством 3 .3.3. Доказательство полноты алгоритмаСформулируем теперь критерий полноты для предложенного алгоритма.Критерий полноты для нашего алгоритма определим следующим образом.Пусть для произвольного документа , для любого его текстового фрагмента ,66а также для — некоторой выдачи алгоритма и для любой группы неточныхповторов фрагмента с точностью (см.
опр. 2.1.11) истинно следующееусловие:∀ ∈ ∃ ∈ : | ∩ | ≥Функцию||2||21(3 − )(3.3.3)1(3 − ) будем обозначать как (). Смысл данного крите-рия заключается в том, что для любого фрагмента документа , являющегосянеточным повтором образца , множество R будет содержать текстовый фрагмент, который существенно пересекает данный неточный повтор. Таким образом, этот неточный повтор оказывается «покрыт» выдачей, и пользователь, просматривая результаты работы алгоритма, сможет, при желании выполнить редактирование границ соответствующего элемента выдачи с тем, чтобы данный повтор был включён в результирующую выдачу полностью.
Степень существен1ности этого пересечения задаётся с помощью (). Функция ( ) = 0,√3при бо́льших () > 0, так как эта функция возрастает по (её производная равна||21(3 + 2 ) и, очевидно, положительна при всех допустимых1√3<≤1). На практике наилучшие результаты достигаются для ≥ 0,77: при таких () >||2, то есть все элементы «цепляют» неточные повторы, минимум,на половину длины образца. Отметим, что данная оценка пессимистична: результаты экспериментов показывают бо́льшее пересечение выдачи алгоритма и неточных повторов в документе.Теперь перейдём к доказательству полноты предложенного алгоритма.
Сначала докажем ряд вспомогательных утверждений.Утверждение 3.3.1. Пусть — группа неточных повторов фрагмента с точ| |1ностью . Тогда для ∀ 1 , 2 ∈ справедливо ≤ |1| ≤ .267Доказательство. Пусть А — архетип группы , тогда в силу (2.1.1) имеем:|1 | ≤ |||2 | ≤ ||.Так как ⊂ str ()1 и ⊂ str (2 ), имеем:|1 | ≤ || ≤ |1 ||2 | ≤ || ≤ |2 |.Следовательно, справедливо следующее:|g1 | ≤ |2 |(3.3.4)|g 2 | ≤ |1 |.(3.3.5)Разделив (3.3.4) на |2 |, а (3.3.5) — на |2 |, получаем:|1 ||2 |1≤|1 |≤1|1 |⇒|2 ||2 |≤≤1|1 |≤⇒|1 |1|2≤||2 |■Утверждение 3.3.2.
Пусть — группа неточных повторов фрагмента с точностью . Тогда ∀ ∈ справедливо следующее: d (, ) ≤ (1 − 2 )||.Доказательство. Поскольку и принадлежат одной группе неточных повторов, то они имеют один и тот же архетип и могут быть представлены следующим образом: = 0 1 1 2 … −1 , = 0 1 1 2 … −1 ,где 1 , 2 … , является архетипом группы , 0 , 1 , … , — вариативной частью , 0 , 1 , … , — вариативной частью .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
