Rozdział 8: Tablice sufiksowe

Oznaczmy przez $Subwords(x)$ wszystkie podsłowa tekstu $x$, a wszystkie wystąpienia (początkowe pozycje) słowa $z$ w słowie $x$ oznaczmy przez $Occ(z,\, x)$. Oznaczenie $Occ$ jest skrótem od ang. occurrences. Chcemy znaleźć taką reprezentację zbioru $Subwords(x)$, by można było łatwo odpowiedzieć na pytanie, czy $z \in Subwords(x)$, co jest równoważne $Occ(z,\, x) \neq \emptyset$, jak również rozwiązywać inne problemy tekstowe. Poza tym chcemy, by rozmiar tej reprezentacji był liniowy, podczas gdy rozmiar $Subwords(x)$ może być kwadratowy. Spośród wielu dobrych reprezentacji najprostszymi są tablice sufiksowe (oznaczane przez $SA$ - suffix array).

Niech $x = a_{1}a_{2}\dots a_{n}$ i niech $x_{n+1}=\#$ będzie specjalnym znakiem leksykograficznie większym od każdego innego symbolu (czasami będziemy również używać $x_{n+1}=\#$ jako najmniejszego leksykograficznie symbolu). Oznaczmy przez $sufiks_{i}=a_{i}a_{i+1}\dots a_{n}$ sufiks tekstu $x$ zaczynający się na pozycji $i$-tej. Niech $SA[k]$ będzie pozycją, od której zaczyna się $k$-ty leksykograficznie sufiks $x$. Sufiks zaczynający się na pozycji $(n+1)$-szej nie jest brany pod uwagę. Ciąg sufiksów posortowany leksykograficznie wygląda następująco:

$$sufiks_{SA[1]} < sufiks_{SA[2]} < sufiks_{SA[3]} < \ldots < sufiks_{SA[n]}$$

Przykład.
Rozważmy tablicę sufiksową $SA_n$ dla n-tego słowa Thue-Morse'a:
$$\tau_0=0,\ \tau_1=01,\ \tau_2=0110,\ \tau_3=01101001.$$
$$SA_1 = 0\;1,\, SA_2 = 3\;0\;2\;1,\, SA_3 = 5\;6\;3\;0\;7\;4\;2\;1$$

Dla parzystych $n$ konstruujemy tablicę z poprzedniej następująco.

Załóżmy, że $SA_{n-1}$ składa się z połówek $\alpha,\, \beta$. Wtedy
$$SA_n = (2\beta + 1,\, 2\alpha,\, 2\beta,\, 2\alpha+1).$$
Dla nieparzystych $n$ robimy poprawkę: początek drugiej ćwiartki przenosimy na pozycję $p(n)+1$, a początek ostatniej ćwiartki przenosimy na początek trzeciej ćwiartki.

Liczby $p(n)$ zadane są poprzez
$$p(3)=1,\ p(n+2)=4 \cdot p(n)+1.$$
Równoważnie
$$p(2n+1) = (4^n-1)/3+1.$$

Zamiast tablicy SA można wprowadzić tablice posortowanych cyklicznych przesunięć (pierwsze pozycje). Wtedy dla słów Thue-Morse'a tablice takie konstruujemy podobnie jak tablice SA, ale dużo prościej, nie jest wymagana poprawka.

Przykład.
Jako drugi przykład rozważmy słowa Fibonacciego kończące się literą a. Niech $N$ będzie długością słowa.

Dla tych słów tablica sufiksowa, jako ciąg, jest postępem arytmetycznym (modulo $N$, numeracja pozycji zaczyna się od zera). Pierwszym elementem ciągu jest $N-1$ (ostatnia pozycja - odpowiada to sufiksowi składającemu się z jednej litery a). Różnicą postępu arytmetycznego jest liczba Fibonacciego.

Dla słów Fibonacciego tablice przesunięć cyklicznych jako ciągi są postępami arytmetycznymi. Zachodzi następujący fakt:

Fakt.
Zbiór wystąpień dowolnego wzorca w słowie Fibonacciego (pierwsze pozycje) jest postępem arytmetycznym (modulo długość całego słowa).

Oznaczmy przez $LCP[k]$ długość wspólnego prefiksu $k$-tego i następnego sufiksu w kolejności leksykograficznej. Tablica sufiksowa ma następującą przydatną własność. Niech
$$
\begin{split}
& first_{z} = \min \lbrace k : z \text{ jest prefiksem } sufiks_{SA[k]}\rbrace \\
& last_{z} = \max \lbrace k : z \text{ jest prefiksem } sufiks_{SA[k]}\rbrace \\
\end{split}
$$

Wtedy $Occ(z,\, x)$ jest przedziałem w tablicy sufiksowej od $first_{z}$ do $last_{z}$.

Szukanie podsłów

Pokażemy, jak sprawdzać, czy $z$ występuje w $x$ używając w tym celu tablicy sufiksowej.

Możemy sprawdzić, czy $z$ jest prefiksem $i$-tego sufiksu w czasie $O(m)$. Korzystając z tego, wykonujemy rodzaj binarnego szukania. W ten sposób znajdujemy pierwszy sufiks, którego prefiksem jest $z$. Jeśli jest taki sufiks, to $z \in Subwords(x)$. W przeciwnym wypadku $z$ nie jest podsłowem $x$. Podobnie znajdujemy ostatni sufiks. Zbiór wystąpień odpowiada przedziałowi w tablicy $SA$ między obliczonymi pierwszym i ostatnim sufiksem zaczynającym się od $z$. Złożoność czasowa algorytmu wynosi $O(m \log n)$.

Wyznaczanie liczby podsłów

Pokażemy, jak znaleźć liczbę podsłów słowa $x$ przy pomocy tablicy sufiksowej. Końcowego znacznika $\#$ nie traktujemy jako części słowa $x$. Liczba podsłów jest równa $\vert Subwords(x) \vert $. Jeśli wszystkie symbole słowa są różne to oczywiście $\vert Subwords(x) \vert = \binom{n + 1}{2}$. W przeciwnym wypadku liczymy
$$\binom{n+1}{2} - \sum_i LCP[i]$$

Pozostawiamy jako ćwiczenie uzasadnienie tego, że liczba podsłów jest poprawnie obliczona. Mając tablicę sufiksową oraz LCP algorytm działa oczywiście w czasie $O(n)$.

Przykład

Dla przykładowego tekstu $x = babaabababba$ tablica sufiksowa prezentuje się następująco (dla czytelności podano także pełne sufiksy, w rzeczywistości operujemy wyłącznie liczbami identyfikującymi sufiksy):

4: aabababba#
2: abaabababba#
5: abababba#
7: ababba#
9: abba#
12: a#
3: baabababba#
1: babaabababba#
6: bababba#
8: babba#
11: ba#
10: bba#

Pogrubioną czcionką oznaczono najdłuższe wspólne prefiksy kolejnych dwóch słów tworzących tablicę sufiksową. Wartości $LCP$ wynoszą zatem kolejno: 1, 3, 4, 2, 1, 0, 2, 4, 3, 2, 1. Korzystając ze wzoru na liczbę różnych podsłów mamy
$$\binom{n+1}{2} - \sum_{i = 1}^{n - 1 = 11} LCP[i] = 78 - 23 = 55.$$

Podobnie jak tablicę sufiksową możemy zdefiniować tablicę $ROT$, odpowiadającą posortowanemu ciągowi wszystkich cyklicznych przesunięć słowa $x$ (rotacji $x$). Pozostawiamy jako ćwiczenie znalezienie liniowego algorytmu obliczania tablicy $ROT$, przy założeniu, że mamy liniowy algorytm obliczania tablicy sufiksowej.

Dygresja. Ciekawą klasę słów, dla których tablice $SA$ i $ROT$ są szczególnie interesujące, stanowią słowa Fibonacciego $Fib_n$. W tym szczególnym przypadku załóżmy, że pozycje numerujemy od zera. Dla każdego $n$ tablica $ROT$ jest postępem arytmetycznym (modulo długość słowa). Natomiast tablica $SA$ jest postępem arytmetycznym, gdy $n$ jest parzyste. Ciekawym ćwiczeniem jest znalezienie wzoru na $\vert Subwords(Fib_n)\vert$.

Obliczanie tablicy $LCP$

Niech $rank(i)$ będzie pozycją $sufiks_i$ w porządku leksykograficznym. W naszym przykładowym słowie mamy:
$$ rank = [8,\, 2,\, 7,\, 1,\, 3,\, 9,\, 4,\, 10,\, 5,\, 12,\, 11,\, 6] $$

Niech $LCP'[k] = LCP[rank[k]-1]$. Załóżmy dla uproszczenia, że $LCP[0] = 0$ oraz że tekst kończy się specjalnym symbolem. Obliczamy tablice $LCP',\, LCP$ następująco:

Algorytm Oblicz-LCP

Ze względów notacyjnych tablica $LCP'$ oznaczana jest przez LCPp.

for i := 1 to n do
    rank[SA[i]] := i;
l := 0;
for i := 1 to n do
begin
    if (rank[i] > 1) then
        while (x[l + i] = x[l + SA[rank[i] - 1]]) do
            l := l + 1;
    LCPp[i] := l;
    if (l > 0) then
        l := l - 1;
end;

Pozostawiamy jako ćwiczenie dowód tego, że
$$ LCP'[k] \geq LCP'[k-1]-1$$.

Jeśli $LCP'[k-1] - 1 = t$, to $LCP'[k]$ obliczamy sprawdzając symbol po symbolu (od lewej do prawej) zgodność prefiksów odpowiednich słów startując od pozycji $t$. W ten sposób sumaryczny koszt jest liniowy. W każdej iteracji cofamy się o jeden, a potem idziemy "do przodu" (sprawdzając kolejne symbole). Jest to analiza typu "jeden krok do tyłu i kilka do przodu". Liczba iteracji jest liniowa, więc liczba kroków do tyłu też. Ponieważ odległość "do celu" jest liniowa, to suma kroków też jest liniowa.

Słownik podsłów bazowych i konstrukcja tablicy sufiksowej w czasie $O(n \log n)$

Opiszemy uproszczoną wersję algorytmu Karpa-Millera-Rosenberga (w skrócie algorytmu KMR) rozwiązywania problemów tekstowych metodą słownika podsłów bazowych. Ustalmy pewien tekst $x$ długości $n$. Zakładamy w tej sekcji, że dodatkowym symbolem jest $x_{n+1}=\#$, leksykograficznie największy symbol. Przez segment $k$-bazowy rozumiemy segment tekstu $x[i .. i+2^k-1]$ długości $2^k$ lub kończący się na $x_{n+1}$. W praktyce programistycznej możemy przyjąć, że po symbolu $\#$ mamy bardzo dużo takich symboli na prawo i każdy segment startujący w $x[1 .. n]$ ma dokładnie długość $2^k$.

Słownik podsłów bazowych słowa $x$ (w skrócie $DBF(x)$, od ang. dictionary of basic factors) składa się z $\log n$ tablic $DBF_0$, $DBF_1$, $DBF_2$, $ \ldots DBF_{\left\lceil \log n \right\rceil}$. Przyjmujemy, że $DBF_k[i]$ jest pozycją słowa $x[i..i+2^k-1]$ na posortowanej liście (bez powtórzeń) wszystkich podsłów długości $2^k$ słowa $x$. Jeśli długość "wystaje" poza koniec $x$ to przyjmujemy, że są tam (umownie) same symbole $\#$.

Algorytm liczenia tablic $DBF$ jest bardzo prosty. Załóżmy od razu, że symbole są ponumerowane leksykograficznie. Wtedy $DBF_0$ jest zasadniczo równa tekstowi $x$. Wyznaczamy $DBF_{k+1}$ na podstawie $DBF_k$ w następujący sposób. Dla każdego $i$ tworzymy nazwę-kompozycję słowa $x[i..i+2^{k+1}-1]$ jako parę liczb naturalnych $(DBF_k[i],\, DBF_k[i+2^k])$. Sortujemy te pary w czasie liniowym algorytmem sortowania pozycyjnego (RadixSort) i w ten sposób otrzymujemy tablicę, która koduje (w porządku leksykograficznym) każdą parę liczbą naturalną (pozycją w porządku leksykograficznym). Wartością $DBF_{k+1}[i]$ jest kod pary $(DBF_k[i],\, DBF_k[i+2^k])$.

Zauważmy, że tablica sufiksowa odpowiada tablicy $DBF_{\lceil \log n \rceil}$. Możemy to podsumować następująco:

Słownik $DBF(x)$ możemy skonstruować w czasie $ O(n \log n) $ i pamięci $O(n \log n)$ (jest to również rozmiar słownika).
Tablicę sufiksową możemy otrzymać, stosując algorytm KMR, w czasie $O(n \log n)$ i pamięci $O(n)$ (potrzebujemy pamiętać jedynie ostatnie dwa wiersze tablicy $DBF$ w każdej iteracji).

Konstrukcja tablicy $SA$ w czasie $O(n)$: algorytm KS

Opiszemy teraz błyskotliwy algorytm Kärkkäinena-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$ zawiera co trzecią pozycję w tekście: $N = \lbrace 3,\, 6,\, 9,\, 12,\, 15 \ldots \rbrace$
Zbiór $M$ zawiera pozostałe pozycje: $M = \lbrace 1,\, 2,\, 4,\, 5,\, 7,\, 8,\, 10,\, 11 \ldots \rbrace$

Przez $SA_M$, oznaczmy tablicę sufiksową dla pozycji ze zbioru $M$, podobnie zdefiniujmy $SA_N$. $SA_M$ daje posortowany ciąg sufiksów zaczynających się na pozycjach ze zbioru $M$.

Przykład

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

$ M = \lbrace 1,\, 2,\, 4,\, 5,\, 7,\, 8,\, 10,\, 11 \rbrace $
$ N = \lbrace 3,\, 6,\, 9 \rbrace $
$SA_M = [4,\, 2,\, 5,\, 7,\, 11,\, 1,\, 10,\, 8]$
$SA_N = [3,\, 6,\, 9]$

Sprowadzenie obliczania $SA_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 RadixSort. 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:

$$
\begin{split}
& y1 = kod(a_1 a_2 a_3) \cdot kod(a_4 a_5 a_6) \ldots kod(a_{n-2} a_{n-1} a_n) \\
& y2 = kod(a_2 a_3 a_4) \cdot kod(a_5 a_6 a_7) \ldots kod(a_{n-1} a_{n} a_{n+1}) \\
\end{split}
$$

$$compress(x) = y1 \; \& \; y2$$
gdzie $\&$ jest nowym maksymalnym symbolem.

Przykład

Weźmy początkowy przykład $x = babaababbba\#$, gdzie $\#$ jest największym leksykograficznie symbolem. 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) = \langle z \rangle $. Wtedy

$$
\begin{split}
& y1 = \langle bab \rangle \langle aab \rangle \langle aba \rangle \langle bba \rangle = 3\, 1\, 2\, 5 \\
& y2 = \langle aba \rangle \langle aba \rangle \langle bab \rangle \langle ba\# \rangle = 2\, 2\, 3\, 4 \\
\end{split}
$$

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

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

Algorytm Kärkkäinen-Sanders

$x' := compress(x)$;
Obliczamy tablicę sufiksową dla $x'$ rekurencyjnie;
Obliczamy $SA_M$ w czasie liniowym, znając tablicę sufiksową dla $x'$;
Obliczamy $SA_N$ w czasie liniowym (bez rekursji), znając $SA_M$;
Scalamy posortowane ciągi $SA_M,\, SA_N$ w tablicę sufiksową dla całego słowa $x$;

Krok 1. algorytmu sprowadza się do RadixSort, podobnie jak w algorytmie KMR. Kroki 3. i 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. Jeśli nie, to mamy dwa przypadki.

Przypadek 1.
Mamy sufiks typu $M$ na pozycji $i \bmod 3 = 1$ oraz pewien sufiks typu $N$ na pozycji $j$. Porównujemy ze sobą pary $(x[i],\, sufiks_{i+1})$ i $(x[j],\, sufiks_{j+1})$. Ponieważ $i + 1 \bmod 3 = 2$ i $j + 1 \bmod 3 = 1$, to oba te sufiksy są typu $M$, zatem można je porównać w czasie stałym.

Przypadek 2.
Mamy sufiks typu $M$ na pozycji $i \bmod 3 = 2$ oraz pewien sufiks typu $N$ na pozycji $j$. Tym razem porównujemy trójki $(x[i],\, x[i+1],\, sufiks_{i+2})$ i $(x[j],\, x[j+1],\, sufiks_{j+2})$. Ponieważ $i + 2 \bmod 3 = 1$ i $j + 2 \bmod 3 = 2$, to oba te sufiksy są typu $M$, zatem można je porównać w czasie stałym.

Niech $T(n)$ będzie czasem działania algorytmu KS. Zachodzi
$$T\left (n \right) = T \left( \left\lceil \frac{2}{3}\cdot n \right\rceil \right) + O\left( n \right).$$
Rozwiązaniem jest $T(n) = O(n)$. Mamy więc liniowy algorytm liczenia tablicy sufiksowej.

Informatyka MIMUW