Algorytmy i struktury danych/Algorytmy tekstowe I

Algorytmy tekstowe I

Tekst jest ciągiem symboli, przyjmujemy że jest on zadany tablicą x[1..n] elementami której są symbole ze zbioru A (zwanego alfabetem). Liczba $n=|x|$ jest długością (rozmiarem)tekstu. W większości naszych algorytmów jedyne operacje dopuszczalne na symbolach wejściowych to porównania dwóch symboli.

Algorytmy na tekstach wyróżniają się tym, że wykorzystują specyficzne kombinatorycznewłasności tekstów. Okresem tekstu $x$ jest każda liczba naturalna niezerowa $p$ taka, że$x[i]=x[i+p]$, dla każdego i dla którego obie strony są zdefiniowane. Przez per(x) oznaczmyminimalny okres x. Okresowość spełnia następującą ciekawą własność kombinatoryczną. Niech $nwd(p,q)$ oznaczanajmnieszy wspólny dzielnik p,q.

Lemat [Lemat o okresowości]

Jeśli x ma okresy p, q oraz $p+q\le |x|$ to $nwd(p,q)$ jest również okresem x.

Lemat ten wynika z poprawności algorytm Euklidesa z odejmowaniem, który liczy nwd(p,q). Zauważmy, żejeśli $p>q$ są okresami to p-q też jest okresem. Dokładny dowód zostawiamy jako ćwiczenie.

Lemat ten można wzmocnić osłabiając założenia. Dowód pozostawiamy jako ćwiczenie.

Lemat [Silny lemat o okresowości]

Jeśli x ma okresy p, q oraz $p+q\le |x|+nwd(p,q)$ to $nwd(p,q)$ jest również okresem x.

Pojęciem dualnym do okresu jestprefikso-sufiks tekstu, jest to najdłuższy własciwy (nie będący całym x) prefiks tekstu x będącyjednocześnie sufiksem x. Oczywistym jest, że $|x|-per(x)$ jest długością prefikso-sufiksu x.Jeśli $per(x)=|x|$ to prefikso-sufiksem x jest słowo puste o długości zerowej.

Oznaczmy przez $P[k]$ rozmiar prefikso-sufiksu $x[1..k]$, zatem $per(x)=n-P[n]$, gdzie $n=|x|$.

Przykład

Dla $x=abababababb$ mamy:

$P[1..11]=[0,0,1,2,3,4,5,6,7,8,0].$

Wartość $P[0]$ jest warością sztuczną (przyjmiemy potem $P[0]=-1$).

Liczenie tablicy Prefikso-Sufiksów

Przedstawimy jeden z możliwych algorytmów liniowych oblicznaia tablicy P, jest to iteracyjna wersja algorytmu rekurencyjnego, który moglibyśmy otrzymac korzystając z faktu:

$x[j]=x[t+1]\text{<mrow data-mjx-texclass="ORD">oraz</mrow>}t=P[j-1]\Rightarrow P[j]=t+1$

W algorytmie do liczenia $P[j]$ korzystamy z wartości $P[k]$ dla $k<j$.

Algorytm Prefikso-Sufiksy

---

$P[0]:=-1$; $t:=-1$;
for $j:=1$ to $m$ do
   while $t\ge 0$ and $x[t+1]\ne x[j]$ do $t:=P[t]$
   $t:=t+1$; $P[j]:=t$;

Złożoność liniowa wynika stąd, że w każdej iteracji zwiększamy wartość t co najwyżejo jeden, a wykonanie każdej operacji $t:=P[t]$ zmniejsza wartość t co najmniej o jeden. Proste zastosowanie zasady magazynu (lub potencjału) implikuje, że operacji $t:=P[t]$ wykonujemy conajwyżej n. Dowód poprawności pozostawiamy jako ćwiczenie.

Minimalne słowo pokrywające

Pokażemy pewne proste zastosowanie tablice prefikso-sufisków.

Słowem pokrywającym tekst x taki tekst y, którego wystąpienia w x pokrywają cały tekst x. Na przykład aba pokrywa ababaaba, natomiast nie pokrywa tekstu abaaababa. Obliczyć długość najkrótszego słowa pkrywającego dany tekst x.

Niech $S[i]$ będzie rozmiarem minimalnego pokrywajćego słowa dla prefiksu $x[1..i]$. Następujący algorytm liczy długość minimalnego słowa pokrywającego tekstu x. Liczymy wartości $S[i]$ najmniejszej długości minimalnego słowa pokrywającego $x[1\dots i]$ dla każdego $1\le i\le n$. W $i$-tej iteracji algorytm pamięta jaki jest ``znany zakres każdego minimalnego słowa pokrywającego.

Rysunek 3: $i$-ta iteracja algorytmu, dla $i=15$, oraz słowa $x=abaabababaababa\dots$. Tuż przed rozpoczęciem tej iteracji mamy $P[i]=8$, $q=S[8]=3$, $Zakres[3]=13$. Po zakończeniu $i$-tej iteracji

mamy $S[15]=3,Zakres[3]=15$, ponieważ $i-Zakres[3]\le q$.

Algorytm Rozmiar-Minimalnego-Pokrycia

---

for $i:=2$ to $n$ do
   $Zakres[i]=i,S[i]=i$

for $i:=2$ to $n$ do
   if $P[i]>0$ oraz $i-Zakres[S[P[i]]\le S[P[i]]$ then
      $S[i]:=S[P[i]]$; $Zakres[S[P[i]]:=i$;

return $S[n]$;

Tablica Silnych Prefikso-Sufiksów

Wprowadzimy silną tablicę prefikso-sufisów dla wzorca $x[1..m]$:    jeśli $j<|x|$ to $P^{\prime }[j]=k$, gdzie $k$ jest maksymalnym rozmiarm słowa będącego prefiksem i sufiksem $x[1..j]$najdłuższego własciwegoi spełniającego dodatkowy warunek $x[k+1]\ne x[j+1]$ dla $j<n$.
Jeśli takiego k nie ma toprzyjmujemy $P^{\prime }[j]=-1$. Przyjmujemy ponadto, że $P^{\prime }[m]=P[m]$.

Wartości tablicy P' mogą być znacznie mniejsze niż wartości tablicy P.

Przykład

Dla $x=abaab$ mamy:

$P[0..5]=[-1,0,0,1,1,2];P^{\prime }[0..5]=[-1,0,-1,1,0,2].$

Algorytm bazuje na następującej relacji między P i P':

$(t=P[j]\text{<mrow data-mjx-texclass="ORD">oraz</mrow>}x[t+1]\ne x[j+1])\Rightarrow P^{\prime }[j]=t$

$(t=P[j],t\ge 0,\text{<mrow data-mjx-texclass="ORD">oraz</mrow>}x[t+1]=x[j+1])\Rightarrow P^{\prime }[j]=P^{\prime }[t]$

Nie musimy liczyć tablicy P, potrzebna jest jedynie ostatnia wartość $t=P[j]$, którą liczymy on-line.

Algorytm Silne-Prefikso-Sufiksy

---

$P^{\prime }[0]:=-1$; $t:=-$1;
for $j:=$ 1 to $m$ do // $t=P[j-1]$
   while $t\ge 0$ and $x[t+1]\ne x[j]$do
      $t:=P^{\prime }[t]$;
   $t:=t+1$;
   if $j=m$ or $x[t+1]\ne x[j+1]$
      then $P^{\prime }[j]:=t$ else $P^{\prime }[j]:=P^{\prime }[t]$;

Gdyweżmiemy $x=ab{a}^{m-2}$ to $P^{\prime }[0]=-1$, $P^{\prime }[1]=0$, $P^{\prime }[2]=-1$,oraz $P^{\prime }[j]=1$, dla $3\le j\le m$. To jest pesymistyczny przypadek dla algorytmu Silne-Prefikso-Sufiksy, algorytm wykonuje$3m-5$ porównań symboli.

String-matching: algorytm Knutha-Morrisa-Pratta

Przedstawimy klasyczny algorytm Knutha-Morrisa-Pratta (w skrócie KMP) dla problemu string-matchingu:  obliczyć w w tekście $y$ wszystkie (lub pierwsze) wystąpienia danego tekstu $x$, zwanego wzorcem (ang. pattern).

Oznaczmy $m=|x|,n=|y|$, gdzie $m\le n$.

Operacją dominującą w algorytmie jest porównanie dwóch symboli.

Zaczniemy od obliczania jedynie pierwszego wystąpienia. Algorytm KMP przegląda tekst y od lewej do prawej, sprawdzając, czy jest zgodność na pozycji $j+1$ we wzorcu x, oraz na pozycji $i+j+1$ w tekście y. Jeśli jest niezgodność to przesuwamy potencjalny początek (pozycja i) wystąpienia x w y.Zakładamy, że algorytm zwraca wartość false gdy nie zwróci wcześniej true. Pozostawiamy dowód poprawności(określenie niezmienników) jako ćwiczenie.

Algorytm Algorithm KMP

---

$i:=0$; $j:=0$;
while $i\le n-m$ do
   while $j<m$ and $x[j+1]=y[i+j+1]$ do $j=j+1$;
   if $j=m$ then return(true);
   $i:=i+j-P^{\prime }[j]$; $j:=\max (0,P^{\prime }[j])$

Operacją dominującą w algorytmie jest operacja: $x[j+1]=y[i+j+1]$.

Udowodnimy, że algorytm KMP wykonuje co najwyżej 2n-m porównań symboli. Zauważmy, że dla danejpozycji w tekście y jest ona co najwyżej raz porównana z pewną pozycją we wzorcu w porównaniupozytywnym (gdy symbole są równe). Jednocześnie każde negatywne porównanie powoduje przesunięciepozycji $i$ co najmniej o jdeden, maksymalna wartość i wynosi n-m, zatem mamy takich porównań conajwyżej n-m, w sumie co najwyżej 2n-m porównań w algorytmi KMP.

<flash>file=KMP.swf|width=450|height=220</flash>

Algorytm dla $x=ab$, $y=aa..a$ wykonuje 2n-2porównania, zatem 2n-m jest dolną i jednocześnie górną granicą na liczbę porównań w algorytmie.

Obserwacja. Tablicę P' możemy w algorytmie KMP zamienić na P bez zmiany złożoności pesymistycznej.

W wersji on-line algorytmu okaże się, że jest zdecydowana różnica między użyciem P' i P,to właśnie jest motywem wprowadzenia silnych prefikso-sufiksów.

Rysunek 1: Jedna iteracja algorytmu KMP. Przesunięcie $shift=j-P^{\prime }[j]$ potencjalnego początku wystąpienia wzorca gdy $x[j+1]\ne y[i+j+1]$.

Wersja on-line algorytmu KMP

Przedstawimy teraz wersję on-line algorytmu KMP. Wczytujemy kolejne symbole $y$ i wypisujemy on-line (nabieżąco) odpowiedż:

• 0 - gdy dotychczas wczytany tekst nie zawiera x jako sufiks,
• 1 - jeśli zawiera

Algorytm On-Line-KMP

---

repeat forever
   read($symbol$);
   while $j>-1$ and $x[j+1]\ne symbol$ do $j:=P^{\prime }[j]$;
   $j:=j+1$;
   if $j=m$ then
      write(1); $j:=P^{\prime }[m]$;
   else write(0);

Oznaczmy przez delay(m) maksymalną liczbę kroków algorytmu On-Line-KMP między wczytaniem symbolui daniem odpowiedzi. Przez delay'(m) oznaczmy podobną wielkość, w sytuacji gdy zamiast tablicy P' użyjemy P.

Przykład

Jeśli $x=aaaa\dots a$ oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle y=a^{m-1b} , to $delay(m)=O(1)$, $dela{y}^{\prime }(m)=\mathrm{\Theta }(m)$.

Z lematu o okresowości wynika, że zachodzi następujący fakt:

$delay(m)=\mathrm{\Theta }(\log m)$

Uzasadnienie pozostawiamy jako ćwiczenie.

Wersja real-time algorytmu KMP

Pokażemy teraz wersje algorytmu on-line która działa real-time, tzn. czas reakcji między wczytaniem symbolui daniem odpowiedzi jest O(1) niezalżnie od rozmiaru alfabetu.

Algorytm zachowuje się podobnie jak algorytm On-Line-KMP, podstawowa różnica polega na tym, że algorytm wkłada do kolejki wczytane symbole, które jeszcze nie są przetworzone w sensie algorytmu KMP. Algorytm zachowuje siępodobnie jak algorytm on-line, ale wczytuje kolejne symbole z kolejki, a nie bezpośrednio z wejścia. Rysunekpokazuje relacje tego algorytmu do algorytmu KMP. Symbole z wejścia najpierw wędrują do kolejki.

Rysunek 2: Typowa konfiguracja w algorytmie real-time-KMP.

Algorytm Real-Time-KMP

---

inicjalizacja: $j:=0$; Kolejka $:=\mathrm{\varnothing }$;
repeat forever
   read(symbol);
   insert(symbol,Kolejka);
   write(OUTPUT(Kolejka, j));

W celu skrócenia zapisów pojedyńczych algorytmów rozbijamy algorytm na dwie części. Zasadniczaczęść jest zapisana jako osobna funkcja OUTPUT(Kolejka,\ j). Funkcja taliczy 0 lub 1, w zależności od tego czy ostatnio wczytany symbol kończy wystąpieniewzorca x. Zmienne Kolejka, j są globalne.

Oczywistym jest że opóżnienie (czas reakcji) tego algorytmu jest O(1).

Pozostawiamy jako ćwiczenie uzasadnienie tego, że algorytm Real-Time-KMP jest poprawny.

Algorytm Real-Time-KMP: funkcja OUTPUT(Kolejka, j)

---

output $:=$ 0;
repeat 2 times
   if Kolejka niepusta then
      if $j=-1$ then
         j $:=$ 0; delete(Kolejka);
      else if $x[j+1]\ne first(Kolejka)$ then $j:=P^{\prime }[j]$;
      else
         $j:=j+1$; delete(Kolejka);
         if $j=m$
            output $:=$1; j $:=P^{\prime }[m]$;
return(output);

Wersja algorytmu KMP z 3/2.n porównaniami

Algorytm KMP wykonuje co najmniej 2n-m porównań symboli. Załóżmy, że są to operacje dominujące ispróbujmy zmniejszyć stały wspó:lczynnik 2 do $\frac{3}{2}$. Na początku załóżmy, że $x=ab$.Następujący algorytm znajduje wszystkie wystąpienia wzorca ab w tekście y.

Algorytm Szukanie-ab

---

wzorcem jest $ab$
$i:=0$;
while $i\le n-m$ do
   while $y[i+2]\ne b$ do$i=i+1$;
   if $y[i+1]=a$ then
      wypisz-wystąpienie;i$:=$i+2

Algorytm KMP dla wzorca ab wykonywał 2n-2 porównań symboli, nowy algorytm jest lepszy. Zachodzi fakt:    algorytm Szukanie-ab wykonuje co najwyżej n porównań w tym przypadku.

Uzasadnienie pozostawimay jako ćwiczenie.

Uogólnimy algorytm na dowolne wzorce. Niech x zawiera co najmniej dwa różne symbole, $x=a^{k}b\alpha$, gdzie $a\ne b$.Oznaczmy $x^{\prime }=b\alpha$ skrócony wzorzec

Przykład

$x=aaaabaaaababa$, wtedy $x^{\prime }=baaaababa$, $\alpha =aaaababa$.

Podamy nieformalny zarys działania oszczędniejszej wersji algorytmu KMP, w której osobno szukamy x' i osobno części $a^k$.

Niech $KM{P}^{\prime }$ będzie taką wersją algorytmu KMP w której jedynie szukamy wzorca $x^{\prime }$, ale tablica $P^{\prime }$ jest policzona względem wzorca $x$.Jeśli $j>0$ i $shift\le k$ to wykonujemy przesunięcie potencjalnego początku i wzorca w y o k+1, gdzie $shift=j-P^{\prime }[j]$. Inaczej mówiąc, nie szukamy wszystkich wystąpień x', ale jedynie takich, które mają sens pod względem potencjalnego znalezienia na lewo ciągu $a^k$.

Tak zmodyfikowany algorytm KMP zastosujemy jako część algorytmu Oszczędny-KMP. Graficzna ilustracja działania algorytmu Oszczędny-KMP jest pokazana na rysunku.

Algorytm Oszczędny-KMP

---

Znajdujemy wystąpienia x' w tekście $y[k+1..m]$ algorytmem KMP';
dla każdego wystąpienia x' sprawdzamy czy na lewo jest wystąpienie $a^k$;
nie sprawdzamy tych pozycji w y, których zgodność z pewną pozycją w x jest znana;

Rysunek 3:Typowa konfiguracja w algorytmie Oszczędny-KMP.

Pozostawiamy jako ćwiczenie dokładny zapis algorytmu w pseudokodzie oraz dowód tego, że algorytm Oszczędny-KMP wykonuje co najwyżej $\frac{3}{2}n$ porównan.

Ogólna idea jest przedstawiona na rysunku.

Rysunek 4: Ilustracja tego, że liczba operacji dodatkowych jest ograniczona przez $\frac{1}{2}n$.

Niech zasadniczymi operacjami będą operacje sprawdzania pierwszego b na danej pozycji tekstu y,oraz te sprawdzania symboli ktore sa z wynikiem pozytywnym. Takich operacji jest co najwyżej n. Pozostałe operacje to

(1) sprawdzanie w części $\alpha$ z wynikiem negatywnym, wtedy przesuwamy wzorzec co najmniej o k,

(2) sprawdzanie części $a^k$ na lewo od pozytywnego $b$ (w kwadraciku na rysunku), na pozycjach gdzie wcześniej było sprawdzanie negatywnego b. Wtedy odległość między pozytywnymi kolejnymi b jest co najmniej 2w, gdzie $w\le k$ liczba sprawdzanych na lewo symboli a.Zatem lokalnie przesunięcie jest co najmniej dwukrotnie większe niż liczba dodatkowych operacji.

Suma przesunięć wzorca na tekście $y$ wynosi co najwyżej n, tak więc sumaryczna liczba dodatkowych operacji jest co najwyżej $\frac{1}{2}n$, a liczb wszstkich nie przekracza $\frac{3}{2}n$.

Równoważność cykliczna słów

Pokażemy problem, który prawdopodobie najlepiej pokazuje użyteczność porządku liniowego na alfabecie. Rotacją słowa $u=u[1..n]$ jest kaz'rde słowo postaci $u^{(k)}=u[k+1..n]u[1..k]$. (w szczególności $u^{(0)}=u^{(n)}=u)$. Niech $u,w$ będą słowami długości $n$, mówimy, że są one cyklicznie równoważne gdy $u^{(i)}=w^{(j)}$ dla pewnych $i,j$.

Naturalnym algorytmem sprawdzania cyklicznej równoważności jest szukanie słowa $u$ w słowie $ww$, ale podamy algorytm znacznie prostszy bazujący na porządku leksykograficznym , który będzie działal w czasie liniowym i w miejscu (dodatkowa pamięć jest stała).

W algorytmie roszerzamy tablice $u,w$ na $uu,ww$ ale robimy to jedynie dla uproszczenia, w rzeczywistości możemy poruszać się cyklicznie po $u$ i po $w$, pozostawiamy modyfikację jako ćwiczenie.

Algorytm Równoważność-Cykliczna

---

$x:=uu$; $y:=ww$;
$i:=0$; $j:=0$;
while $(i<n)$ and $(j<n)$ do
   $k:=1$;
   while$x[i+k]=y[j+k]$ do $k:=k+1$;
   if $k>n$ then return true;
   if $x[i+k]>y[i+k]$ then$i:=i+k$ else $j:=j+k$;
return false;

Problem poprawności pozostawiamy jako ćwiczenie.

Liczba porównań jest oczywiście liniowa. Pozostawiamy jako ćwiczenie policzenie dokładnego wzoru na maksymalną liczbę porównań symboli dla tekstów długości $n$.