Relacje między drzewami i tablicami sufiksowymi

Pokażemy najpierw jak skonstruować tablicę sufiksową mając drzewo sufiksowe.

W celu znalezenia początkowych pozycji sufiksów w porządku leksykograficznym przechodzimy drzewo sufiksowe metodą DFS, zakładając, że dla każdego węzła lista jego synów podana jest w kolejności leksykograficznej etykiet krawędzi prowadzących do synów. Wystarczy sprawdzać piewsze symbole tych etykiet. Załóżmy, że w liściach mamy początki sufiksów, które do nich prowadzą. Kolejność odwiedzania liści w naszym przejściu metodą DFS automatycznie generuje elementy tablicy sufiksowej.

Pokażemy teraz jak skonstruować drzewo sufiksowe mając tablicę sufiksową. Dowiedziemy konstruktywanie następujący istotny fakt: jeśli znamy tablicę sufiksową \(SA\) i tablicę \(LCP\), to drzewo sufiksowe dla danego tekstu możemy skonstruować w czasie liniowym.

Przypuśćmy, że \(SA = [i_1,\, i_2,\ldots,\, i_n]\), a więc:
$$sufiks_{i_1} < sufiks_{i_2}< sufiks_{i_3}< \ldots sufiks_{i_n}.$$

Opiszemy w jaki sposób wstawiamy kolejny sufiks \(sufiks_{i_k}\) do drzewa. Załóżmy, że w każdym węźle drzewa trzymamy długość tesktu, który ten węzeł reprezentuje (jako pełna etykieta od korzenia do węzła). Niech \(sufiks_{i_{k-1}}\) będzie poprzednio wstawionym sufiksem, a \(u\) poprzednio utworzonym liściem. Wtedy wstawienie \(sufiks_{i_k}\) polega na znalezieniu maksymalnego wspólnego prefiksu \(p\) tekstów \(sufiks_{i_{k-1}}\) i \(sufiks_{i_k}\). Niech \(sufiks_{i_k} = p \cdot s\). Znajdujemy węzeł \(v\) odpowiadający ścieżce od korzenia etykietowanej \(p\). Podstawowym trikiem jest to, że węzła \(v\) szukamy nie od korzenia, ale od ostatnio utworzonego liścia \(u\). Jeśli takiego węzła \(v\) nie ma (jest wewnątrz krawędzi) to go tworzymy. Następnie dodajemy nowy liść \(w\), odpowiadający sufiksowi \(sufiks_{i_k}\) oraz krawędź \((v,\, w)\) etykietowaną \(s\).

Z tablicy \(LCP\) odczytujemy długość słowa \(p\). W celu znalezienia \(v\) posuwamy się ścieżką od \(u\) w górę drzewa, aż znajdziemy węzeł oddalony od korzenia o \(\vert p \vert\). Przechodząc drzewo przemieszczamy się po węzłach drzewa, przeskakując potencjalnie długie teksty na krawędziach. Koszt operacji wstawienia wynosi \(Depth(u) - Depth(v) + O(1)\) - najpierw wykonujemy tyle cofnięć, ile trzeba aby przejść z \(u\) do \(v\), a potem dodajemy nowy liść. Po każdym dodanym liściu zwiększamy głębokość o 1, zatem sumaryczna liczba cofnięć jest liniowa i cały algorytm działa w czasie \(O(n)\).

Słowo \(p\) jest najdłuższym wspólnym prefiksem słów \(sufiks_{i_{k-1}}\) i \(sufiks_{i_k}\). Kluczowe znaczenie w operacji ma znajomość wartości \(\vert p \vert = LCP[k-1]\) - wiemy kiedy się zatrzymać idąc do góry od węzła \(u\) w kierunku korzenia.

Szkielet grafu podsłów

Graf podsłów tak naprawdę powinien nazywać się grafem sufiksów, w sposób istotny rozróżnia on sufiksy i niesufiksy danego tekstu. Każda ścieżka od źródła do ujścia w tym grafie reprezentuje pewien sufiks (ale niekoniecznie każdy sufiks jest taką ścieżką, może się kończyć wewnątrz grafu). Jeśli mamy dwa słowa \(w\) i \(v\), z których jedno jest sufiksem a drugie nie jest, to nie prowadzą one do tego samego węzła. Pokażemy pewne związki między trzema strukturami danych reprezentującymi sufiksy słowa.

Zanim przejdziemy do relacji między grafami podsłów i drzewami sufiksowymi pokażemy, że graf podsłów jest w istocie zadany przez drzewo składające się z krawędzi na najdłuższych ścieżkach (krawędzie twarde z poprzedniego rozdziału). Drzewo to nazywamy szkieletem grafu podsłów słowa \(w\) i oznaczmy przez \(S=Szkielet(w)\). Każdy węzeł \(S\) utożsamiamy ze słowem reprezentującym ścieżkę od korzenia do tego węzła. Jeśli mamy drzewo \(S\), to tablica dowiązań sufiksowych jest liczona tak samo jak tablica prefikso-sufiksów dla pojedynczego tekstu:

• \(Suf(u)\) jest najdłuższym właściwym (być może słowem pustym - korzeniem \(S\)) sufiksem \(u\), który należy do \(S\).
• Liczenie dowiązań sufiksowych odpowiada liczeniu tablicy \(P\) dla drzewa wielu wzorców, patrz rozdział 12.

Zostaje jedynie uzupełnienie grafu podsłów pozostałymi krawędziami (krawędziami miękkimi).

Relacje między drzewami sufiksowym i grafami podsłów

W drzewie sufiksowym załóżmy, że wszystkie sufiksy tekstu odpowiadają wierzchołkom, choćby miały one mieć tylko jednego syna. Można sztucznie dodac na końcu tekstu jakiś znacznik (ang. endmarker), który powoduje utworzenie takich wierzchołków, a następnie znacznik ten usunąc.

Zatem niech \(T\) będzie drzewem sufiksowym słowa \(w\), natomiast \(S = Szkielet(w^R)\) będzie szkieletem grafu podsłów odwróconego słowa \(w^R\). Oznaczmy przez \(Nodes(T)\) zbiór podsłów odpowiadających węzłom drzewa \(T\) i \(Nodes(S)\) zbiór podsłów odpowiadających węzłom grafu \(S\).

Lemat
Niech dane będą \(S = Szkielet(w^R)\) i \(T\) - drzewo sufiksowe słowa \(w\) z dodanymi węzłami dla wszystkich sufiksów \(w\) (dodajemy endmarker w czasie konstrukcji drzewa, a na końcu usuwamy). Wtedy zachodzi:

1. Reprezentanci węzłów drzewa \(S\) są odwotnościami reprezentantów węzłów drzewa \(T\), inaczej mówiąc \(Nodes(S) = \lbrace u^R : u \in Nodes(T) \rbrace \).
2. Drzewo \(S\) jest drzewem dowiązań sufiksowych drzewa \(T\).

Dowód

1. \(Nodes(T)\) to słowa, które są sufiksami \(w\) lub takie, które mają dwa różne rozszerzenia w prawo w słowie \(w\). Z drugiej strony \(Nodes(S)\) to słowa, które są prefiksami \(w\) lub takie, które mają dwa różne rozszerzenia w lewo w słowie \(w^R\). Zauważmy, że w odwróconym tekście sufiks staje się prefiksem, a rozszerzenie w prawo staje się rozszerzeniem w lewo. Dowodzi to punktu (1).
2. Drzewo dowiązań sufiksowych daje porządek, w jakim usuwamy symbole od początku słowa do końca. Zatem jeśli tekst odpowiadający węzłowi \(v\in T\) jest równy \(w = s_1 s_2 \ldots s_k\), to usuwamy w kolejności \(s_1\), \(s_2\) itd. Natomiast jeśli odwrócimy kolejność (będziemy wtedy wstawiać to, co usuwaliśmy w odwrotnej kolejności), to otrzymamy słowo \(s_k s_{k-1} \ldots s_1\), które odpowiada słowu \(w^R\). Inaczej mówiąc odwrotności krawędzi drzewa sufiksowego czytane od korzenia do danego węzła \(v\) dają ścieżkę od korzenia do węzła odpowiadającego \(v\) w grafie podsłów. Wynika stąd bezpośrednio teza punktu (2), co kończy uzasadnienie prawdziwości lematu.