Диссертация (1149623), страница 13
Текст из файла (страница 13)
Введем следующие обозначения: = 0 1 … , = 0 1 … ,|I||p| = 1 2 … . Тогда в силу (2.1.1) имеем:≥ ⇒ || − | | ≥ || ⇒ || − || ≥ | | ⇒ ||(1 − ) ≥ .68Аналогично: ||(1 − ) ≥ . При этом из можно получить заменой на , то есть d (, ) ≤ | | + | | ≤ (1 − )(|| + ||). В силу утверждения3.3.1 имеем|| ≤ ||. Тогда d (, ) ≤ (1 − )(1 + )|| = (1 − 2 )||. ■Утверждение 3.3.3.
Пусть — группа неточных повторов фрагмента с точностью , множество 1 является результатом первой фазы алгоритма, а ∈ — произвольный текстовый фрагмент. Тогда критерий полноты выполнен длямножества 1 , если его взять в качестве множества .Доказательство. Для d справедливо неравенство треугольника: d (, ) ≤d (, ) + d (, ). Согласно утверждению 3.3.2, d (, ) ≤ ||(1 − 2 ).Также известно, что ⊆ . Следовательно, поскольку можно получить из отбрасывая всех символов, которые принадлежат \, справедливо следующееутверждение: d (, ) ≤ || − ||. Но так как || =||и, согласно утвержде1нию 3.3.1, || ≥ ||, то справедливо следующее: || − || ≤ || − ||.
Сле11довательно, d (, ) ≤ || ( − + 1 − 2 ) = || (1 + ) (1 − 2 ). Очевидно,что при сканировании документа на фазе 1 найдётся такое положение окна, что попадает в окно. Тогда в силу (3.2.2) ∈ 1 . Таким образом, справедливоследующее:∀ ∈ : (|| =||, ⊆ ) ⇒ ∈ 1 .Поскольку для любого неточного повтора найдётся элемент из 1 , которыйне просто пересекает этот повтор, а целиком его содержит, то критерий 1 выполнен для множества 1 , если его взять в качестве множества . ■Утверждение 3.3.4. Пусть — группа неточных повторов фрагмента сточностью , а множество 2 — это результат второй фазы алгоритма.
Тогдасправедливо следующее утверждение:∀ ∈ ∃2 ∈ 2 : | 2 ∩ | ≥ .Доказательство. На фазе 2 алгоритма каждый элемент 1 ∈ 1 заменяется нановый. Таким образом, общее количество элементов в множествах 1 и 2 одно69и то же. Согласно утверждению 3.3.3, для каждого ∈ можно найти подходящий 1 ∈ 1 такой, что ⊆ 1 .
Докажем, что получающийся в результатефазы 2 текстовый фрагмент 2 , соответствующий 1 , удовлетворяет формулировке утверждения.1По построению множества 1 имеем: |1 | = ||. В соответствии с утвер1ждением 3.3.1 || ≤ || ≤ ||. Поскольку по утверждению 3.3.3 в 1 попа1дают все фрагменты длины ||, содержащие , можно выбрать фрагмент 1так, чтобы интервал [] был расположен по центру интервала [1 ]. Далее, врамках этой ситуации рассмотрим случай, когда по результатам фазы 2 в качестве 2 был выбран фрагмент текста, «прижатый» к правому краю 1 : e(2 ) =e(1 ).Рис.
3.3.1. Расположение фрагментов текста 1 , 2 , g,когда 2 «прижат к правому краю» 1 .Обозначим b(2 ) и e(2 ) как и соответственно. Согласно описаниюфазы 2 имеем: || = |2 | ≥ ||. Точка также совпадает с e(1 ). Точку e()1обозначим как . Тогда между границами и 1 остаётся || = (|1 | − ||).211 ||Покажем теперь, что ∈ . Действительно, || = (|1 | − ||) ≤ ( −22 112||) = || ( − ). Это неравенство справедливо согласно описанию фазы 1, всилу которого |1 | =||, а также утверждения 3.3.1 (|| ≥ ||). Посколькутакже справедливо, что || ≥ ||, то справедливо и следующее:||1 11|| − || ≥ || ( − ( − )) =(3 − )2 2(3.3.6)70Легко показать, что поскольку1√3< ≤1, то правая часть (3.3.6) положи-тельна и, следовательно, || − || > 0.
Таким образом, точка лежит внутриотрезка . Теперь можно оценить || следующим образом:|| = | 2 ∩ | = || − || ≥||21(3 − ) = .Аналогично рассматривается ситуация, когда b(2 ) = b(1 ), то есть когда2 «прижат» к левому краю окна 1 .Очевидно, что когда 2 «не прижат» к краям окна, оценки |2 | остаютсяпрежними, но поскольку 2 смещается ближе к центру 1 , то | 2 ∩ | можетразве лишь увеличиться, и в этом случае также оказывается справедливым утверждение | 2 ∩ | ≥ .
■Утверждение 3.3.5. Пусть — группа неточных повторов фрагмента с точностью и дано множество 3 — результат работы третьей фазы алгоритма.Тогда справедливо следующее утверждение:∀ ∈ ∃3 ∈ 3 : | ∩ 3 | ≥ .Таким образом, утверждается, что результаты третьей фазы алгоритма даютоценку для пересечения с неточными повторами в тексте не хуже, чем результаты второй фазы алгоритма.Доказательство. Первый шаг третьей фазы алгоритма очевидно не ухудшаетэту оценку, т.к.
он лишь устраняет дубликаты.Второй шаг третьей фазы алгоритма, встретив 2′ , 2′′ ∈ 2 : 2′ ⊂ 2′′ , оставляет из них лишь 2′′ . Но если 2′ ⊂ 2′ , то очевидно, что ∀ ∈ | ∩ 2′′ | <| ∩ 2′′ |. Следовательно, второй шаг третьей фазы, убрав из результата 2′ ,также не ухудшит оценку. ■Теперь докажем полноту предложенного алгоритма.Теорема 3.3.1. Для любого текстового фрагмента ∈ , для любого :1√3< ≤ 1, для любой соответствующей выдачи алгоритма и для любой группынеточных повторов фрагмента с точностью выполняется критерий полноты.71Доказательство.
Фаза 1 алгоритма формирует набор фрагментов 1 , в отношении которого в силу утверждения 3.3.3 следует, что оно удовлетворяет критерию полноты. Фаза 2 поэлементно оптимизирует 1 , строя на основе его элементов 2 . При этом утверждение 3.3.4 доказывает, что для каждого ∈ средиэлементов 2 найдутся те, которые удовлетворяют критерию полноты. Фаза 3отбрасывает избыточные и неоптимальные элементы 2 . При этом утверждение3.3.5 доказывает, что оставшихся в 3 элементов также достаточно, чтобы удовлетворить критерию полноты. Поскольку = 3 , то результат работы всего алгоритма удовлетворяет критерию.
■3.4. Эксперименты и оптимизацииДля предложенного алгоритма был проведён ряд экспериментов на документах ПО из табл. 1.5.1. Исследовались время работы алгоритма и величина выдачи. В последнем случае интересовало количество ложных срабатываний.Эксперименты проводились на компьютере с центральным процессором IntelCore i7 2600 (тактовая частота 3,4 ГГц, кэш 8 Мб) и 16 Гб ОЗУ. Для определениявремени работы эксперименты проводились для образцов длиной от 20 до 100 сшагом в 10 символов. Для сопоставления, фрагменты из Приложения (колонка«Найдено») имеют длину в среднем 338 символов, а длина максимального фрагмента составила 348 символов. Эксперименты проводились при значении мерыблизости = 0,87 (по утв. 2.1.1 соответствует 15% в определении 2.1.9).
В качестве образца для поиска в каждом документе выбирались фрагменты текста, повторяющиеся наибольшее количество раз. Выбор подходящего фрагмента производился каждый раз «вручную» с использованием тепловой карты и алгоритмакомпоновки. Здесь автор исследования исходил из того соображения, что чембольшее число раз образец встречается в документе среди образцов той жедлины, тем больше времени будет работать алгоритм. Тот факт, что в данномэксперименте изменяемым параметром является длина образца, а мера близостизафиксирована, объясняется тем, что, исходя из предварительных эксперимен-72тов, время работы алгоритма сильно варьируется в зависимости от размера образца и этот размер может значительно меняться, в то время как меняется внезначительном диапазоне и поэтому не оказывает значительного влияния напроизводительность.В результате экспериментов было установлено следующее.
Как показано нарис. 3.4.1, при изменении длины образца от 20 до 100 быстро растёт и достигаетв среднем 7 минут. При этом для самого большого документа (Blender, 2,5 Мб)время работы алгоритма при || = 100 составило более получаса. С учётом того,что поиск по образцу для одного документа может выполняться десятки раз, иэтот поиск происходит в интерактивном режиме, такая скорость работы алгоритма является неприемлемой на практике.
Соответственно, эксперименты сбольшей длиной образца давали результат в 10 минут и более, и в тексте диссертационной работы они не представлены в детальном виде.Для оценки длины выдачи использовался описанный выше эксперимент. Анализ документации показал, что на практике большинство осмысленных группнеточных повторов образовано двумя текстовыми фрагментами, реже — десятью, ещё реже — несколькими десятками, в отдельных случаях — несколькимисотнями. Тем не менее, для различных документов и искомых образцов алгоритмчасто выдавал в 5–10 раз больше повторов, чем фактически содержалось в документе. Для документов из табл.
1.5.2 максимальный размер выдачи в рамках проводимых экспериментов составил 13056 элементов. Это была самая большая выдача на рассмотренных в ходе эксперимента примерах. При этом ложноположительных срабатываний оказалось 12044. Большинство ложноположительныхсрабатываний, выдаваемых данным алгоритмом, являются фрагментами текста,смещёнными относительно друг друга на один или несколько символов.
Это связано с тем, что во время первой фазы алгоритма для каждого вхождения образцафрагменты текста начинают попадать в 1 не позже, чем двигающееся по текстуокно полностью включит в себя это вхождение, и продолжают попадать в 1 покрайней мере до тех пор, пока окно не сдвигается с него (см. доказательствоутв. 3.3.3). При этом окно существенно больше любого вхождения (то есть оно73является максимально большим текстовым фрагментом, который может попастьс образцов в одну группу неточных повторов). Итак, выдача алгоритма являетсяформально верной (соответствует критерию полноты), но её размер не позволяетпользоваться алгоритмом на практике.В результате проведённых экспериментов были сформулированы следующиедополнительные требования к алгоритму.1.
Время работы алгоритма не должно превышать нескольких минут для документов, размер которых не превышает 3 Мб.2. Алгоритм должен обеспечивать обозримую выдачу за счёт существенногоуменьшения ложноположительных срабатываний.Для того, чтобы удовлетворить этим требованиям, были предложены и реализованы следующие оптимизации.Оптимизация 1 применяется на фазе 1 (сканирование) и позволяет минимизировать количество вычислений , тем самым существенно понижая времяработы алгоритма.
Идея оптимизации взята из известного алгоритма поиска точных вхождений образца в строку, предложенного Р. Бойером (R. Boyer) иДж. Муром (J. Moore) [45]. Как и в алгоритме Бойера-Мура, мы, убедившись, чтоданное положение окна не подходит для выдачи, используем результаты проверки для того чтобы определить, на сколько символов можно переместить окно,не рискуя пропустить значимый результат. То есть, если во время сканированиядля положения окна справедливо d (, ) > + 1, то будем сдвигать окнона (d (, ) − )/2 символов вправо, в противном случае сдвигаем на одинсимвол.Оптимизация 2 применяется на фазе 2 («усушка») и также позволяет минимизировать количество вычислений d .
Подход аналогичен используемому впредыдущей оптимизации. Во время «усушки» текстового фрагмента w1 прикаждом положении окна 2′ обновляем (при необходимости) наименьшее значение d (, 2′ ) (обозначим его ). Если для данного положения окна 2′справедливо d (, 2′ ) > + 1, сдвинем далее окно не на один, а на74(d (, 2′ ) − )/2 символов вправо, в противном случае сдвинем окно наодин символ вправо. Значение стирается в начале нового цикла со следующим фиксированным значением длины сканирующего окна.Оптимизация 3 применяется на фазе 3 (фильтрация) и позволяет уменьшитьмощность 3 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
