O ile w drzewie sufiksowym do każdego wierzchołka prowadziła unikalna ścieżka z korzenia, w grafie podsłów takich ścieżek może być więcej. Zanim przejdziemy do dalszych rozważań, zdefiniujmy na nowo etykietę \(Label(v)\) i dowiązanie sufiksowe \(Suf(v)\) dla wierzchołka grafu \(v\). Każdy wierzchołek reprezentuje te podsłowa tekstu, które można zbudować przechodząc wszystkimi możliwymi ścieżkami od korzenia. Uznajmy zatem, że \(Label(v)\) związane będzie z najdłuższym słowem spośród tego zbioru, a \(Suf(v)\) wskazuje na taki wierzchołek \(w\), że \(Label(w)\) jest najdłuższym sufiksem \(Label(v)\) nie należącym do zbioru słów reprezentowanego przez wierzchołek \(v\). Umownie przyjmijmy też, że dowiązaniem sufiksowym korzenia \(root\) grafu podsłów jest jakiś umowny wskaźnik NULL.
Fakt
Zbiór słów reprezentowanych przez wierzchołek grafu podsłów zawiera słowa o długościach będących kolejnymi liczbami całkowitymi od \(c_1\) do \(c_2\) dla pewnych wartości \(c_1\) i \(c_2\). Fakt ten wynika ze sposobu konstrukcji grafu podsłów na podstawie nieskompresowanego drzewa sufiksowego: począwszy od najdłuższego słowa w pewnym zbiorze \(EndPos\), kolejne, krótsze słowa znajdują się na ścieżce dowiązań sufiksowych w drzewie. Na przykład wierzchołek grafu z powyższego przykładu o zbiorze \(EndPos = \lbrace 4 \rbrace\) reprezentuje słowa:
Czyli dla tego wierzchołka \(c_1 = 2\) i \(c_2 = 4\). Jego dowiązanie sufiksowe wskazuje na wierzchołek o zbiorze \(EndPos = \lbrace 3,\, 4,\, 6 \rbrace\), dla którego zachodzi \(c_1 = c_2 = 1\).
Fakt (o zbiorach \(EndPos\))
Dla dwóch wierzchołków grafu \(v\) i \(w\) takich, że \(Suf(v) = w\) zachodzi \(EndPos(v) \subset EndPos(w)\) (podzbiór właściwy - to ważne).
Z powyższego faktu wynikają dalsze konsekwencje. Zauważmy bowiem, że jeśli weźmiemy dwa dowolne różne wierzchołki grafu podsłów, to albo przecięcie ich zbiorów \(EndPos\) będzie puste, albo zbiór \(EndPos\) jednego z nich będzie podzbiorem właściwym zbioru \(EndPos\) drugiego z nich. Tym samym widać, że dowiązania sufiksowe wierzchołków grafu podsłów tworzą drzewo. Prowadzi to prosto do twierdzenia o rozmiarze grafu podsłów.
Twierdzenie
Graf podsłów \(G\) zbudowany z tekstu o długości \(n\) ma \(O(n)\) wierzchołków.
Dowód
Jak pokazaliśmy, dowiązania sufiksowe wierzchołków tworzą drzewo. Co więcej, takie drzewo ma co najwyżej \(n\) liści - liść będzie wierzchołkiem grafu, dla którego \(EndPos\) jest zbiorem jednoelementowym. Gdybyśmy mogli uznać, że każdy wewnętrzny węzeł takiego drzewa ma przynajmniej dwóch potomków, to byłby to koniec dowodu. Jednak tak się nie dzieje np. dla tekstu postaci \(a^n\), gdzie mamy jeden liść oraz \(n - 1\) węzłów wewnętrznych.
Z faktu o zbiorach \(EndPos\) wynika, że w relacji rodzic-dziecko w drzewie dowiązań sufiksowych zbiór \(EndPos\) rodzica zawiera zawsze jakiś indeks, który nie znajduje się w zbiorze \(EndPos\) potomka. Zatem ze względu na drzewiastą strukturę zawierania się zbiorów \(EndPos\) oraz liniową liczbę wszystkich indeksów, liczba takich jednopotomkowych węzłów wewnętrznych jest także co najwyżej liniowa. Koniec dowodu.
Twierdzenie
Graf podsłów \(G\) zbudowany z tekstu o długości \(n\) ma \(O(n)\) krawędzi.
Dowód
Rozważmy dowolne skierowane drzewo rozpinające graf \(G\). Skierowanie oznacza tutaj, że zaczynając w korzeniu grafu możemy osiągnąć wszystkie inne wierzchołki grafu idąc tylko zgodnie ze skierowaniem krawędzi. Takie drzewo ma oczywiście \(O(n)\) krawędzi.
Zastanówmy się, ile pozostaje w \(G\) krawędzi, które nie należą do drzewa rozpinającego. Rozpatrzmy jedną taką krawędź, postaci \(v_1 \stackrel{\alpha}{\to} v_2\). Zbudujmy słowo \(w\) postaci \(p \alpha s\), gdzie \(p\) jest prefiksem \(w\) zbudowanym poprzez przejście wybranym drzewem rozpinającym z korzenia do wierzchołka \(v_1\), \(\alpha\) jest symbolem etykietującym wybraną krawędź niedrzewową, \(s\) jest sufiksem słowa \(w\) i zarazem całego tekstu, zbudowanym poprzez przejście dowolną ścieżką z \(v_2\) do końca grafu \(G\). W ten sposób z przejściem krawędzią niedrzewową utożsamiamy pewien sufiks całego tekstu. Sufiksów jest liniowo wiele, a zatem liczba krawędzi niedrzewowych także jest liniowa, co kończy dowód.
Twierdzenie
Graf podsłów zbudowany z tekstu o długości \(n \geq 3\) ma co najwyżej \(2n - 1\) wierzchołków i co najwyżej \(3n - 4\) krawędzi.
Dowód
Ćwiczenie dla Czytelnika - udowodnić, że nie da się uzyskać więcej i podać przykłady tekstów, które osiągają to ograniczenie dla dowolnego \(n \geq 3\).
Algorytm konstrukcji grafu podsłów
Przedstawiamy działający w liniowym czasie algorytm konstrukcji grafu podsłów. Algorytm ten jest typu on-line, konstruuje graf w kolejnych fazach, dodając po jednym symbolu do tekstu, na podstawie którego graf jest zbudowany. W fazie \(k\)-tej algorytm konstruuje graf podsłów \(G_k\) dla \(k\)-znakowego prefiksu całego tekstu na podstawie grafu podsłów \(G_{k-1}\). Oznaczmy przez \(pref_i(x)\) prefiks tekstu \(x\) o długości \(i\), tzn. słowo \(x_1 x_2 \ldots x_i\).
Zastanówmy się jakie zmiany należy wprowadzić do grafu \(G_{k-1}\), aby uzyskać graf \(G_k\). Na pewno musimy stworzyć nowy wierzchołek, reprezentujący podsłowa tekstu \(pref_k(x)\), które nie są podsłowami tekstu \(pref_{k-1}(x)\). Oprócz tego być może będziemy musieli rozbić pewien wierzchołek po dodaniu nowego znaku, aby zachować zgodność z definicją zbiorów \(EndPos\).
Obserwacja: pewne podsłowo \(y\) słowa \(x\) jest reprezentantem wierzchołka grafu podsłów (tzn. dla pewnego \(v\) zachodzi \(Label(v) = y\)) wtedy i tylko wtedy, gdy albo \(y\) jest prefiksem \(x\), albo wśród zbioru wystąpień \(y\) w \(x\) znajdują się dwa takie, które poprzedzone są różnymi znakami z alfabetu. Wynika to z definicji zbioru \(EndPos\).
Weźmy najdłuższy sufiks słowa \(pref_k(x)\), który występuje w tym słowie więcej, niż jeden raz - oznaczmy to słowo \(tail\). Jeśli \(tail\) jest słowem pustym, to niczego już nie robimy. W przeciwnym wypadku znajdźmy w grafie \(G_{k-1}\) wierzchołek \(v\) odpowiadający słowu \(tail\) (tzn. istnieje ścieżka z \(root\) do \(v\), która "buduje" słowo \(tail\), ale niekoniecznie \(Label(v) = tail\)). Jeśli słowo \(tail\) występowało w \(pref_{k-1}(x)\) zawsze poprzedzone tym samym znakiem \(\alpha\), natomiast ostatnie wystąpienie \(tail\) w \(pref_k(x)\) poprzedzone jest znakiem \(\beta\) różnym od \(\alpha\), to wtedy w grafie \(G_k\) wierzchołek \(v\) rozbijamy na dwa nowe wierzchołki \(v'\) i \(v''\):
- \(v'\) będzie reprezentował słowa ze zbioru definiowanego przez \(v\) o długościach mniejszych lub równych długości słowa \(tail\) - zachodzi oczywiście \(Label(v') = tail\)
- \(v''\) będzie reprezentował pozostałe słowa odpowiadające wierzchołkowi \(v\), tzn. dłuższe od \(tail\)
Skąd wiadomo, że istnieje tylko jeden wierzchołek, który należy rozbić i dlaczego rozbicie przebiega wedle tych reguł? Po pierwsze, jeśli któreś słowo było prefiksem lub występowało poprzedzone dwoma różnymi znakami w \(pref_{k-1}(x)\), to nie straci ono żadnej z tych własności w \(pref_k(x)\). Po drugie, spośród potencjalnie dużego zbioru słów, które w \(pref_k(x)\) pojawiają się z dwoma różnymi znakami po lewej stronie, ale jeszcze w \(pref_{k-1}(x)\) występują tylko z jednym, weźmy najdłuższe takie słowo \(y\) oraz przyjmijmy, że jest związane z pewnym wierzchołkiem \(v\).
Teraz zapiszmy \(Label(v)\) jako \(p \alpha y\). Możemy tak zrobić, bo \(y\) na pewno nie jest \(Label\) dla żadnego wierzchołka grafu (\(p\) może być słowem pustym, ale na pewno występuje jakieś \(\alpha\)). Zatem w słowie \(pref_{k-1}(x)\) każde wystąpienie podsłowa \(y\) było poprzedzone \(p \alpha\), ale w słowie \(pref_{k}(x)\) już tak się nie dzieje: \(\beta y\) musi być sufiksem \(pref_{k}(x)\) dla \(\alpha \neq \beta\). Ponieważ \(\beta y\) nie wystąpiło wcześniej w \(pref_{k-1}(x)\), to \(y\) jest dokładnie słowem \(tail\) - najdłuższym sufiksem występującym więcej niż jeden raz w całym słowie \(pref_k(x)\). Co więcej, \(y\) i wszystkie jego sufiksy należące do zbioru słów reprezentowanych przez wierzchołek \(v\) występują jako sufiksy \(pref_k(x)\), natomiast słowa z tego samego zbioru dłuższe od \(y\) już nie. Z tego wynika słuszność rozbicia \(v\) na \(v'\) i \(v''\). Rozważyliśmy w tym momencie wszystkie podsłowa \(pref_k(x)\), zatem potrzeby rozbijania innych wierzchołków nie ma.
Dygresja: powyższe rozważania są także inną metodą udowodnienia liniowej liczby wierzchołków grafu podsłów - pokazaliśmy, że wraz z każdym kolejnym znakiem tekstu dodajemy do grafu jeden albo dwa wierzchołki.
Aby efektywnie aktualizować graf \(G_{k-1}\) do \(G_k\), potrzebujemy oprócz dowiązań sufiksowych jeszcze dodatkowej informacji zapamiętywanej dla krawędzi. Krawędzie dzielimy na:
- twarde - krawędzie tworzące najdłuższe ścieżki z korzenia do wszystkich wierzchołków grafu; innymi słowy przejście wyłącznie krawędziami twardymi z korzenia \(root\) do dowolnego wierzchołka \(v\) generuje słowo \(Label(v)\),
- miękkie - wszystkie pozostałe.
Oznaczmy przez \(v_{tail_k}\) wierzchołek grafu \(G_k\), który zawiera ogon (sufiks \(tail\) zgodnie z wcześniejszą definicją) słowa \(pref_k(x)\). Wyróżnijmy też ujście grafu \(G_k\) - wierzchołek \(sink_k\) taki, że \(EndPos(sink_k) = \lbrace k \rbrace\). Łatwo zauważyć, że w każdej fazie tworzymy nowe ujście, które podłączamy do ujścia poprzedniego oraz inicjalnie (dla słowa pustego) ujście jest korzeniem: \(sink_0 = root\). Ujście jest jednym z co najwyżej dwóch wierzchołków, które tworzymy w jednej iteracji algorytmu.
Użycie dowiązań sufiksowych oraz rozróżnianie pomiędzy krawędziami twardymi i miękkimi pozwala szybko znajdować wierzchołek, który potencjalnie należy rozbić. Zauważmy bowiem, że \(Suf(sink_{k-1}) = v_{tail_{k-1}}\), a zatem jeśli \(x_k = \alpha\) i znajdziemy najmniejsze takie \(j\), że \(Suf^j(sink_{k-1}) = v\), gdzie \(v\) zawiera krawędź \(v \stackrel{\alpha}{\to} w\), to wtedy \(w = v_{tail_k}\). Jeśli takie \(j\) nie istnieje, tzn. przechodząc dowiązaniami sufiksowymi począwszy od \(sink_{k-1}\) dojdziemy aż do korzenia \(root\) i nie znajdziemy wierzchołka o wychodzącej krawędzi etykietowanej \(\alpha\), to znaczy, że \(tail_k\) jest słowem pustym i tym samym symbol \(\alpha\) wystąpił po raz pierwszy w \(pref_k(x)\).
Jeśli jednak takie \(v\) istnieje, to \(w\) należy rozbić na \(w'\) i \(w''\) wtedy i tylko wtedy, gdy krawędź \(v \stackrel{\alpha}{\to} w\) jest miękka. Zapiszmy bowiem \(tail_k\) jako \(y \alpha\). Podsłowo \(y\) występuje przynajmniej dwukrotnie w \(pref_{k-1}\) i jest poprzedzone zawsze tym samym znakiem \(\beta\). W przeciwnym wypadku krawędź \(v \stackrel{\alpha}{\to} w\) byłaby twarda i zachodziłoby \(Label(w) = y \alpha\). Co więcej \(\alpha \neq \beta\), bo w przeciwnym wypadku \(y\alpha\) nie byłoby najdłuższym sufiksem występującym przynajmniej dwukrotnie w \(pref_k(x)\), czyli nie byłoby słowem \(tail_k\). To znaczy, że właśnie powstało nowe wystąpienie \(y \alpha\), przed którym znajduje się inny znak, niż przed każdym wcześniejszym wystąpieniem tego słowa i należy dokonać rozbicia węzła \(w\).
Rozważyliśmy już wszystkie koniecznie aktualizacje grafu po dodaniu nowego znaku oraz opisaliśmy pomocne rozróżnienie krawędzi. Możemy teraz przystąpić do określenia pełnego algorytmu.
Twierdzenie
Powyższy algorytm konstruuje graf podsłów słowa \(x\) o długości \(n\) w czasie \(O(n)\).
Uwaga: podobnie jak w rozdziale poprzednim zakładamy, że mamy do czynienia z alfabetem stałego rozmiaru. W przeciwnym wypadku należy przemnożyć złożoność czasową przez czynnik \(O(\log \vert \Sigma \vert)\).
Dowód
Każdą operację w algorytmie poza rozbiciem wierzchołka wykonujemy w czasie stałym. Stworzenie nowego wierzchołka \(v'\) zajmuje czas proporcjonalny do liczby krawędzi wychodzących z klonowanego wierzchołka \(v\) - czas ten jest sumarycznie ograniczony przez liczbę wszystkich krawędzi grafu, których jest liniowo wiele. Jedynym potencjalnie problematycznym punktem jest ostatnia pętla while, która nie dodaje nowych krawędzi (jedynie przekierowuje istniejące) i na pierwszy rzut oka wydaje się, że tam właśnie złożoność może się zepsuć. Dla uproszczenia dowodu będziemy obliczać liczbę iteracji obu pętli while pomimo wiedzy, że liczba iteracji pierwszej z nich musi być ograniczona ze względu na udowodniony wcześniej liniowy rozmiar grafu.
Oznaczmy przez \(Depth(v)\) głębokość dowiązań sufiksowych wierzchołka \(v\), tzn. taką najmniejszą liczbę \(j\), że \(Suf^{j} (v) = root\). Wtedy niech \(SufPath(v)\) będzie zbiorem wierzchołków \(\lbrace Suf^1(v),\, Suf^2(v), \ldots,\, Suf^{Depth(v)}(v) \rbrace\). Rozważmy parę wierzchołków \(v\) i \(w\) takich, że krawędź \(v \stackrel{\alpha}{\to} w\) jest twarda. Z tego wynika, że dla każdego \(w' \in SufPath(w)\) istnieje krawędź \(v' \stackrel{\alpha}{\to} w'\), gdzie \(v' \in SufPath(v)\) i nie istnieją inne krawędzie o etykiecie \(\alpha\) wchodzące do wierzchołków ze zbioru \(SufPath(w)\). Zatem jeśli sumarycznie z wierzchołków należących do \(SufPath(v)\) wychodzi \(k_1\) twardych oraz \(k_2\) miękkich krawędzi \(\alpha\), to zachodzi
$$\vert SufPath(w) \vert = k_1 + 1 = \vert SufPath(v) \vert - k_2 + 1.$$
Wróćmy do kodu obu pętli while. W \(i\)-tej fazie algorytmu zaczynamy od stworzenia krawędzi twardej \(sink_{i-1} \stackrel{\alpha}{\to} sink_i\). Zarówno w jednej jak i drugiej pętli tworzymy nowe albo przyłączamy już istniejące miękkie krawędzie z wierzchołków ze zbioru \(SufPath(sink_{i-1})\) do wierzchołków ze zbioru \(SufPath(sink_i)\). Z powyższej równości wynika, że z każdą taką miękką krawędzią metaforycznie "skracamy" zbiór \(SufPath(sink_i)\). Nie należy jeszcze zapominać o sytuacji, gdy rozbijamy pewien wierzchołek na ścieżce sufiksowej. Wtedy wkładamy nowy wierzchołek gdzieś w środku \(SufPath(sink_i)\). Finalnie otrzymujemy nierówność:
$$\vert SufPath(sink_{i}) \vert \leq \vert SufPath(sink_{i-1}) \vert - k + 2,$$
gdzie \(k\) oznacza sumaryczną liczbę obrotów obu pętli while w \(i\)-tej fazie algorytmu. Oczywisty wniosek: łączna liczba obrotów pętli jest liniowa ze względu na długość tekstu, co kończy dowód.
Zastosowania
Graf podsłów ma wszystkie atuty drzewa sufiksowego oraz kilka dodatkowych:
- Pomimo niebanalnej teorii stojącej za nim, algorytm liniowej konstrukcji grafu podsłów jest prostszy, niż analogiczny algorytm dla drzewa sufiksowego.
- Wygoda implementacyjna i użytkowa wynikająca z nieskompresowanej postaci grafu.
- Grafy podsłów także można kompresować. Dla niektórych tekstów otrzymujemy w ten sposób reprezentację rozmiaru subliniowego.
- Konstrukcja grafu może także pomóc w dostrzeżeniu pewnych regularności w tekstach. Ciekawym przykładem są grafy podsłów dla słów Fibonacciego.