Zaawansowane algorytmy i struktury danych/Wykład 3

Zaawansowane algorytmy tekstowe III

W module tym zajmiemy się wykrywaniem regularności w tekstach: szukaniem symetrii.

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

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{lub}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{oraz}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$;
   $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ż tylko czysto teoretyczny ) 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ę 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 \mathit{ 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$.