Rozdział 1: Elementy prostej kombinatoryki tekstów

Tekst jest ciągiem symboli. Przyjmujemy, że jest on zadany tablicą $x[1 .. n]$, elementami której są symbole ze skończonego zbioru $ \Sigma$ (zwanego alfabetem). Liczba $n=|x|$ jest długością (rozmiarem) tekstu. W większości naszych algorytmów jedyne operacje dopuszczalne na symbolach wejściowych to porównania dwóch symboli.

Algorytmy na tekstach wyróżniają się tym, że wykorzystują specyficzne, kombinatoryczne własności tekstów. Okresem tekstu $x$ jest każda niezerowa liczba naturalna $p$ taka, że $x[i]=x[i+p]$, dla każdego $i$, dla którego obie strony są zdefiniowane. Przez $ per(x) $ oznaczmy minimalny okres $x$. Zachodzi następująca ciekawa własność kombinatoryczna okresowości w tekstach.

Lemat o okresowości

Niech $nwd(p,\, q)$ oznacza najmniejszy wspólny dzielnik $p$ i $q$. Jeśli tekst $x$ ma okresy $p$, $q$ oraz $p+q \le |x|$, to $nwd(p,\, q)$ jest również okresem $x$.

Lemat ten wynika z poprawności algorytmu Euklidesa z odejmowaniem, który oblicza $nwd(p,\, q)$. Zauważmy, że jeśli $p > q$ są okresami, to $p-q$ też jest okresem.

Lemat o okresowości można wzmocnić, osłabiając założenia.

Silny lemat o okresowości

Jeśli tekst $x$ ma okresy $p$, $q$ oraz $p + q \le |x|+nwd(p,\, q)$, to $nwd(p,\, q)$ jest również okresem $x$.

Cyklicznym przesunięciem słowa $x$ jest każde słowo postaci $vu$, gdzie $x = uv$. Zastanówmy się nad możliwą liczbą cyklicznych przesunięć danego słowa.

Przykład

Rozważmy przesunięcia cykliczne słowa abaaaba. Mamy dokładnie 7 takich przesunięć:

abaaaba
aabaaab
baabaaa
abaabaa
aabaaba
aaabaab
baaabaa
abaaaba

Słowo $w$ nazywamy pierwotnym (nierozkładalnym), gdy nie można przedstawić $w$ jako konkatenacji wielu (co najmniej 2) kopii tego samego słowa. Tzn. jeśli można zapisać $w$ jako $x^k$ takie, że $k > 1$, to słowo $w$ nie jest pierwotne. Z lematu o okresowości wynika następujący fakt.

Lemat

Słowo pierwotne $x$ długości $p$ ma dokładnie $p$ różnych przesunięć cyklicznych.

Dowód

Przypuśćmy, że $x$ ma dwa przesunięcia równe co do wartości (jako słowa): $x = uv = u'v'$ oraz $vu = v'u'$, gdzie $u \neq u'$. Niech $|u'| < |u|$. Wtedy $u = u' \alpha,\, v'=\alpha \cdot v$ oraz $vu'\alpha = \alpha vu'$. Zatem słowo $\alpha \cdot v \cdot u' \cdot \alpha$ ma prefikso-sufiksy $\alpha \cdot v \cdot u'$ oraz $\alpha$. W konsekwencji tekst $\alpha \cdot v \cdot u' \cdot \alpha$ ma dwa okresy rozmiaru $r = \vert \alpha \vert $ oraz $p= \vert vu'\alpha \vert $. Jednocześnie zachodzi: $r+p = \vert\alpha \cdot v \cdot u' \cdot \alpha \vert$.

Z lematu o okresowości wynika, że tekst ma okres $nwd(r,\, p)$, którego długość jest w szczególności mniejsza od $p$, zatem $x$ jest potęgą słowa krótszego od siebie i nie jest pierwotne. A zatem $x$ nie może mieć dwóch takich samych przesunięć.

Pokażemy teraz proste zastosowanie w teorii liczb. W roku 1640 Pierre de Fermat pokazał następujący fakt.

Twierdzenie

Jeśli $ p$ jest liczbą pierwszą, to $p$ jest dzielnikiem liczby $n^p-n$ dla każdego naturalnego $n$. Na przykład $101\ | \ 10^{101}-10$.

Dowód

Definiujemy relację równoważności $x \equiv y$ gdy $x$ jest przesunięciem cyklicznym $y$. Mówimy, że słowo jest unarne, jeśli wszystkie jego litery są takie same.

Niech $S$ bedzie zbiorem słów nieunarnych długości $p$ nad alfabetem $\lbrace 1,\, 2,\ldots,\,n \rbrace $. Słowa te są pierwotne, gdyż ich długość jest liczbą pierwszą i nie są unarne. Zgodnie z poprzednim lematem każda klasa równoważności ma dokładnie $p$ elementów. Klasy te są rozłączne. Moc zbiorów $S$ jest równa $ n^p-n $ oraz $S$ można podzielić na rozłączne podzbiory o tej samej mocy $p$. Zatem moc $S$ jest podzielna przez $p$, a więc $p\ |\ n^p-n$.

Prefikso-sufiksy i tablica $P$

Pojęciem dualnym do okresu jest prefikso-sufiks tekstu. Jest to najdłuższy właściwy (nie będący całym tekstem) prefiks tekstu $x$ będący jednocześnie jego sufiksem. Oczywiste jest, że $|x|-per(x)$ jest długością prefikso-sufiksu $x$. Jeśli $per(x)=|x|$ to prefikso-sufiksem $x$ jest słowo puste o długości zerowej.

Oznaczmy przez $P[k]$ rozmiar prefikso-sufiksu $x[1..k]$. Zatem $per(x)=n-P[n]$, gdzie $n=|x|$.

Przykład

Dla $x\ =\ abababababb$ mamy:
$$P[1..11]\ =\ [0,\ 0,\ 1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8,\ 0].$$

Wartość $P[0]$ jest wartością sztuczną (przyjmiemy, że $P[0]=-1$).

Przedstawimy jeden z możliwych algorytmów liniowych obliczania tablicy $P$. Jest to iteracyjna wersja algorytmu rekurencyjnego, który moglibyśmy otrzymać korzystając z faktu:

Jeśli $x[j] = x[t+1]$ oraz $t = P[j-1]$, to $P[j] = t+1$

W algorytmie obliczania $P[j]$ korzystamy z wartości $P[k]$, dla $k < j$.

Algorytm Prefikso-Sufiksy

P[0] := -1;
t := -1;
for j := 1 to m do begin
    while (t >= 0) and (x[t+1] <> x[j]) do
        t := P[t];
    t := t + 1;
    P[j] := t;
end;

Złożoność liniowa wynika stąd, że w każdej iteracji zwiększamy wartość $t$ co najwyżej o jeden, a wykonanie każdej operacji $t:=P[t]$ zmniejsza wartość $t$ co najmniej o jeden. Proste zastosowanie zasady magazynu (lub potencjału) implikuje, że operacji $t:=P[t]$ wykonujemy co najwyżej $t$. Dowód poprawności pozostawiamy jako ćwiczenie.

Zastosowanie tablicy $P$: liczenie maksymalnego sufiksu

Oznaczmy przez $MaxSuffix(x)$ leksykograficznie maksymalny sufiks $x$. Jeśli $|x|=n$ to niech $MaxSuffix(x)=x[s+1\ldots n]$. Przedstawimy jeden z możliwych algorytmów liniowych obliczania $MaxSuffix(x)$. Algorytm ten pochodzi z pracy Lexicographically least circular substrings autorstwa K. S. Bootha i stanowi wersję algorytmu liczenia tablicy $P$.

Korzystamy z następującego faktu:

Jeśli $MaxSuffix(x)=z$, i $MaxSuffix(xc)=z'c$, to $z'$ jest prefikso-sufiksem $z$.

W algorytmie obliczamy jednocześnie tablicę $P$ dla tekstu $x[s + 1\,\ldots j]$. Utrzymujemy niezmienik: mamy poprawaną tablicę $P$ dla tekstu $x[s + 1\,\ldots j]$ oraz $x[s + 1\,\ldots j] = MaxSuffix(x[1\,\ldots j]).$

Algorytm MaxSuffix

P[0] := -1;
t := -1;
s := 0;
for j := 1 to m do begin
   while (t >= 0) and (x[s + t + 1] < x[j]) do begin
        s := j - 1 - t;
        t := P[t];
   end;
   while (t >= 0) and (x[s + t + 1] <> x[j]) do
        t := P[t];
    t := t + 1;
    P[j - s] := t;
end;

Zastosowanie tablicy $P$: minimalne słowa o zadanej strukturze okresów

Niech $Okresy(w)$ onacza zbiór długości okresów słowa $w$. Rozważamy następujący problem: znaleźć minimalne leksykograficznie słowo $u$ nad binarnym alfabetem spełniające $Okresy(w) = Okresy(u)$.

Opisany algorytm jest wersją algorytmu pochodzącego od Vesa Halava, Tero Harju, Lucian Ilie, który kostruuje
jakikolwiek tekst binarny okresowo równoważny danemu słowu. Nasz algorytm podaje leksykograficznie minimalny
taki tekst, a pomimo tego (a może właśnie dzięki temu) jest prostszy.

Pierwszym krokiem jest policzenie zbioru okresów $Okresy(w)$ tego słowa, po czym właściwie zapominamy o słowie $w$. Zakładamy zatem odtąd, że znamy zbiór okresów słowa wejściowego. Pozostawiamy czytelnikowi jako proste ćwiczenie wyprowadzenie z lematu o okresowości dowodu następującego faktu.

Lemat o tekstach pierwotnych

Jeśli tekst nie jest pierwotny to zmiana pojedynczego symbolu na dowolnej pozycji zamienia ten tekst na pierwotny.

Zamiast przetwarzać okresy wygodniej robić to dla prefikso-sufiksów: słów niepustych będących jednocześnie prefiksem i sufiksem tekstu. Oczywiście cały tekst także jest swoim prefikso-sufiksem.

Oznaczmy rosnący ciąg długości kolejnych prefikso-sufiksów słowa $w$ przez $\pi(w) = (p_1,\, p_2,\ldots,\, p_k)$, w szczególności $p_k = n$. Ciąg $\pi(w)$ łatwo wyliczyć znając zbiór okresów, zachodzi bowiem $Okresy(w) = Okresy(v) \Leftrightarrow \pi(w) = \pi(v)$.

Przykład

$$Okresy(w) = \lbrace10,\, 20,\, 25,\, 27\rbrace \Longrightarrow\ \pi(w) = (2,\, 7,\, 17,\, 27)$$

Oznaczmy minimalne leksykograficznie słowo, którego ciągiem długości prefikso-sufiksów jest $(p_1,\, p_2,\ldots,\, p_i)$ przez:
$$P_i = MinLex(p_1,\ldots,\, p_{i}).$$
Słowo to jest $i$-tym (w kolejności długości) prefikso-sufiksem wyniku.

Nieformalny opis algorytmu

Zasadnicza koncepcja algorytmu jest naturalna i narzucająca się - chcemy ,,wepchnąć'' w tekst jak największą liczbę zer celem uzyskania leksykograficznej minimalności. Algorytm opiera się zatem na zachłannym wpisywaniu $0^+$ albo $0^*1$ w te fragmenty tekstu, które nie są zdeterminowane przez prefikso-sufiksy w następującym sensie: każdy $P_{i+1}$ musi się zaczynać od $P_i$.

Początkowo mamy tekst długości $n$ którego wszystkie pola są ,,puste''. Wypełniamy kolejne puste pola od końca wpisując prefikso-sufiksy, zaczynając od najkrótszego z nich, tzn. $P_1$. Dla $\pi = (p_1,\, p_2,\ldots,\ p_k)$ słowo $P_{i+1}$ konstruujemy dopisując na początku $P_i$ lub jego prefiks, jeśli jest za mało miejsca na całe $P_i$. Niezapełnione pola tekstu zastępujemy leksykograficznie pierwszym ciągiem $\Delta$, który nie wygeneruje nadmiarowego prefikso-sufiksu.

Obserwacja
Najciekawszą własnością algorytmu jest fakt, że wystarczy zawsze sprawdzić tylko dwie alternatywy na brakujący fragment:
$$\Delta \in \lbrace O^j,\, O^{j-1}1 \rbrace \text{ dla } j = p_{i+1} - 2 p_i$$.
Dzięki temu możliwy jest algorytm działający w czasie liniowym. Postawową operacją wykonywaną w algorytmie jest sprawdzenie którą z opcji na $\Delta$ wybrać, aby nie wygenerował się nadmiarowy prefikso-sufiks.

Rysunek

Schemat generowania docelowego słowa

Konstrukcja kolejnego prefikso-sufiksu w sytuacji gdy $2 p_i < p_{i+1}$. Z definicji prefikso-sufiksu, początkową i końcową częścią tekstu jest $P_i$. Wolne pola (fragment aktywny) zapełniamy jak największą liczbą zer; w miejsce symbolu ? wstawiamy 0 albo 1.

Przykład (kontynuacja)

Opiszemy w jaki sposób konstruujemy minimalne leksykograficznie słowo $MinLex(\pi)$ dla naszego przykładowego ciągu prefikso-sufiksów $\pi(w) = (2,\, 7,\, 17,\, 27)$:

Konstruujemy $MinLex(2)\ = $ 01
Wiemy, że $MinLex(2,\, 7) = $ 01???01, próbujemy wstawić minimalny leksykograficznie ciąg 000
zastępując znaki ?. Otrzymujemy $MinLex(2,\, 7) = $ 0100001 - tekst ten jest zgodny z ciągiem prefikso-sufiksów $(2,\, 7)$.
$MinLex(2,\, 7,\, 17) = MinLex(2,\, 7)$???$MinLex(2,\, 7)$. Jeśli zastąpimy znaki ? przez 000 to otrzymamy tekst 01000 01000 01000 01, który ma nadmiarowy prefikso-sufiks długości 12. Zatem próbujemy zastąpić ??? przez następny w kolejności leksykograficznej ciąg 001. Tym razem otrzymany tekst jest zgodny z ciągiem prefikso-sufiksów $(2,\, 7,\, 17$. Zatem $MinLex(2,\, 7,\, 17) = $ 01000010010100001.
Ponieważ $27 - 17 <17$ wiemy, że wynikiem jest tekst którego prefiksem i sufiksem jest $MinLex(p_1,\ldots,\, p_{i+1})$, zatem końcowym wynikiem jest:
$$MinLex(2,\, 7,\, 17,\, 27) = \mathtt{0100001001}\; MinLex(2,\, 7,\, 17) = \mathtt{0100001001}\; \mathtt{01000010010100001}.$$

Algorytm $\mathbf{MinLex}(p_1,\, p_2, \ldots,\, p_k)$

if ($p_1 = 1$) then
- $P_1 := 0$
else
- $P_1 := 0^{p_1-1}1$;
for $i = 1$ to $k-1$ do
- $j := p_{i+1} - 2 p_i$;
- if ($j \leq 0$) then
  - $P_{i+1} := \alpha P_i$, gdzie $\alpha$ jest prefiksem $P_i$ długości $p_{i+1}-p_i$
  else if ($Pierwotny(P_i 0^j)$) then
  - $P_{i+1} := P_i 0^j P_i$
return $P_k$;

Poprawność algorytmu

Zauważmy, że jeśli mamy sytuację gdy $j > 0$ to wtedy $P_i$ zawiera co najmniej jedną jedynkę. Poprawność algorytmu wynika z następujących dwóch faktów.

Fakt 1.
Niech $j > 0$ oraz $P$ będzie dowolnym binarnym tekstem zawierającym co najmniej jedną jedynkę. Wtedy $u = P\, 0^j P$ ma (nadmiarowy) prefikso-sufiks o długości $|P\,| < p < |u|$ wtedy i tylko wtedy gdy $P\, 0^j$ nie jest pierwotny.

Uzasadnienie
Przypuśćmy, że istnieje nadmiarowy prefikso-sufiks $P\,'$. Ten prefikso-sufiks nie może się zacząć wewnątrz aktywnego fragmentu $O^j$, bo $P$ zawiera jedynkę. Z drugiej strony jeśli $P\,'$ zaczyna się w prefiksie $P$ słowa $u$, to na mocy lematu o okresowości słowo $u$ ma (mały) okres, który jest krótszy od $P\, 0^j$ i jest dzielnikiem długości tego słowa. Wynika to stąd, że tekst $u$ miałby okresy o długościach $| P\, 0^j|$ oraz $|P\,'| \leq |P\,|$. Długość tekstu $u$ jest nie mniejsza od sumy tych okresów i można wtedy zastosować lemat o okresowości.

Zatem jeśli $P\, 0^j P$ ma nadmiarowy prefikso-sufiks, to $P\, 0^j$ nie jest pierwotne. Łatwo można zauważyć implikację odwrotną, wtedy $u$ ma nadmiarowy prefikso-sufiks o długości $u - p$, gdzie $p$ jest (małym) okresem $P\, 0^j$. Kończy to uzasadnienie faktu.

Fakt 2.
Jeśli $P\, 0^j$ nie jest pierwotny, to $P\, 0^{j-1}1$ jest pierwotny. Uzasadnienie wynika z lematu o tekstach pierwotnych.

Złożoność algorytmu

Podstawowym problemem jest sprawdzenie czy tekst $P_i 0^j$ jest pierwotny. W miarę konstruowania coraz większych prefikso-sufiksów, a więc jednocześnie prefiksów całego tekstu wynikowego, budujemy on-line tablicę wszystkich prefikso-sufiksów z algorytmu Knutha-Morrisa-Pratta. Dzięki tej tablicy znamy najkrótszy okres i możemy sprawdzić czy dany prefiks jest pierwotny. Zatem algorytm działa w czasie liniowym.

Informatyka MIMUW