Zaawansowane algorytmy i struktury danych/Wykład 3

Zaawansowane algorytmy tekstowe III

W module tym zajmiemy się wykrywaniem regularności w tekstach: szukaniem symetrii i powtórzeń. 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.

Słowo jest symetryczne, gdy $x=x^R$, gdzie $R^{}$ jest operacją odwracania słowa. Algorytmicznie symetrie w słowach są bardzo interesujące.

Kompresja typu LZ i faktoryzacja tekstów

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_1{v}_2..v_{k-1}|=i-1$, to $v_k$ jest najdłuższym tekstem, który występuje w $v_1{v}_2..v_{k-1}$, a jeśli takiego nie ma, to $v_k=x[i]$.

Oznaczmy przez $LZ(x)$ faktoryzację $x$.

Rysunek 1:

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=abaababaabaab$

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, gdy zaczyna się w $u$ i kończy w $v$. Wprowadzimy dwie funkcje logiczne $RighTest(u,v),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$.

Rozważmy przypadek obliczania $RightTest$.

Rysunek 2: $PREF[k]+S[k]\ge k$

Dla każdej pozycji $k$ w $v$ liczymy

1. $PREF[k]$: długość maksymalnego podsłowa zaczynającego się w $k$ i będącego prefiksem $v$;
2. $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$:
$Rightest(u,v)$ zachodzi wtedy i tylko wtedy, gdy dla pewnego $k$ mamy nierówność $PREF[k]+S[k]\ge 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)\text{<mrow data-mjx-texclass="ORD">lub</mrow>}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 - Rekurencyjne

---

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,\dots ,v_m)$

$x$ zawiera powtórzenie wtedy i tylko wtedy, gdy dla pewnego $k$ zachodzi

$RightTest(v_1,v_2\dots v_{k-2},v_{k-1}{v}_k$ lub $Righttest(v_1,v_2\dots 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,\dots ,z_m)$;
for $k:=1$ to $m$ do
   $u1:=z_1,z_2\dots z_{k-2};v1:=z_{k-1}{z}_k$;
   $u2:=z_1,z_2\dots z_{k-1};v2:=z_k$;
   if $RightTest(u1,v1)$ lub $RightTest(u2,v2)$
      then return true;
return false;

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

Wykrywanie symetrii w tekstach

Słowo $x$ nazwiemy palindromem, gdy jest symetryczne oraz $|x|>1$. Palindromy parzyste to palindromy o parzystej długości. Oznaczmy zbiór wszystkich palindromów przez $PAL$, a przez $PA{L}_0,PA{L}_1$ oznaczmy odpowiednio zbiory palindromów parzystych i nieparzystych.

Przykładami palindromów są słowa:

kajak, atypotopyta, zagwiżdżiwgaz

Problem najdłuższego prefikso-palindromu polega na rozkładzie danego słowa $x=uv$ takim, że $u\in PAL$ oraz $u$ jest najdłuższy o tej własności. Istnieje prosty algorytm oparty na tablicy prefikso-sufiksów $P$.

Algorytm Prefikso-Palindrom

---

1. oblicz tablicę P dla słowa-kompozycji $x\mathrm{\#}{x}^R$ (słowo długości $2n+1$),
2. jeśli $P(2n+1)>0$ to jest to długość najdłuższego prefikso-palindromu
3. w przeciwnym przypadku $x$ nie ma prefikso-palindromu.

Podobnie możemy zdefiniować problem najkrótszego prefisko-palindromu. Algorytm powyższy można łatwo zmodyfikować, aby znajdował najkrótszy prefikso-palindrom.

Chociaż powyższy algorytm działa w czasie liniowym, możliwy jest szybszy algorytm, który znajduje najkrótszy prefikso-palindrom w czasie $O(s)$, gdzie $s$ jest długością najkrótszego prefikso-palindromu, założywszy że tekst posiada prefikso-palindrom.

Skoncentrujemy się na razie na palindromach parzystych. Definiujemy dla każdej pozycji $i$ promień palindromu parzystego o środku w $i$ jako:

$Rad[i]=\max \{j:j=0\text{<mrow data-mjx-texclass="ORD">lub</mrow>}x[i-j+1..i]=x[i+1..i+j]\}$

Załóżmy, dla uproszczenia, że tekst $x$ zaczyna się od specjalnego symbolu (marker początku), który występuje tylko na początku.

Opiszemy algorytm, który oblicza tablice promieni palindromów dla kolejnych pozycji $i$ od strony lewej do prawej. Załóżmy, że policzyliśmy już wartości:

$Rad[1],Rad[2],\dots ,Rad[i].$

Okazuje się, że korzystając z symetrii możemy obliczyć pewne nowe elementy tablicy $Rad$, nie wykonując żadnych porównań symboli. Wynika to z następującego faktu.

Własność promieni palindromów

$1\le k\le Rad[i]\text{<mrow data-mjx-texclass="ORD">oraz</mrow>}Rad[i-k]\ne Rad[i]-k\Rightarrow Rad[i+k]=\min (Rad[i-k],Rad[i]-k)$

Uzasadnimy krótko tę własność rozważając dwa przypadki:

Przypadek (a): $Rad[i-k]<Rad[i]-k$.

Wówczas palindrom $Rad[i-k]$ o środku w $i-k$ jest całowicie zawarty w dłuższym palindromie o środku w $i$. Pozycja $i-k$ jest symetryczna do $i+k$ ze względu na $i$. Zatem z symetrii o środku $i$ wynika, że najdłuższy palindrom o środku $i+k$ ma taki sam promień jak ten o środku $i-k$. Zatem w tym przypadku $Rad[i+k]=Rad[i-k]$.

Przypadek (b): $Rad[i-k]>Rad[i]-k$.

Sytuacja jest pokazna na rysunku, który przedstawia maksymalne palindromy o środkach $i-k$, $i$ i $i+k$. Ponieważ $a\ne b$ (z definicji maksymalności palindromu o środku w $i$), zatem $Rad[i+k]=Rad[i]-k$.

Rysunek 3: Przypadek (b) dowodu własności promieni palindromów parzystych.

Poniżej przedstawiamy algorytm Promienie-Palindromów. W jednej głównej iteracji pętli while algorytm oblicza $Rad[i+k]$ dla kolejnych $k=1,2,\dots$, dla których $Rad[i-k]\ne Rad[i]-k$. Jeśli ostatnim takim $k$ jest $k^{\prime }$, wtedy zaczynamy całą główną iterację od nowego $i$ równego $i+k^{\prime }$.

Pozostawiamy jako ćwiczenie modyfikację algorytmu, aby liczył promienie palindromów nieparzystych.

W pierwszym momencie, gdy algorytm wykryje prefikso-palindrom (promień palindromu sięga do początku tekstu), możemy algorytm zatrzymać i podać długość najkrótszego prefikso-palindromu. W sumie pokazaliśmy następujący fakt:

(a) Tablicę promieni palindromów (parzystych i nieparzystych) można policzyć w czasie liniowym.

(b) Długość $s$ najkrótszego prefikso-palindromu (zakładając że taki istnieje) można policzyć w czasie proporcjonalnym do jego długości.

Algorytm Promienie-Palindromów

---

$Rad[1]:=0$; $j:=0$;
$i:=2$;

while $i\le \lfloor n/2\rfloor$ do
   while $x[i-j]=x[i+1+j]$ do $j:=j+1$;
   if $j=i$ then $Rad[i]:=j$;
   $k:=1$;
   while $Rad[i-k]\ne Rad[i]-k$do
      $Rad[i+k]:=\min (Rad[i-k],Rad[i]-k)$; $k:=k+1$;
   $j:=max(j-k,0)$;$i:=i+k$;

Kompozycje słów symetrycznych

Rozważmy teraz interesujący (chociaż mało użyteczny w praktyce) problem sprawdzania, czy słowo jest nietrywialną kompozycją słów symetrycznych. Przez $PA{L}_0^{*},PA{L}^{*}$ oznaczmy odpowiednio zbiór konkatenacji dowolnej liczby słów należących do $PA{L}_0,PAL$.

Elementy $PA{L}^{*}$ nazywamy palstarami a elementy $PA{L}_0^{*}$ nazywamy palstarami parzystymi.

Niech $first(i)$, $firs{t}_0(i)$ będzie (ze względów technicznych załóżmy, że słowo puste też jest palstarem (parzystm i nieparzystym jednocześnie)) odpowiednio pierwszą pozycją $j>i$ w słowie $x$ taką, że $x[i..j]\in PAL$, $x[i..j]\in PA{L}_0$, wartością funkcji zaś jest zero, gdy nie ma takiego $j$.

Algorytm Parzyste-Palstary

---

$s:=0$;
while $s<n$ do    $s:=s+1$;
   if $firs{t}_0(s)=0$ then return false;
   $s:=first(s)$;
return true;

Mówiąc nieformalnie, algorytm Parzyste-Palstary obcina słowo o najkrótszy prefikso-palindrom, aż tekst będzie pusty (sukces) albo aż się em zatnie (nie ma rozkładu na parzyste palindromy). Algorytm Parzyste-Palstary ma złożoność liniową, ponieważ policzenie $firs{t}_0(i)$ zajmuje czas proporcjonalny do wartości $s=first(i)$, zakładając, że $s\ne 0$. Nietrywialna natomiast jest poprawność algorytmu. Zdefiniujmy

$pars{e}_0(i)=\min \{j:x[i..j]\in PA{L}_0$ oraz $j=n$ lub $x[j+1..n]\in PA{L}_0^{*}\}$

Własność parzystych palstarów: $x[i..n]\in PA{L}_0^{*}\Rightarrow pars{e}_0(i)=firs{t}_0(i)$

Poprawność algorytmu wynika natychmiast z powyższej własności. Pozostawiamy dowód tej własności jako ćwiczenie.

Możemy podobnie zdefiniować funkcję $parse(i)$ dla dowolnych palstarów i dowolnych palindromów. Własność parzystych palstarów nie zachodzi dla dowolnych palstarów, ale zachodzi własność bardziej skomplikowana.

Własność dowolnych palstarów:

$x[i..n]\in PA{L}^{*}\Rightarrow parse(i)\in \{first(i),2\cdot first(i)+1,2\cdot first(i)-1\}$

Pozostawimay dowód tej własności jako ćwiczenie. Algorytm testowania dowolnych palstarów jest interesujący, ponieważ przebiega on zupełnie inaczej niż dla parzystych palstarów.

Pierwszym krokiem algorytmu jest stablicowanie funkcji $first$. Obliczamy tablicę $FIRST[i]=first(i)$ w czasie liniowym dla wszystkich $i$ łącznie.

Pozostawiamy jako ćwiczenie policzenie tej tablicy w czasie $O(n)$. Obliczenie takie opiera się na wykorzystaniu tablicy promieni palindromów.

Załóżmy teraz, że mamy tablicę FIRST. Funkcja $first$ działa teraz w czasie stałym (gotowe wartości z tablicy). Poniższy algorytm dla każdej pozycji $i$ sprawdza, czy $x[i..n]\in PA{L}^{*}$. Odpowiedź jest zapisana w tablicy logicznej $PAL$. Zakładamy, że początkowo tablica $PAL$ ma wartości {\em false}, włącznie z elementami wykraczającymi poza zakres tablicy (dla uproszczenia zapisu).

Algorytm Testowanie-Palstarów

---

$PAL[n]:=$ true;
for $i:=n-1$ down to $0$ do    $f:=FIRST[i]$;
   if $f=0$ then $PAL[i]:=$ false
   else $PAL[i]:=(PAL[i+f]$ or $PAL[i+2f-1]$ or $PAL[i+2f+1])$

Interesującym problemem jest rozkład słowa $x$ w postaci $PA{L}^k$, gdzie $k$ jest ustalone. Istnieją algorytmy liniowe dla $k=2,3,4$ oparte na następującej własności zawężającej zbiór rozkładów do zweryfikowania:

jeśli $x\in PA{L}^2$ to $x=uv$, dla pewnych $u,v\in PAL$ gdzie $u$ jest najdłuższym palindromem będącym prefiksem $x$ lub $v$ jest najdłuższym palindromem będącym sufiksem $x$.