Informatyka MIMUW

Pokażemy konstruktywnie następujący istotny fakt:

jeśli znamy tablicę sufiksową i tablicę \( lcp \), to drzewo sufiksowe dla danego tekstu możemy łatwo skonstruować w czasie liniowym.

Przypuśćmy, że \( SUF\ =\ [i_1,i_2,\ldots,i_n] \), a więc:

\( sufiks_{i_1} < sufiks_{i_2} < sufiks_{i_3} < \ldots sufiks_{i_n}. \)

Algorytm Drzewo-Sufiksowe

  T := drzewo reprezentujące sufiks(i_1) (jedna krawędź); 
  for k:=2 to n do 
    wstaw nową ścieżkę o sumarycznej etykiecie sufiks(i_k) do T;

Rysunek 3: Wstawianie kolejnego sufiksu \( sufiks_{i_k} \) do drzewa sufiksowego, przed włożeniem wszystkie krawędzie ścieżki roboczej od \( u \) do korzenia są skierowane w lewo.

Opiszemy w jaki sposób wstawiamy kolejny sufiks \( \beta \) do drzewa. Operacja ta jest zilustrowana na rysunku. Załóżmy, że w każdym węźle drzewa trzymamy długość tekstu, który ten węzeł reprezentuje (jako pełna etykieta od korzenia do węzła).

Niech \( \alpha \) będzie poprzednio wstawionym sufiksem, a \( u \) ostatnio utworzonym liściem.

Wtedy wstawienie \( \beta \) polega na znalezieniu maksymalnego wspólnego prefiksu \( \gamma_1 \) tekstów \( \alpha \), \( \beta \). Niech \( \beta=\gamma_1\cdot \gamma_2 \). Znajdujemy węzeł \( v \) odpowiadający ścieżce od korzenia etykietowanej \( \gamma_1 \).

Kluczowym pomyslem algorytmicznym jest tutaj 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 tworzymy nowy liść \( w \) odpowiadający sufiksowi \( \beta \), oraz krawędź \( (v,w) \) etykietowaną \( \gamma_2 \).

Z tablicy \( lcp \) odczytujemy długość \( \gamma_1 \).

W celu obliczenia \( v \) posuwamy się ścieżką od \( u \) w górę drzewa, aż znajdziemy węzeł oddalony od korzenia o \( |\gamma| \).

Przechodząc drzewo posuwamy się po węzłach drzewa, przeskakując (w czasie stalym) potencjalnie długie teksty na krawędziach.

Koszt operacji wstawienia jest proporcjonalny do sumy: jeden plus zmniejszenie głębokości nowego liścia w stosunku do starego. Suma tych zmniejszeń jest liniowa. \( \gamma_1 \) 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 \( |\gamma_1|= lcp[k-1] \). Wiemy kiedy się zatrzymać idąc do góry od węzła \( u \) w kierunku korzenia.

Lokalnie wykonana praca w jednej iteracji jest zamortyzowana zmniejszeniem się głębokości aktualnego liścia w stosunku do poprzedniego. W sumie praca jest liniowa.

Historia algorytmu jest pokazana dla przykładowego tekstu na rysunkach.

Rysunek 4: Pierwsze 6 iteracji algorytmu Drzewo-Sufiksowe dla tekstu \( babaabababba\# \).

Rysunek 5: Ostatnie 6 iteracji algorytmu Drzewo-Sufiksowe dla tekstu \( babaabababba\# \).