Rozdział 9: Drzewa sufiksowe - algorytmy McCreighta i Ukkonena

Dużo starszym od tablic sufiksowych pomysłem na reprezentację wszystkich podsłów tekstu jest struktura drzewa sufiksowego. Drzewo sufiksowe jest drzewem TRIE zbudowanym z wszystkich sufiksów danego tekstu. Dla przypomnienia: TRIE to drzewo, w którym każda krawędź jest etykietowana pewnym znakiem lub ciągiem znaków. Wtedy korzeń TRIE reprezentuje napis pusty, natomiast ścieżki od korzenia do dowolnego innego węzła w drzewie reprezentują pewien napis, zbudowany z konkatenacji etykiet na krawędziach tworzących tę ścieżkę. Ponieważ zgodnie z definicją drzewo sufiksowe budujemy z wszystkich sufiksów tekstu, otrzymujemy strukturę danych reprezentującą wszystkie podsłowa. Na początku skupimy się na zastosowaniach drzewa sufiksowego, następnie na algorytmach jego konstrukcji.

W poniższych rozważaniach zakładamy, że budujemy drzewo sufiksowe z tekstu postaci $x\#$, gdzie $\#$ jest specjalnym symbolem niewystępującym w alfabecie. Oznacza to, że każdemu sufiksowi słowa $x$ odpowiada w drzewie sufiksowym dokładnie jeden liść. Ułatwi to nieco rozważania teoretyczne, natomiast w praktyce nie jest taki sposób konstrukcji drzewa niezbędny.

Szukanie podsłów

Aby sprawdzić, czy w zadanym tekście występuje jakiś wzorzec $y = y_1 y_2 \ldots y_m $ próbujemy zbudować w drzewie sufiksowym ścieżkę rozpoczynającą się w korzeniu i przechodzącą kolejno krawędziami etykietowanymi znakami $y_1$, $y_2$ itd. Jeśli w pewnym momencie po zbudowaniu ścieżki składającej się z pierwszych $i$ symboli słowa $y$ nie możemy przejść do symbolu $y_{i+1}$, ponieważ w drzewie nie istnieje krawędź o odpowiedniej etykiecie, to znaczy, że słowo $y$ nie występuje w tekście $x$.

Jeśli jednak zbudujemy całą ścieżkę i znajdziemy się na końcu w pewnym punkcie drzewa sufiksowego, możemy łatwo znaleźć wartości takie, jak liczba i miejsca wystąpień wzorca $y$ w tekście $x$. Zbiór wystąpień bowiem można łatwo określić patrząc na liście poddrzewa ukorzenionego w punkcie, w którym skończyliśmy wyszukiwane wzorca. Ponieważ istnieje odpowiedniość pomiędzy liścmi drzewa i sufiksami tekstu, łatwo można określić zbiór pozycji, na których wzorzec występuje. Oczywiście można dzięki temu znaleźć także np. pierwsze czy ostatnie wystąpienie dowolnego wzorca w tekście.

Zadanie: Jak znaleźć najdłuższe podsłowo występujące przynajmniej 2 razy w tekście? Jak zmieni się algorytm, jeśli będziemy szukać podsłów występujących co najmniej (albo dokładnie) $k$ razy w tekście?

Wyznaczanie liczby podsłów

Napisaliśmy wcześniej, że krawędź w TRIE jest etykietowana znakiem lub ciągiem znaków. Zdefiniujmy wagę krawędzi jako liczbę znaków, które znajdują się na etykiecie. Wtedy liczbę różnych podsłów w danym tekście można obliczyć sumując wagi wszystkich krawędzi drzewa sufiksowego.

Konstrukcja drzewa sufiksowego

W oczywisty sposób możemy zbudować drzewo sufiksowe w czasie $O(n^2)$ poprzez dodawanie do TRIE kolejnych sufiksów tekstu (zarówno tutaj jak i w dalszej części zakładamy, że alfabet $\Sigma$ ma rozmiar stały; w przeciwnym przypadku do każdej operacji należy dodać czynnik $\log \vert \Sigma \vert$). Wtedy każda krawędź drzewa jest etykietowana pojedynczym znakiem. Rozmiar takiej struktury danych także jest kwadratowy. Aby w ogóle rozważać szybszy algorytm konstrukcji struktury danych, należy określić taką jej reprezentację, której rozmiar jest mniejszy niż kwadratowy względem rozmiaru danych.

Zmieńmy nieco podejście: jeśli w drzewie występuje łańcuch krawędzi bez żadnych rozgałęzień, to zastępujemy go pojedynczą krawędzią etykietowaną kolejnymi znakami z zastępowanego właśnie łańcucha. Będziemy o takiej strukturze mówić skompresowane drzewo sufiksowe. Zauważmy, że ponieważ skompresowane drzewo ma dokładnie $n + 1$ liści (dla tekstu postaci $x = x_1 x_2 \ldots x_n \#$), to ma dokładnie $n$ węzłów wewnętrznych, a zatem $2n$ krawędzi. Co więcej, krawędzi nie musimy etykietować explicite ciągiem znaków, lecz parą liczb, oznaczających początek i koniec pewnego podsłowa w tekście $x$. Otrzymaliśmy w ten sposób reprezentację drzewa sufiksowego liniowego rozmiaru.

W wyniku kompresji przestają istnieć niektóre węzły drzewa, do których mimo wszystko będziemy się odnosić w dalszej części tekstu. Takie wierzchołki będziemy nazywać niejawnymi, natomiast wierzchołki rzeczywiście istniejące w skompresowanych drzewach sufiksowych nazwiemy jawnymi. Zdefiniujmy dodatkowo operację $Label(v)$, która dla zadanego węzła $v$ w drzewie generuje słowo z nim stowarzyszone oraz tzw. dowiązanie sufiksowe (ang. suffix link) $Suf(v)$, które dla zadanego węzła $v$ takiego, że $Label(v) = y_0 y_1 y_2 \ldots y_k$ zwraca wskaźnik na taki węzeł $v'$, że $Label(v') = y_1 y_2 \ldots y_k$. Czyli innymi słowy otrzymujemy wskaźnik na węzeł reprezentujący słowo pozbawione pierwszego znaku. Dla korzenia $root$, którego $Label$ jest słowem pustym, przyjmujemy $Suf(root) = root$.

Algorytm McCreighta - konstrukcja offline

Algorytm McCreighta buduje skompresowane drzewo sufiksowe w kolejności od najdłuższego sufiksu do najkrótszego. Ogólny schemat algorytmu jest następujący:

W fazie pierwszej inicjujemy drzewo najdłuższym sufiksem $sufiks_1$, czyli pojedynczą krawędzią reprezentującą cały tekst $x$.
Załóżmy, że jesteśmy w fazie $k > 1$ i dodajemy do drzewa $sufiks_k$.
Przedstawmy słowo $sufiks_k$ jako konkatenację dwóch słów $p q$ takich, że słowo $p$ jest najdłuższym prefiksem $sufiks_k$, który można utworzyć podążając ścieżką od korzenia w dół drzewa. Taki rozkład jest jednoznaczny.
Definiujemy głowę $head_k$ $k$-tego sufiksu jako taki węzeł $v$ (być może niejawny) w drzewie, że $Label(v) = p$.
Dodajemy do drzewa krawędź reprezentującą słowo $q$ w węźle $head_k$.

Dość łatwo można dostrzec analogię pomiędzy problemem znajdowania $head_k$ a obliczaniem najdłuższego wspólnego prefiksu pomiędzy słowem $sufiks_k$ i zbiorem słów $\lbrace sufiks_1,\, sufiks_2, \ldots,\, sufiks_{k-1}\rbrace$. W dalszych rozdziałach pokażemy sposób konstrukcji drzewa sufiksowego na podstawie tablicy sufiksowej oraz tablicy LCP.

Oczywiście szukanie głowy w sposób naiwny - poprzez przechodzenie od korzenia w dół drzewa i szukanie pierwszego miejsca, gdzie wstawiany sufiks dokonuje rozgałęzienia - niczym nie różni się od algorytmu kwadratowego. Skorzystamy z dowiązań sufiksowych, aby szybko znajdować głowę $k$-tego sufiksu. Oznaczmy przez $parent(v)$ rodzica wierzchołka $v$ w drzewie $T$ (w sensie wierzchołków jawnych). Przyjmujemy $parent(root) = root$. Korzystamy z następujących własności drzew sufiksowych:

$head_i$ jest potomkiem $Suf(head_{i-1})$
$Suf(v)$ jest potomkiem $Suf(parent(v))$ dla każdego $v \in T$

Korzystając z wymienionych właściwości drzewa $T$ możemy zaoszczędzić sporo pracy, wyszukując głów idąc niejako "na skróty" przez dowiązania sufiksowe. Aby wydusić odpowiednią złożoność, musimy jeszcze przyspieszyć nieco poruszanie się w dół drzewa. Rózróżniamy dwa sposoby schodzenia w dół drzewa:

Wolne ($slowfind$), czyli przemieszczanie się znak po znaku. Używane, gdy nie wiemy wystarczająco wiele o szukanym słowie, aby przemieszczać się w sposób szybki. Schodzenie wolne stosujemy np. w algorytmie sprawdzania, czy dane słowo $y$ jest podsłowem tekstu $x$ - nie mamy pewności, czy $y$ występuje, więc ostrożnie testujemy kolejne znaki drzewa zbudowanego z tekstu $x$.
Szybkie ($fastfind$), gdy wyszukujemy w drzewie słowa, o którym wiemy, że na pewno je znajdziemy, a bardziej interesuje nas gdzie (w jakim węźle jawnym lub niejawnym) je znajdziemy. Pozwala to w czasie stałym omijać całe krawędzie drzewa, niezależnie od tego jak długie podsłowa one reprezentują.

Funkcja dwuargumentowa $slowfind(v,\, y)$ (analogicznie $fastfind(v,\, y)$) zwraca węzeł (być może niejawny), na którym kończy się zejście w dół drzewa zapoczątkowane w węźle $v$, w poszukiwaniu słowa $y$. Po drodze znajdujemy jeszcze wartość $Suf(head_{i-1})$ - jest to ostatni jawny węzeł drzewa na ścieżce z korzenia do $head_i$ włącznie. Na potrzeby opisu algorytmu oznaczmy jeszcze przez $leaf_k$ węzeł końcowy (liść drzewa), powstały po dodaniu $k$-tego sufiksu. Mając już cały arsenał pojęć i pomocniczych operacji, możemy opracować dokładny algorytm konstrukcji drzewa sufiksowego.

Algorytm McCreighta

$T := $ inicjalne drzewo, zbudowane z jednej krawędzi etykietowanej całym tekstem $x$ o długości $n$;
$head_1 := root$, $leaf_1 := $ jedyny liść drzewa;
for i := 2 to n do begin
- Niech $p$ oznacza etykietę na krawędzi $parent(head_{i-1}) \to head_{i-1}$;
- Niech $q$ oznacza etykietę na krawędzi $head_{i-1} \to leaf_{i-1}$;
- if $head_{i-1} = root$ then
  - Usuń pierwszy znak z $q$;
  - $head_i := slowfind(root,\, q)$;
  else
  - $u := parent(head_{i-1})$;
  - if $u = root$ then
    - Usuń pierwszy znak z $p$;
    - $v := fastfind(root,\, p)$;
    else
    - $v := fastfind(Suf(u),\, p)$;
  - if $v$ jest węzłem niejawnym then
    - $head_i := v$;
    else
    - $head_i := slowfind(v,\, q)$;
  - $Suf(head_{i-1}) := v$; {uproszczenie notacyjne: nawet jeśli v jest niejawne, to zaraz zostanie utworzone jako jawne}
- Stwórz węzeł $leaf_i$;
- if $head_i$ jest węzłem niejawnym then
  - rozbij krawędź, na której znajduje się $head_i$ na dwie krawędzie ($head_i$ staje się jawne);
- Stwórz krawędź $head_i \to leaf_i$ o odpowiedniej etykiecie;
end;

Twierdzenie
Algorytm McCreighta buduje drzewo sufiksowe tekstu o długości $n$ w czasie $O(n)$, przy założeniu $\vert \Sigma \vert = O(1)$.

Dowód
Rozważmy oddzielnie czas działania wszystkich wykonań $slowfind$ i $fastfind$. Wszystkie pozostałe operacje działają w czasie stałym. Niech $depth(v)$ oznacza głębokość węzła $v$ w drzewie sufiksowym, tzn. liczbę węzłów w skompresowanym drzewie na ścieżce od korzenia do $v$.

Operacja $fastfind$ zwiększa głębokość, na której przebywamy. Przejście do rodzica oraz przejście dowiązaniem sufiksowym zmniejsza tę głębokość. Zachodzi $depth(v) \leq depth(Suf(v)) + 1$. Oznacza to, że w każdej iteracji algorytmu najpierw zmniejszamy głębokość o co najwyżej 2, a następnie zwiększamy tę głębokość. Nie możemy jej zwiększać w nieskończoność, bo liczba węzłów drzewa jest w danej fazie liniowa względem numeru iteracji (rzędu $2n$), zatem po wszystkich iteracjach wykonamy co najwyżej liniowo wiele przemieszczeń po węzłach drzewa w trakcie $fastfind$.

Wykażemy teraz, że czas spędzony na wykonywaniu $slowfind$ także jest liniowy, co zakończy dowód. Przez zapis $\vert head_i \vert$ rozumiemy odległość węzła $head_i$ od korzenia w sensie nieskompresowanego drzewa sufiksowego. Używamy $slowfind$ aby znaleźć $head_i$ rozpoczynając od $Suf(head_{i-1})$. Ponieważ początkowych $\vert head_{i-1} \vert$ znaków znajdujemy przy pomocy $fastfind$, praca wykonana przez $slowfind$ wynosi $\vert head_i \vert - \vert head_{i-1} \vert + O(1)$. Zatem łącznie wykonamy liniowo wiele operacji:
$$\sum_{i = 2}^{n} \vert head_i \vert - \vert head_{i-1} \vert + O(1) = O(n)$$

Algorytm Ukkonena - konstrukcja online

Algorytm online konstrukcji drzewa sufiksowego będzie stosował odmienną filozofię (a raczej kierunek) działania. Rozważmy najpierw prosty algorytm działający w złożoności kwadratowej. Budujemy nieskompresowane drzewo sufiksowe z kolejnych prefiksów słowa $x = x_1 x_2 \ldots x_n$: w $k$-tej fazie dodajemy w pewnych punktach drzewa $T_{k-1}$ krawędzie etykietowane znakiem $x_k$ w taki sposób, aby otrzymać drzewo sufiksowe $T_k$ dla słowa $x_1 x_2 \ldots x_k$. Te punkty to miejsca, w których w drzewie $T_{k-1}$ kończą się sufiksy. Innymi słowy utrzymujemy listę miejsc, gdzie kończą się sufiksy drzewa $T_{k-1}$ i w kolejnej fazie przedłużamy każdy taki sufiks o symbol $x_k$, aktualizując tym samym listę. Należy do niej oczywiście dodać nowy sufiks, składający się wyłącznie z symbolu $x_k$.

Może zdarzyć się tak, że przedłużając pewien sufiks $sufiks_i$ o symbol $x_k$ okaże się, że w węźle odpowiadającym "zakończeniu" tego sufiksu istnieje już krawędź etykietowana znakiem $x_k$. Wtedy oczywiście nie dodajemy w tym punkcie nowej krawędzi, a jedynie aktualizujemy "zakończenie" sufiksu $sufiks_i$. Całość można opisać następującym pseudokodem:

Algorytm Drzewo-Sufiksowe-Online

$L$ oznacza listę wszystkich końcówek sufiksów.

$T := root$;
$L := \lbrace root \rbrace$;
for i := 1 to n do begin
- for j := 1 to i do begin
  - $v := L[j]$;
  - if nie istnieje krawędź w drzewie $T$ o etykiecie $x_i$ wychodząca z $v$ then
    dodaj taką krawędź;
  - $L[j] := v'$, gdzie $v'$ jest wierzchołkiem docelowym krawędzi wychodzącej z $v$ etykietowanej $x_i$;
- $L.push(root)$;
end;

Postaramy się usprawnić ten algorytm korzystając z pewnej regularności wykonywanych w nim operacji. Łatwo można zaobserwować następujące fakty dotyczące działania algorytmu:

Jeśli w pewnej iteracji algorytmu któraś z "końcówek" sufiksu stanie się liściem wskutek dodania nowej krawędzi do drzewa, to taka końcówka zostaje liściem już na zawsze, niezależnie od liczby i kompozycji dodawanych znaków.
Jeśli w wewnętrznej pętli dla pewnej wartości $j$ nie będziemy musieli dodawać nowej krawędzi, ponieważ dla końcówki $j$-tego sufiksu potrzebna krawędź już istnieje, to z własności drzew sufiksowych wynika, że istnieje taka krawędź już dla wszystkich dalszych końcówek sufiksów znajdujących się na liście, zatem algorytm dokona jedynie przesunięcia tych końcówek o pojedynczą krawędź w dół drzewa.
Zgodnie z definicją dowiązań sufiksowych, zachodzi następująca odpowiedniość między elementami na liście $L$: $L[j + 1] = Suf(L[j])$.

Możemy teraz zastanowić się nad wyprowadzeniem analogicznego algorytmu dla drzew skompresowanych wykorzystując powyższe własności.

Własność 1.
Za każdym razem gdy przedłużamy sufiks dodając nowy liść do drzewa sufiksowego, możemy o tym sufiksie już zapomnieć: przy założeniu opisu krawędzi skompresowanych za pomocą dwóch liczb (początek i koniec jakiegoś podsłowa w $x$) możemy jako drugiej liczby użyć umownego znacznika nieskończoności $\infty$. Dzięki temu zachowamy własność online algorytmu, ponieważ taka krawędź reprezentować będzie dowolny tekst zaczynający się w określonym punkcie. Będziemy zatem chcieli przeglądać jedynie te końcówki sufiksów, które wymagać będą przedłużenia nową krawędzią, wykonywać operację dodania takiej krawędzi w czasie stałym i zapominać o takich sufiksach.

Własność 2.
Jeśli rozważając kolejne sufiksy natrafimy na taki, którego nie musimy przedłużać, bo odpowiednia krawędź znajduje się już w drzewie, to nie musimy też przeglądać dalszych, ponieważ dla nich także odpowiednia krawędź występuje. W poprzednim algorytmie aktualizowaliśmy pozycje tych końcówek, tutaj chcemy tego uniknąć.

Własność 3.
Uniknąć tego możemy, o ile potrafimy szybko znajdować kolejne końcówki sufiksów korzystając z dowiązań sufiksowych, aby w razie potrzeby namierzyć kolejne miejsce wymagające rzeczywistej aktualizacji, tzn. dodania krawędzi-liścia. Można zastosować w tym celu ten sam trik, co w algorytmie McCreighta: zapamiętujemy jedynie dowiązania sufiksowe wierzchołków jawnych, a jeśli chcemy znaleźć dowiązanie wierzchołka niejawnego, to najpierw przechodzimy po dowiązaniu sufiksowym jego (jawnego) rodzica w drzewie, a następnie wykonujemy operację $fastfind$.

Algorytm Ukkonena

$v := root$;
for i := 1 to n do begin
- if istnieje krawędź wychodząca z $v$ etykietowana $x_i$ then
  - Zejdź o jeden znak w dół krawędzią z symbolem $x_i$;
  else
  - $prev_v := \emptyset$;
  - while ($v \neq root$) and (nie istnieje krawędź wychodząca z $v$ etykietowana $x_i$) then
    - Dodaj krawędź-liść $[i,\, \infty]$ wychodzącą z $v$ (być może tworząc węzeł jawny w $v$);
    - $prev_v := v$;
    - Niech $p$ oznacza etykietę na krawędzi $parent(v) \to v$;
    - if ($parent(v) = root$) then
      - Usuń pierwszy znak z $p$;
    - $v := fastfind(Suf(parent(v)),\, p)$;
    - $Suf(prev_v) := v$;
  - if (nie istnieje krawędź wychodząca z $v$ etykietowana $x_i$) then
    - Dodaj krawędź-liść $[i,\, \infty]$ wychodzącą z $root$; {zachodzi v = root}
    else
    - Zejdź o jeden znak w dół krawędzią z symbolem $x_i$;
end;

Twierdzenie
Algorytm Ukkonena buduje drzewo sufiksowe tekstu o długości $n$ w czasie $O(n)$, przy założeniu $\vert \Sigma \vert = O(1)$.

Dowód
Obrotów wewnętrznej pętli while mamy liniowo wiele - każdy obieg odpowiada dodaniu jednego liścia, a tych jest $O(n)$. Wszystkie operacje w pętli poza $fastfind$ wykonujemy w czasie stałym. Należy zatem rozważyć łączną pracę wykonaną przez wszystkie wywołania $fastfind$ - dowód identyczny do dowodu z algorytmu McCreighta.

Ciekawy przykład

Niech $Fib'_n$ oznacza $n$-te słowo Fibonacciego (dla $n \geq 3$) pozbawione dwóch ostatnich liter. Kilka pierwszych słów tej postaci:

$Fib'_3 = a$
$Fib'_4 = aba$
$Fib'_5 = abaaba$
$Fib'_6 = abaababaaba$

Interesujący fakt, którego nie będziemy tutaj udowadniać: takie słowo jest palindromem. Ponadto drzewo sufiksowe dla słów $Fib'$ wykazuje interesującą regularność, co wynika ze struktury tych słów - każde z nich można przedstawić jako konkatenację odwróconych kolejnych słów Fibonacciego. Tzn. jeśli $R_k = Fib_k^R$, to wtedy $Fib'_n = R_1 R_2 \ldots R_{n-2}$.

Przykład

Poniższy rysunek pokazuje drzewa sufiksowe słów $Fib'_6$ i $Fib'_7$. Łatwo określić regułę, wedle której potrafimy przewidzieć budowę drzewa sufiksowego dla słowa $Fib'_8$ i dalszych.
Drzewo sufiksowe zmodyfikowanych słow Fibonacciego

Przyjrzyjmy się szczegółom działania algorytmu. W momencie, gdy mamy zbudowane drzewo dla $Fib'_6$, znajdujemy się (tzn. wierzchołek $v$ z algorytmu) na skrajnie lewej krawędzi drzewa, dokładnie na styku słów $R_3$ i $R_4$. Kontynuujemy budowanie drzewa dla $Fib'_7$, czyli dodajemy w miejscu $v$ słowo $R_5$. $R_5$ zaczyna się od symbolu a, natomiast krawędź, na której się znajdujemy ma jedynie zejście dla symbolu b - dla przypomnienia: znajdujemy się pośrodku krawędzi, zaraz przed fragmentem opisującym słowo $R_4$, które zaczyna się od a, z czego wynika ta niezgodność. Musimy zatem dodać nowy liść w drzewie sufiksowym oraz skorzystać z dowiązań sufiksowych i funkcji $fastfind$, aby znaleźć następny sufiks w drzewie i być może dodać kolejne liście. Poniższy rysunek pokazuje to działanie - zielonym kolorem pokazane są kolejne węzły na ścieżce dowiązań sufiksowych: $v = v_0$, $v_i = Suf(v_{i-1})$. Niebieskim kolorem oznaczono dodane węzły-liście.

Dodanie symbolu 'a' do drzewa sufiksowego

Jak widać na rysunku i co łatwo sprawdzić samodzielnie, w węźle $v_3$ istnieje krawędź wychodząca, rozpoczynającą się symbolem a, zatem przerywamy przechodzenie dowiązaniami sufiksowymi i schodzimy tym symbolem w dół. To samo dzieje się dla kolejnych dodawanych znaków słowa $Fib'_7$, dopóki nie zejdziemy aż do styku słów $R_4$ i $R_5$ - staje się to idealnie w momencie zbudowania drzewa sufiksowego dla słowa $Fib'_7$, zatem jeśli chcielibyśmy kontynuować i zbudować drzewo dla $Fib'_8$, to cała sytuacja powtarza się od początku. Poniższy rysunek prezentuje kilka etapów pośrednich oraz efekt końcowy przebudowy drzewa $Fib'_6$ w drzewo $Fib'_7$.

Kolejne etapy rozbudowy drzewa sufiksowego.