Rozdział 7: Powtórzenia i kompresja typu LZ

Słowo jest powtórzeniem, gdy jest postaci \(zz\), gdzie \(z\) jest niepustym tekstem. Powtórzenia w tekstach reprezentują strukturę wewnętrznych okresowości i regularności, których wyszukiwanie ma zastosowania np. w biologii obliczeniowej. Powtórzenia są związane z kompresją tekstów. Im więcej powtórzeń w słowie, tym bardziej jest kompresowalne.

Powtarzające się segmenty tekstu związane są z kompresją. Jeśli mamy dwie kopie tego samego (być może długiego) podsłowa, to drugą z nich możemy zastąpić referencją do pierwszej. Jeśli czytamy tekst od lewej do prawej i napotkamy segment \(x[i..j]\), który pojawił się wcześniej jako \(x[p..q]\), gdzie \(q < i\), to możemy reprezentować \(x[i..j]\) przez parę liczb \([p,\, q]\). Filozofia ta prowadzi do rodziny algorytmów kompresji podanych przez Lempela i Ziva (kompresji typu LZ). Jest wiele różnych wariantów tego typu kompresji.

Zdefiniujmy teraz faktoryzację tekstów typu LZ. Faktoryzacją tekstu \(x\) jest rozkład \(x = v_{1}v_{2}\dots v_{m}\), gdzie \(v_1=x[1]\), oraz jeśli \(|v_1v_2 \dots v_{k-1}| = i-1\), to \(v_k\) jest najdłuższym tekstem, który występuje w \(v_1v_2 \dots v_{k-1}\), a jeśli takiego nie ma, to \(v_k=x[i]\).

Oznaczmy przez \(LZ(x)\) faktoryzację \(x\). Faktoryzacja taka nazywana jest czasem faktoryzacją Crochemora, który z niej korzystał przy szukaniu powtórzeń. Różni się ona jedynie kosmetycznie od faktoryzacji związanej bezpośrednio z algorytmem Lempel-Ziv. Dlatego też będziemy nazywać ją faktoryzacją LZ.

Rysunek: faktoryzacja LZ

Faktoryzacja typu LZFaktoryzacja typu LZ
Obliczanie następnego czynnika w faktoryzacji typu LZ zaczynającego się na pozycji \(i\)-tej (jako najdłuższego słowa, które występuje we wcześniejszym tekście). Poprzedni czynnik kończy się na pozycji \(i-1\). \(Pos(i)\) jest początkiem wcześniejszego segmentu, który jest referencją aktualnego czynnika.


Przykład

Faktoryzacja przykładowego słowa Fibonacciego jest następująca:

LZ(abaababaabaab) \(= v_1 \ v_2 \ v_3 \ v_4 \ v_5 \ v_6 = a \ b \ a \ aba \ baaba \ ab\)

Korzystając z drzew sufiksowych można udowodnić następujący fakt:

Dla danego tekstu \(x\) długości \(n\) możemy policzyć \(LZ(x)\) w czasie liniowym. Zakładamy tutaj, że alfabet da się posortować w czasie liniowym (jest to naturalne założenie).

Powtórzenia zakotwiczone

Przypuśćmy, że \(x=uv\). Powtórzenie jest \((u,\, v)\)-zakotwiczone (na pozycji pomiędzy \(u\) i \(v\)), gdy zaczyna się w \(u\) i kończy w \(v\). Wprowadzimy dwie funkcje logiczne \(RightTest(u,\, v)\), i \(LeftTest(u,\, v)\) dla słów \(u,\, v\). \(RightTest(u,\, v)\) zachodzi, gdy istnieje \((u,\, v)\)-zakotwiczone powtórzenie, którego środek znajduje się na początku lub wewnątrz \(v\). Podobnie definiujemy \(LeftTest\) dla słowa \(u\).

Rozważmy przypadek obliczania \(RightTest\).

Rysunek: RightTest

RightTestRightTest

\(PREF[k]+S[k]\geq k\)

Dla każdej pozycji \(k\) w \(v\) liczymy

  • \(PREF[k]\): długość maksymalnego podsłowa zaczynającego się w \(k\) i będącego prefiksem \(v\);
  • \(S[k]\): długość maksymalnego podsłowa kończącego się na pozycji \(k-1\) i będącego sufiksem \(u\).

Własność funkcji \(RightTest\): \(RightTest(u,v)\) zachodzi wtedy i tylko wtedy, gdy dla pewnego \(k\) mamy nierówność \(PREF[k]+S[k] \geq k\), patrz rysunek.

Wiemy już jak obliczyć tablicę \(PREF\) w czasie liniowym, tablicę \(S\) liczymy symetrycznie. W ten sposób pokazaliśmy, że obliczenie \(RightTest(u,\, v)\) wymaga jedynie czasu liniowego. Podobnie jest dla \(LeftTest\).

Szukanie dowolnych powtórzeń w czasie \(n \log n\)

Niech \(Test(u,\, v)\) będzie funkcją logiczną wyrażającą fakt posiadania przez \(x\) powtórzenia \((u,\, v)\)-zakotwiczonego. Inaczej mówiąc, \(Test(u,\, v) \equiv RightTest(u,\, v)\ \textrm{lub}\ LeftTest(u,\, v)\). Następujący algorytm ma strukturę taką, jak merge-sort. Szukamy powtórzenia w lewej połowie, w prawej oraz na styku obu połówek (funkcja \(Test\)).

Algorytm Powtórzenia rekurencyjnie

if n = 1 then
   return false;
zastosuj algorytm rekurencyjnie do tekstu \(x[1.. \lfloor n/2\rfloor ]\);
zastosuj algorytm rekurencyjnie do tekstu \(x[\lfloor n/2\rfloor +1.. n]\);
if \(Test(x[1..\lfloor n/2\rfloor],\ x[\lfloor n/2\rfloor +1.. n])\) then
   return true;

Algorytm w oczywisty sposób działa w czasie \(O(n \log n)\), gdyż liczenie funkcji \(Test\) jest w czasie liniowym.

Dygresja: Istnieje ciekawa wersja tego algorytmu, działająca w czasie \(O(n \log n)\) i (dodatkowej) pamięci stałej (nie możemy mieć dodatkowych tablic \(PREF,\ S\)).

Szukanie dowolnych powtórzeń w czasie liniowym

Algorytm liniowy szukania powtórzenia opiera się na faktoryzacji tekstów. Niech
$$LZ(x) = (v_{1},\, v_{2},\, \ldots,\, v_{m})$$

\(x\) zawiera powtórzenie wtedy i tylko wtedy, gdy dla pewnego \(k\) zachodzi
$$RightTest(v_1\, v_2\, \ldots\, v_{k-2},\, v_{k-1}\, v_k) \ \mathrm{lub}\ RightTest(v_1\, v_2\, \ldots\, v_{k-1},\, v_k)$$

Dowód tej własności pozostawiamy jako ćwiczenie.

Algorytm Szukanie Powtórzeń

oblicz faktoryzację \(LZ(x) = (z_{1},\, z_{2},\, \ldots,\, z_{m})\);
for k := 1 to m do begin
   \(u1 := z_1\, z_2\ldots z_{k-2}; v1 := z_{k-1}\, z_k\);
   \(u2 := z_1\, z_2\ldots z_{k-1}; v2 := z_k\);
   if \(RightTest(u1,\, v1)\) or \(RightTest(u2,\, v2)\) then
       return true;
end;
return false;

Algorytm działa w czasie liniowym, pozostawiamy to jako ćwiczenie.