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 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

RightTest

$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.

Informatyka MIMUW