Zaawansowane algorytmy i struktury danych/Wykład 3

From Studia Informatyczne

Zaawansowane algorytmy tekstowe III


Spis treści


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 PAL_0,\ PAL_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\#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 \ \textrm{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\leq k\leq Rad[i]\ \textrm{oraz}\ Rad[i-k]\neq 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.

Grafika:ZASD_3_3.jpg
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]\neq Rad[i]-k. Jeśli ostatnim takim k jest k', wtedy zaczynamy całą główną iterację od nowego i równego i+k'.

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\leq \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]\neq 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 PAL_0^*, PAL^* oznaczmy odpowiednio zbiór konkatenacji dowolnej liczby słów należących do PAL_0,\ PAL.

Elementy PAL^* nazywamy palstarami a elementy PAL_0^* nazywamy palstarami parzystymi.

Niech first(i), first_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 PAL_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 first_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 first_0(i) zajmuje czas proporcjonalny do wartości s=first(i), zakładając, że s \ne 0. Nietrywialna natomiast jest poprawność algorytmu. Zdefiniujmy

parse_0(i)=\min \{j\ :\ x[i.. j]\in PAL_0 oraz j=n lub x[j+1.. n]\in PAL_0^{*}\}


Własność parzystych palstarów: x[i..n] \in PAL_0^* \ \Rightarrow\ parse_0(i)=first_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 PAL^* \ \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 PAL^*. 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 PAL^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 PAL^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.