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ęć:

  1. abaaaba
  2. aabaaab
  3. baabaaa
  4. abaabaa
  5. aabaaba
  6. aaabaab
  7. baaabaa
  8. 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
  1. P[0] := -1;
  2. t := -1;
  3. for j := 1 to m do begin
  4. while (t >= 0) and (x[t+1] <> x[j]) do
  5. t := P[t];
  6. t := t + 1;
  7. P[j] := t;
  8. 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
  1. P[0] := -1;
  2. t := -1;
  3. s := 0;
  4. for j := 1 to m do begin
  5. while (t >= 0) and (x[s + t + 1] < x[j]) do begin
  6. s := j - 1 - t;
  7. t := P[t];
  8. end;
  9. while (t >= 0) and (x[s + t + 1] <> x[j]) do
  10. t := P[t];
  11. t := t + 1;
  12. P[j - s] := t;
  13. 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łowaSchemat 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)\):

  1. Konstruujemy \(MinLex(2)\ = \) 01
  2. 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)\).
  3. \(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.
  4. 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\)
    • else

      • \(P_{i+1} := P_i 0^{j-1}1 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.