Вычисление значений поддержки с использованием региональных запросов

В этом разделе мы увидим, как быстро вычислить поддержку и доверие, используя региональные запросы. Техника, использованная здесь, в основном взята из Mander и Baeza-Yates [21]. Идея состоит в сведении поиска оптимального образца к рассмотрению прямоугольников со сторонами, параллельными осям, на двумерной плоскости рангов лексикографически упорядоченных суффиксов.

Пусть A_p1, A_p2, … , A_pn – последовательность, полученная лексикографическим упорядочиванием всех суффиксов A. Здесь A_p – суффикс строки A, начинающийся в позиции p. Затем, сохраняем индексы p1,…,pn в массив suf: [1..n] ® [1..n] длины n в этом порядке, и определяем массив pos: [1..n] ® [1..n], как обратное отображение подстановки suf. Эти массивы называются суффиксными массивами (Gonnet, Baeza-Yates [14]; Manber, Myers [22]). По определению, suf(i) – позиция суффикса ранга i, pos(p) – ранг суффикса A_p.

Сначала, мы соблюдаем, чтобы для любой вершины v дерева Tree_A, набор местонахождений слова Word(v) занимал смежный подинтервал I(v) = [x₁..x₂] в массиве suf.

Лемма 4. Подинтервалы I(v) для всех вершин v вычисляются за время O(n).

Доказательство. I(v) вычисляется проходом дерева Tree_A, от листьев до корня, например поиском в глубину. Просматривая листья слева направо, полагаем I(v_i) = [i..i] для i-го листа (i = 1,…,n). Затем, проходя дерево Tree_A от листьев до корня, мы посещаем каждую вершину v с её детьми v₁, …, v_h и полагаем I(v) = [L..R], где L – левая граница интервала I(v₁), R – правая граница интервала I(v_h). ÿ

Далее, алгоритм строит из S и C диагональное множество ширины k, которое представляет собой множество помеченных точек на плоскости:

Diag_k = { ( p, q; doc(p) ) | 1 £ p,q £ n, 0 £ (q-p) £ k, doc(p) = doc(q) }.

Затем алгоритм преобразует Diag_k в следующее множество помеченных точек на плоскости:

Rank_k = { (pos(p), pos(q); i) | (p, q; i) Î Diag_k }

Для образца зависимых k-близких слов P = (a, k, b), мы рассмотрим двухмерный прямоугольный регион Rect(P) = I(a) x I(b) и определим count(Rect(P),Q) как число различных i таких что (x,y;i) Î Q Ç Rect(P) x [1..m], где Q – любое подмножество множества Rank_k.

Лемма 5. Для любого образца зависимых k-близких слов P, верно count(P,S) = count(Rect(P), Rank_k).

Из леммы 5 задача вычисления supp_S(P) и conf_S(P) свелась к задаче вычисления count(Rect(P), Rank_k). В [27] стандартными способами показывают верность следующей леммы.

Лемма 6. Пусть i - любое число, Q Í [1..l]² x [1..m] – множество помеченных точек на плоскости и R[1..n]² – любой прямоугольник. Тогда, count(R,Q) вычисляется за время O(m log²n) с использованием памяти O(mn log n) с временем предобработки O(n log n), где n – число точек в Q.

Теорема 1. Пусть (S, S, C, k, s) является примером задачи оптимизации доверия образца. Тогда алгоритм Find_Optimal, данный выше, находит все оптимизированные образцы в канонической форме с близостью k и порогом поддержки s за время O(mn² log²n) с использованием памяти O( kmn log(n) ), где m = card(S) и n = size(S).

Доказательство. Сначала мы строим суффиксное дерево за линейное время с линейными расходами памяти. Затем, вычисляем интервалы I(v) для всех вершин v за время O(n) с использованием алгоритма динамического программирования (Preparata и Shamos 1985). Из леммы 1 и леммы 3, это достаточно для поиска самое большее O(n²) канонических образцов P = (Word(u), k, Word(v)), перечислением пар u, v вершин дерева Tree_A. Затем, мы можем видеть из леммы 5 и леммы 6, что для каждого P мы вычисляем supp(P) и conf(P) за время O(knm log n) предобработки, используя O(kmn log n) памяти, время единичного запроса O(m log²n). Обратите внимание, что число Rank_k самое большее kn. Поскольку число возможных шаблонов в канонической форме O(n²), утверждение доказано.  ÿ

Модифицированный алгоритм

В этом разделе мы представляем модифицированную версию нашего алгоритма, которая выполняется за время O(max{k,m}n²) с использованием памяти O(kn). В этом алгоритме реализуется механизм регионального поиска непосредственно на суффиксном дереве, вместо запроса на региональном дереве, и вычисляем значения count(Rect(P),Rank_k) методом динамического программирования, подобным изложенному в Maass [20].

Procedure Modified_Find_Optimal;

Вход: Выборка S = {s₁,…,s_m}, целевое условие C, близость k ³ 0 и Минимальная поддержка 0£s£1.

Выход: Оптимизированные образцы (a,k, b) в канонической форме.

Используемые структуры: приоритетная очередь Q.

Begin

1 Q := Æ; A := s₁$s₂…s_m, вычислить doc;

2 Построитьсуффиксное дерево Tree_A и суффиксные массивы suf, pos;

3 Вычислить Diag_k и Rank_k.

4 for (каждой вершины u дерева Tree_A, обходимых с листьев до корня) do

5 if (u – x-ый лист l_x) then

6 B(l_x) := { <y,z> | <x,y,z> Î Rank_k, $y, $z};

7 If (u – интервальная вершина с детьми u₁, …, u_h) then

8 B(u) := B(u₁) È … È B(u_h), затем выбрасываем (discard) B(u₁), …, B(u_h);

9 for (каждой вершины v дерева Tree_A, обходимого с листьев до корня) do

10 if (v – y-ый лист l_y) then

11 С(l_y) := {<z> | <y,z>Î B(u), $z };

12 if (v – интервальная вершина с детьми v₁, …, v_h) then

13 C(v) := C(v₁) È … È B(v_h), затем выбрасываем (discard) B(v₁), …, B(v_h);

14 P := (Word(u), k, Word(v) );

15 Вычислить count(P,S₁) и count(P, S₀) из C(v);

16 if (supp(P) ³ s) then

17 Добавить P в Q с ключом conf(P);

18 end for;

19 end for;

20 Вывести все образцы из Q.

End proc.

Каждая вершина v дерева Tree_A имеет линейные списки B(v) и C(v). Элементами B(v) являются пары <y,z> Î [1..n] x [1..m] и сортируются по координате y. Аналогично, элементы C(v) метки <z> Î [1..m] сортируются по координате z. Для любого x Î [1..n], обозначим как l_x x-ый лист.

Лемма 7. Предположим, алгоритм Modified_Find_Optimal посещает вершину u в цикле (строка 4), посещает вершину v в цикле (строка 9) и достигает строки 15. Тогда C(v) – упорядоченный список z, такой что (x,y;z) Î Rank_k Ç Rect(P) x [1..m].

Доказательство. Доказывается индукцией по высоте вершин u и v подобным образом как в 4-ой лемме.  ÿ

Теорема 2.  Пусть (S, S, C, k, s) является примером задачи оптимизации доверия образца. Тогда алгоритм Modified_Find_Optimal находит все оптимальные образцы в канонической форме близости k и порогом поддержки s за время O(max{k,m}n²) с используемым объемом памяти O(kn), где m = card(S), n = size(S).

Доказательство. Утверждение следует из леммы 1, леммы 3, леммы 5 и леммы 7. Оцениваем время. Строка 1 – строка 3 расходует время O(n + kn). Поскольку дерево Tree_A содержит O(n) вершин, внешний цикл (строка 4) выполняется за время O(n) и, таким образом, внутренний цикл (строка 9) выполняется за время O(n²). В каждом посещении вершины u во внешнем цикле каждая операция объединения (строка 8) занимает время O(kn) потому что длина получаемого списка B(u) очевидно ограничена числом kn = card(Rank_k). Строка 6 алгоритма дает общее время O(kn) просмотра всех листьев. Аналогично, каждое посещение вершины v во внутреннем цикле, каждая операция объединения (строка 13) дает время O(hm) потому что каждый C(v_i) отсортирован и его длина ограничена числом m, где р – число детей. Поскольку суммарное количество детей всех вершин O(n), амортизированное общее время строки 13 O(mn). Амортизированное время строки 11 O(kn) – просмотр всех листьев фиксированной вершины u. Объединяя эти наблюдения получаем, что полное время выполнения алгоритма T(n) = O(kn) + O(kn) + n * (O(kn) + O(mn) )= O(max{k,m}n²).  ÿ

Известно, что высота суффиксного дерева O(log n) для случайных текстов сгенерированных равномерным распределением [7]. На основании теоремы 3 мы с высокой вероятностью ожидаем эффективного выполнения алгоритма за время O(kn log³n) для таких случайных текстов.

Теорема 3. Пусть (S, S, C, k, s) является примером задачи оптимизации доверия образца. Тогда существует алгоритм который вычисляет все оптимальные образцы в канонической форме близости k и порогом поддержки s за время O(kd²n log n ) используя O(kn) памяти, где n = size(S), d – высота суффиксного дерева.

Доказательство. Заметим, что каждый слой, набор вершин на одном уровне, суффиксного дерева содержит Т = kn элементов в B(u) (C(u)). В модифицированном алгоритме мы связываем с каждой вершиной указатель на её родителя и отсортированный список C(v) и B(u) точек <y,z> и <x,y,z>. Мы используем сбалансированные деревья для представления каждого списка C(v), так чтобы мы могли осуществить вставку элементов и подсчет положительно помеченных или отрицательно помеченных элементов за время log l для l = card(C(v)). Используя их, мы проходим уровни дерева (tree levelwise) от листьев до корня. Таким образом, в каждой вершине u со списком B(u), мы можем вычислить все C(v) за время O(dn₀ log n₀) (строка 10 – строка 17 алгоритма), где n₀ = card(B(u)). Неоднократно повторяя это рассуждение, мы можем получить оценку O(kd²n log n). Мы опускаем детали. ÿ