Tekst źródłowy strony Algorytmy i struktury danych/Algorytmy tekstowe I

<font size="6"> Algorytmy tekstowe I </font>

__TOC__

Algorytmy tekstowe mają decydujące znaczenie przy wyszukiwaniu informacji typu tekstowego, ten typ informacji jest szczególnie popularny w informatyce, np. w edytorach tekstowych i wyszukiwarkach internetowych. Tekst jest ciągiem symboli. Przyjmujemy, że jest on zadany tablicą <math>x[1,\ldots,n]</math>, elementami której są symbole ze skończonego zbioru ''A'' (zwanego alfabetem). Liczba <math>n=|x|</math> 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, kombinatoryczne własności tekstów. '''Okresem''' tekstu <math>x</math> jest każda niezerowa  liczba naturalna <math>p</math> taka, że <math>x[i]=x[i+p]</math>, dla każdego <math>i</math>, dla którego obie strony są zdefiniowane. Przez ''per(x)'' oznaczmy minimalny okres x. 


Pojęciem dualnym do okresu jest '''prefikso-sufiks''' tekstu. Jest to najdłuższy właściwy (nie będący całym tekstem) prefiks tekstu ''x''  będący jednocześnie jego sufiksem.  Oczywiste jest, że <math>|x|-per(x)</math> jest długością prefikso-sufiksu ''x''. Jeśli <math>per(x)=|x|</math> to prefikso-sufiksem ''x'' jest słowo puste o długości zerowej.

Oznaczmy przez <math>P[k]</math> rozmiar prefikso-sufiksu <math>x[1..k]</math>. Zatem <math>per(x)=n-P[n]</math>, gdzie <math>n=|x|</math>.



{{przyklad|||
Dla <math>x= abababababb</math> mamy:
<center><math>P[1..11]= [0,\ 0,\ 1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8,\ 0]</math>.</center>

Wartość <math>P[0]</math> jest wartością sztuczną  (przyjmiemy, że <math>P[0]=-1</math>).
}}
<br>
Wprowadzimy również  tablicę ‘’'silnych prefikso-sufiksów''' dla wzorca <math>x[1..m]</math>: 
jeśli <math>j<|x|</math>, to <math>P'[j]=k</math>, gdzie <math>k</math> jest maksymalnym rozmiarem słowa będącego właściwym prefiksem i sufiksem <math>x[1..j]</math> i spełniającego dodatkowy warunek <math>x[k+1]\ne x[j+1]</math> dla <math>j<n</math>. 
<br> Jeśli takiego k nie ma, to przyjmujemy <math>P'[j]=-1</math>. 
<br> Przyjmujemy ponadto, że <math>P'[m]=P[m]</math>.
<br>
Wartości tablicy P' mogą być znacznie mniejsze niż wartości tablicy P. 

{{przyklad|||
Dla <math>x= abaab</math> mamy:
<center><math>P[0..5]= [-1,\ 0,\ 0,\ 1,\ 1,\ 2\ ];\ \ P'[0..5]= [-1,\ 0,\ -1,\ 1,\ 0,\ 2\ ]</math>.</center>
}}

== Obliczanie tablicy  Prefikso-Sufiksów==

Przedstawimy jeden z możliwych algorytmów liniowych obliczania tablicy ''P''. Jest to iteracyjna wersja algorytmu rekurencyjnego, który moglibyśmy otrzymać korzystając z faktu:

<center>Jeśli <math>x[j]=x[t+1]</math> oraz <math>t=P[j-1]</math>, to <math>P[j]= t+1</math></center>

W algorytmie obliczania <math>P[j]</math> korzystamy z wartości <math>P[k]</math>, dla <math>k<j</math>.

{{algorytm|Prefikso-Sufiksy|algorytm_prefikso_sufiksy|
 1  <math>P[0]:=-1</math>; <math>t:=-1</math>;
 2  '''for''' <math>j:=1</math> '''to''' <math>m</math> '''do'''
 3   '''begin'''
 4    '''while''' <math>t\geq 0</math> '''and''' <math>x[t+1]\neq x[j]</math> '''do''' <math>t:=P[t];</math>
 5    <math>t:=t+1</math>; <math>P[j]:=t</math>;
 6   '''end;'''
}}

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

== Minimalne słowo pokrywające ==
Pokażemy pewne  proste zastosowanie tablic prefikso-sufiksów.
Słowem pokrywającym tekst ''x'' jest każdy taki tekst ''y'', którego wystąpienia w ''x''
pokrywają cały tekst ''x''. Na przykład słowo ''y=aba'' pokrywa tekst ''x=ababaaba'', natomiast nie pokrywa tekstu ''abaaababa''.
Zajmiemy się problemem: obliczyć w czasie liniowym długość najkrótszego słowa pokrywającego dany tekst ''x''.

Niech <math>S[i]</math>
będzie rozmiarem minimalnego słowa pokrywającego tekst <math>x[1..i]</math>. 

Następujący algorytm oblicza długość minimalnego słowa
pokrywającego tekstu ''x''.  Algorytm jest efektywny ponieważ liczy dodatkową tablicę ''Zakres''.
W <math>i</math>-tej
iteracji algorytmu pamiętany jest ''znany dotychczas zakres'' każdego minimalnego słowa pokrywającego.

<center> [[Grafika:Minpokslowo.jpg]]<br></center>

Rysunek 1: <math>i</math>-ta iteracja algorytmu dla <math>i=15</math> oraz słowa  <math>x= abaabababaababa\ldots</math>. Tuż przed
rozpoczęciem tej iteracji mamy <math>P[i]=8</math>, <math>S[8]=2,\ Zakres[3]=13</math>. 
Zatem spełniony jest warunek  <math>i-Zakres[S[P[i]] \le S[P[i]]</math>. Po zakończeniu <math>i</math>-tej iteracji
mamy  <math>S[15]=3,Zakres[3]=15</math>.

{{algorytm | Rozmiar-Minimalnego-Pokrycia|algorym_rozm_min_pokr|
<Source>
[[pascal,1]]
for i:=2 to n do begin
   Zakres[i]=i; S[i]=i;
end;
for i:=2 to n do
  if P[i]>0 and i-Zakres[S[P[i]]] <= S[P[i]] then begin
    S[i] := S[P[i]];  Zakres[S[P[i]] := i
  end;
return S[n];
</Source>
}}

<!--
{{algorytm | Rozmiar-Minimalnego-Pokrycia|algorym_rozm_min_pokr|
 1  '''for ''' <math>i:=2</math> '''to''' <math>n</math> '''do''' '''begin'''
 2    <math>Zakres[i]=i; S[i]=i;</math>
 3  '''end;'''
 4  '''for ''' <math>i:=2</math> '''to''' <math>n</math> '''do'''
 5    '''if''' <math>P[i]>0</math> '''and''' <math>i-Zakres[S[P[i]] \le S[P[i]]</math> '''then''' '''begin'''
 6      <math>S[i] := S[P[i]]</math>;  <math>Zakres[S[P[i]] := i</math>;<br>
 7    '''end;'''
 8  '''return''' <math>S[n]</math>;
}}-->

==Algorytmy Knutha-Morrisa-Pratta i Morrisa-Pratta==

Przedstawimy klasyczne algorytmy Knutha-Morrisa-Pratta (w skrócie KMP) oraz Morrisa-Pratta (w skrócie MP) 
dla problemu ''string-matching''u:
&nbsp; obliczyć w w tekście <math>y</math> wszystkie (lub pierwsze) wystąpienia danego tekstu <math>x</math>, zwanego wzorcem.

Algorytmy MP i KMP różnią się jedynie tym że jeden używa tablicy P a drugi P'. Tablica P' jest bardziej skomplikowana, będziemy się zatem głównie koncentrować na algorytmie MP, poza wersją on-line (gdzie waśnie P' ma przewagę).

Oznaczmy <math>m=|x|, n=|y|</math>, gdzie <math>m\le n</math>.

Zaczniemy od obliczania jedynie pierwszego wystąpienia. Algorytm MP przegląda tekst y od lewej do prawej, sprawdzając, czy jest zgodność na pozycji <math>j+1</math> we wzorcu x oraz na pozycji <math>i+j+1</math> 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 na końcu wartość ''false'',  jeśli nie zwróci wcześniej ''true''. 


{{algorytm|Algorytm MP|algorytm_kmp|
 1  <math>i:=0</math>; <math>j:=0</math>;
 2  '''while''' <math>i\leq n-m</math> '''do''' '''begin'''
 3    '''while''' <math>j<m</math> '''and''' <math>x[j+1]=y[i+j+1]</math> '''do''' <math>j=j+1</math>;
 4    '''if''' <math>j=m</math> '''then return'''(true);
 5    <math>i:=i+j-P[j]</math>; <math>j:=\max(0,P[j])</math>
 6  '''end;'''
}}

<br>
'''Uwaga:''' Algorytm działa podobnie gdy zamiast  prefikso-sufiksów użyjemy tablicy P' silnych prefisko-sufksów. Algorytm w całości jest wtedy bardziej skomplikowany  ze względu na trudniejszy ''preprocessing'' 
(liczenie P' jest trudniejsze od P).

Algorytm MP z tablicą P' zamiast P nazywamy '''algorytmem Knutha-Morrisa-Pratta''' i oznaczamy przez KMP.
<br>

Operacją '''dominującą''' w algorytmach KMP i MP jest  operacja porównania symboli: <math>x[j+1]=y[i+j+1]</math>.
Algorytmy KMP i MP wykonują co najwyżej 2n-m porównań symboli. Zauważmy, że dla danej pozycji w tekście y jest ona co najwyżej raz porównana z pewną pozycją we wzorcu w porównaniu pozytywnym (gdy symbole są równe). Jednocześnie każde negatywne porównanie powoduje przesunięcie pozycji <math>i</math> co najmniej o jeden, maksymalna wartość i wynosi n-m, zatem mamy takich porównań co najwyżej n-m, w sumie co najwyżej 2n-m porównań.
<br> Poniższa animacja pokazuje przykładowe działanie algorytmu KMP.


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

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

'''Obserwacja'''. 
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 motywacją dla wprowadzenia silnych prefikso-sufiksów.

<center>[[Grafika:Kmp.gif]]


<br>
Rysunek 1: Jedna iteracja algorytmu KMP. Przesunięcie <math>shift=j-P'[j]</math> potencjalnego początku wystąpienia wzorca gdy <math>x[j+1]\ne y[i+j+1]</math>.</center>

==Wersja on-line algorytmu KMP==
Przedstawimy teraz wersję on-line algorytmu KMP. Wczytujemy kolejne symbole <math>y</math> i wypisujemy on-line (na bieżąco) odpowiedź:
* 0 - gdy dotychczas wczytany tekst nie zawiera x jako sufiks,
* 1 - jeśli zawiera

{{algorytm|On-Line-KMP|algorytm_online_KMP|
 0  <math>j:=0;</math>
 1  '''repeat forever'''
 2    read(<math>symbol</math>);
 3    '''while''' <math>j>-1</math> and <math>x[j+1]\ne symbol</math> '''do''' <math>j:=P'[j]</math>;
 4    <math>j:=j+1</math>;
 5    '''if''' <math>j=m</math> '''then''' 
 6      write(1); <math>j := P'[m]</math>;
 7    '''else''' write(0);
}}

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

{{przyklad|||
Jeśli <math>x=aaaa\dots a</math> oraz <math>y=a^{m-1}b</math>, to <math>delay(m)=O(1)</math>, <math>delay'(m)=\Theta(m)</math>.

Z lematu o okresowości wynika, że zachodzi następujący fakt:
<center><math>delay(m)= \Theta(\log m)</math></center>

Uzasadnienie pozostawiamy jako ćwiczenie.
}}





==Obliczanie Tablicy Silnych Prefikso-Sufiksów==


Algorytm liczenia silnych prefikso-sufiksów bazuje na następującej relacji między P a P':
<center><math>(t=P[j]\ \text{oraz}\ x[t+1]\neq x[j+1])\ \Rightarrow\ P'[j]=t</math></center><br>

<center><math>(t=P[j],\ t\ge 0,\ \text{oraz}\ x[t+1]= x[j+1])\ \Rightarrow\ P'[j]=P'[t]</math></center><br>

Nie musimy obliczać tablicy P; potrzebna jest jedynie ostatnia wartość <math>t=P[j]</math>, którą obliczamy on-line.


{{algorytm|Silne-Prefikso-Sufiksy|algorytm_silne_prefikso_sufiksy|
 1  <math>P'[0]:=-1</math>; <math>t:=-1</math>;<br>
 2  '''for''' <math>j:=</math> 1 '''to''' <math>m</math> '''do''' <br>
 3    '''while''' <math>t\geq 0</math> '''and''' <math>x[t+1]\neq x[j]</math>'''do'''
 4          <math>t:=P'[t]</math>;
 5    <math>t:=t+1</math>;
 6    '''if''' <math>j=m</math> '''or''' <math>x[t+1]\neq x[j+1]</math>
 7      '''then''' <math>P'[j]:=t</math> '''else''' <math>P'[j]:=P'[t]</math>;
}}
<br>
Gdy weźmiemy <math>x= aba^{m-2}</math> to 
<br>
<math>P'[0]=-1</math>, <math>P'[1]=0</math>, <math>P'[2]=-1</math>, oraz dla <math>3\leq j\leq m</math> <math>P'[j]=1</math>. <br>
Jest to jest pesymistyczny przypadek dla algorytmu Silne-Prefikso-Sufiksy, algorytm wykonuje wtedy <math>3m-5</math> porównań symboli.