Informatyka MIMUW

Opiszemy teraz błyskotliwy algorytm Karkkainena-Sandersa ( w skrócie KS) będący zoptymalizowaną wersją algorytmu KMR liczenia tablicy sufiksowej. Zauważmy, że algorytm KMR oblicza znacznie więcej niż tablica sufiksowa, ponieważ konstruuje słownik podsłów bazowych wielkości $n \log n$ (mający liczne inne zastosowania, ale jako całość być może niepotrzebny przy liczeniu tablicy sufiksowej)

Główną częścią algorytmu KS jest obliczanie częściowej tablicy sufiksowej w sposób rekurencyjny. Rozbijmy zbiór pozycji [1..n] tekstu $x$ na dwa zbiory N, M  :

Zbiór N składa się z co trzeciej pozycji, a M jest zbiorem pozostałych pozycji.

N = {3,6,9,12,15,....}, M = {1,2,4,5,7,8,10,11,...}

Przez $SUF[M]$, oznaczmy tablicę sufiksową dla pozycji ze zbioru $M$, podobnie zdefiniujmy $SUF[N]$.

$SUF[M]$ daje posortowany ciąg sufiksów zaczynających się na pozycjach ze zbioru $M$.

Dla początkowego przykładowego tekstu $x\ =\ babaabababba\#$ mamy

$M\ =\ \{1,2,4,5,7,8,10,11\}\ \ \ \ \ N\ =\ \{3,6,9,12\}$

$SUF[M]\ =\ [4,\ 2,\ 5,\ 7, \ 1, \ 8,\ 11,\ 10]\ \ \ \ SUF[N]\ =\ [ 9,\ 12,\ 3,\ 6,]$

Sprowadzenie obliczania $SUF[M]$ do obliczania tablicy sufiksowej rozmiaru $\frac{2}{3}n$

Posortujmy leksykograficznie wszystkie podsłowa długości 3 w słowie $x$ korzystając z radix-sort. Każdemu takiemu słowu przyporządkujmy nazwę będącą jego pozycją w posortowanym leksykograficznie ciągu, oznaczmy $kod(z)$ otrzymaną nazwę podsłowa długości 3. Zakładamy, że $x$ kończy się dodatkowo dwoma symbolami $\#$, ale rozważamy tylko podsłowa zaczynające się w $x$. Dla uproszczenia załóżmy, że 3 jest dzielnikiem n.

Tworzymy nowe słowo $compress(x)$ w następujący sposób:

Przykład. Weźmy początkowy przykład $x\ = \ babaababbba\#$, gdzie $\#$jest większe niże a,b. Mamy

$aab \prec aba\prec bab \prec ba\# \prec bba$, Zatem kody tych trójek są kolejno $1,\ 2,\ 3,\ 4, \ 5$.

Oznaczmy$kod(z)= < z>$. Wtedy

$y1\ =\ < bab> < aab> < aba> < bba>\ =\ 3\ 1\ 2\ 5  ;$

$y2\ =\ < aba> < aba> < bab> < ba\#>\ =\ 2\ 2\ 3\ 4$

$compress(x)\ =\ =\ 3\ 1\ 2\ 5 \ \& \ 2\ 2\ 3\ 4\ $,

Jeśli mamy tablicę sufiksową dla słowa $compress(x)$, można łatwo obliczyć $SUF[M]$ w czasie liniowym. Pozostawiamy to jako ćwiczenie.

Algorytm ${\Large KS}$ (Karkkainen-Sanders)

x':= compress(x);
obliczamy tablicę sufiksową dla x' rekurencyjnie;
obliczamy SUF[M] w czasie liniowym, znając tablicę sufiksową dla x'; 
obliczamy SUF[N] w czasie liniowym (bez rekursji), znając SUF[M]; 
scalamy posortowane ciągi  SUF[M], SUF[N] w tablicę sufiksową dla całego słowa x 

Krok 1 algorytmu sprowadza się do radix-sortu, podobnie jak w algorytmie KMR. Kroki 3,4 są proste i ich implementację pozostawiamy czytelnikowi jako ćwiczenie.
Najważniejszy jest krok scalania. Mamy dwie posortowane listy sufiksów i trzeba je scalić w jedną posortowaną listę. Zasadniczym problemem jest implementacja operacji porównania leksykograficznego dwóch (długich) sufiksów w czasie stałym. Jeśli oba sufiksy są typu $M$ lub oba są typu $N$, to porównanie jest w czasie stałym, bo mamy posortowane listy takich sufiksów.

Pokażemy na przykładzie kluczową operację porównania sufiksu typu M z sufiksem typu N w czasie stałym.

Przykład

Nierówność $sufiks_2 < sufiks_{12}$ jest równoważna temu, że zachodzi co najmniej jeden z warunków:

1. $(a_2 < a_{12})$
2. $\ (a_2=a_{12}, a_3 < a_{13})$
3. $(a_2=a_{12}, a_3=a_{13}, sufiks_4 < sufiks_{14})$

Jednakże $4,14\in M$, zatem $sufiks_4$ i $sufiks_{14}$, są typu M i można je porównać w czasie stałym.

Niech $T(n)$ będzie czasem działania algorytmu KS. Zachodzi

$T(n) \ =\ T(\lceil \frac{2}{3}\cdot n \rceil) + O(n)$

Rozwiązaniem jest $T(n)=O(n)$. Mamy więc liniowy algorytm liczenia tablicy sufiksowej. Daje to również liniowy algorytm konstrukcji drzewa sufiksowego.

Istnieje kilka interesujących algorytmów, które konstruują drzewo sufiksowe w czasie liniowym, bez korzystania z tablicy sufiksowej (algorytmy Weinera, McCreighta, Ukkonena). W algorytmach tych współczynnik przy złożoności liniowej wynosi $\log |A|$, gdzie A jest alfabetem.