Algorytmy i struktury danych/Algorytmy tekstowe I: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
m (Zastępowanie tekstu - "\ =\" na "=")
 
(Nie pokazano 74 wersji utworzonych przez 6 użytkowników)
Linia 3: Linia 3:
 
__TOC__
 
__TOC__
  
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 <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 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 liczba naturalna niezerowa <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.  
+
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 x) prefiks tekstu x  będący jednocześnie sufiksem x.  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.
+
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>.
+
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|||
 
{{przyklad|||
Dla <math>x\ =\ abababababb</math> mamy:
+
Dla <math>x= abababababb</math> mamy:
<center><math>P[1..11]\ =\ [0,\ 0,\ 1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8,\ 0].</math></center>
+
<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 potem <math>P[0]=-1</math>).
+
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==
 
== 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:
+
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><math>x[j]=x[t+1]\ \textrm{oraz}\ t=P[j-1] \ \Rightarrow\ P[j]= t+1</math></center>
+
<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>.
+
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|
 
{{algorytm|Prefikso-Sufiksy|algorytm_prefikso_sufiksy|
<math>P[0]:=-1</math>; <math>t:=-1</math>;<br>
+
<math>P[0]:=-1</math>; <math>t:=-1</math>;
'''for''' <math>j:=1</math> '''to''' <math>m</math> '''do'''<br>
+
'''for''' <math>j:=1</math> '''to''' <math>m</math> '''do'''
&nbsp;&nbsp;&nbsp;'''while''' <math>t\geq 0</math> '''and''' <math>x[t+1]\neq x[j]</math> '''do''' <math>t:=P[t]</math><br>
+
3  '''begin'''
&nbsp;&nbsp;&nbsp;<math>t:=t+1</math>; <math>P[j]:=t</math>;
+
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.
+
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 ==
 
== Minimalne słowo pokrywające ==
Pokażemy pewne proste zastosowanie tablicy prefikso-sufiksów.
+
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
+
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.
+
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.
+
Zajmiemy się problemem: obliczyć w czasie liniowym długość najkrótszego słowa pokrywającego dany tekst ''x''.
  
 
Niech <math>S[i]</math>
 
Niech <math>S[i]</math>
będzie rozmiarem minimalnego słowa pokrywającego dla prefiksu <math>x[1..i]</math>. Następujący algorytm oblicza długość minimalnego słowa
+
będzie rozmiarem minimalnego słowa pokrywającego tekst <math>x[1..i]</math>.  
pokrywającego tekstu x. Obliczamy wartości <math>S[i]</math> najmniejszej długości minimalnego słowa pokrywającego <math>x[1
+
 
\ldots i]</math> dla każdego <math>1 \le i \le n</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
 
W <math>i</math>-tej
iteracji algorytm pamięta jaki jest ``znany zakres'' każdego minimalnego słowa pokrywającego.
+
iteracji algorytmu pamiętany jest ''znany dotychczas zakres'' każdego minimalnego słowa pokrywającego.
  
<center> [[Grafika:Minpokslowo.jpg]]<br>
+
<center> [[Grafika:Minpokslowo.jpg]]<br></center>
  
Rysunek 3: <math>i</math>-ta iteracja algorytmu dla <math>i=15</math> oraz słowa  <math>x\ =\ abaabababaababa\ldots</math>. Tuż przed
+
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>q=S[8]=3</math>, <math>Zakres[3]=13</math>. Po zakończeniu <math>i</math>-tej iteracji
+
rozpoczęciem tej iteracji mamy <math>P[i]=8</math>, <math>S[8]=2,\ Zakres[3]=13</math>.
mamy  <math>S[15]=3,Zakres[3]=15</math>, ponieważ <math>i-Zakres[3] \le q</math>. </center>
+
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|
 
{{algorytm | Rozmiar-Minimalnego-Pokrycia|algorym_rozm_min_pokr|
'''for ''' <math>i:=2</math> '''to''' <math>n</math> '''do'''<br>
+
<Source>
&nbsp;&nbsp;&nbsp;<math>Zakres[i]=i, S[i]=i</math><br>
+
[[pascal,1]]
 
+
for i:=2 to n do begin
'''for ''' <math>i:=2</math> '''to''' <math>n</math> '''do'''<br>
+
  Zakres[i]=i; S[i]=i;
&nbsp;&nbsp;&nbsp;'''if''' <math>P[i]>0</math> oraz <math>i-Zakres[S[P[i]] \le S[P[i]]</math> '''then'''<br>
+
end;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>S[i] := S[P[i]]</math><math>Zakres[S[P[i]] := i</math>;<br>
+
for i:=2 to n do
 
+
  if P[i]>0 and i-Zakres[S[P[i]]] <= S[P[i]] then begin
'''return''' <math>S[n]</math>;
+
    S[i] := S[P[i]];  Zakres[S[P[i]] := i
 +
  end;
 +
return S[n];
 +
</Source>
 
}}
 
}}
  
Poprawność jest pozostawiona jako ćwiczenie.
+
<!--
 
+
{{algorytm | Rozmiar-Minimalnego-Pokrycia|algorym_rozm_min_pokr|
==Tablica Silnych Prefikso-Sufiksów==
+
1  '''for ''' <math>i:=2</math> '''to''' <math>n</math> '''do''' '''begin'''
Wprowadzimy silną tablicę prefikso-sufiksów dla wzorca <math>x[1..m]</math>:
+
2    <math>Zakres[i]=i; S[i]=i;</math>
&nbsp;&nbsp;&nbsp;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>.
+
3  '''end;'''
<br> Jeśli takiego k nie ma, to przyjmujemy <math>P'[j]=-1</math>. Przyjmujemy ponadto, że <math>P'[m]=P[m]</math>.
+
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'''
Wartości tablicy P' mogą być znacznie mniejsze niż wartości tablicy P.
+
6      <math>S[i] := S[P[i]]</math><math>Zakres[S[P[i]] := i</math>;<br>
 
+
7    '''end;'''
{{przyklad|||
+
8  '''return''' <math>S[n]</math>;
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>
 
}}
 
  
Algorytm bazuje na następującej relacji między P i P':
+
==Algorytmy Knutha-Morrisa-Pratta i Morrisa-Pratta==
<center><math>(t=P[j]\ \textrm{oraz}\ x[t+1]\neq x[j+1])\ \Rightarrow\ P'[j]=t</math></center><br>
 
  
<center><math>(t=P[j],\ t\ge 0,\ \textrm{oraz}\ x[t+1]= x[j+1])\ \Rightarrow\ P'[j]=P'[t]</math></center><br>
+
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.
  
Nie musimy liczyć tablicy P, potrzebna jest jedynie ostatnia wartość <math>t=P[j]</math>, którą liczymy on-line.
+
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ę).
 
 
 
 
{{algorytm|Silne-Prefikso-Sufiksy|algorytm_silne_prefikso_sufiksy|
 
<math>P'[0]:=-1</math>; <math>t:=-</math>1;<br>
 
'''for''' <math>j:=</math> 1 '''to''' <math>m</math> '''do''' // <math>t=P[j-1]</math> <br>
 
&nbsp;&nbsp;&nbsp;'''while''' <math>t\geq 0</math> '''and''' <math>x[t+1]\neq x[j]</math>'''do'''<br>
 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>t:=P'[t]</math>;<br>
 
&nbsp;&nbsp;&nbsp;<math>t:=t+1</math>;<br>
 
&nbsp;&nbsp;&nbsp;'''if''' <math>j=m</math> '''or''' <math>x[t+1]\neq x[j+1]</math><br>
 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'''then''' <math>P'[j]:=t</math> '''else''' <math>P'[j]:=P'[t]</math>;<br>
 
}}
 
 
 
Gdyweżmiemy <math>x\ =\ aba^{m-2}</math> to <math>P'[0]=-1</math>, <math>P'[1]=0</math>, <math>P'[2]=-1</math>,oraz <math>P'[j]=1</math>, dla <math>3\leq j\leq m</math>. To jest pesymistyczny przypadek dla algorytmu Silne-Prefikso-Sufiksy, algorytm wykonuje<math>3m-5</math> porównań symboli.
 
 
 
==String-matching: algorytm Knutha-Morrisa-Pratta==
 
 
 
Przedstawimy klasyczny algorytm Knutha-Morrisa-Pratta (w skrócie KMP) 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 (ang. pattern).
 
  
 
Oznaczmy <math>m=|x|, n=|y|</math>, gdzie <math>m\le n</math>.
 
Oznaczmy <math>m=|x|, n=|y|</math>, gdzie <math>m\le n</math>.
  
Operacją ''dominującą'' w algorytmie jest porównanie dwóch symboli.
+
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''.  
 
 
Zaczniemy od obliczania jedynie pierwszego wystąpienia. Algorytm KMP 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'' wartość ''false'' gdy nie zwróci wcześniej ''true''. Pozostawiamy dowód poprawności(określenie niezmienników) jako ćwiczenie.
 
  
  
{{algorytm|Algorytm KMP|algorytm_kmp|
+
{{algorytm|Algorytm MP|algorytm_kmp|
<math>i:=0</math>; <math>j:=0</math>;<br>
+
<math>i:=0</math>; <math>j:=0</math>;
'''while''' <math>i\leq n-m</math> '''do'''<br>
+
'''while''' <math>i\leq n-m</math> '''do''' '''begin'''
&nbsp;&nbsp;&nbsp;'''while''' <math>j<m</math> '''and''' <math>x[j+1]=y[i+j+1]</math> '''do''' <math>j=j+1</math>;<br>
+
3    '''while''' <math>j<m</math> '''and''' <math>x[j+1]=y[i+j+1]</math> '''do''' <math>j=j+1</math>;
&nbsp;&nbsp;&nbsp;'''if''' <math>j=m</math> '''then return'''(true);<br>
+
4    '''if''' <math>j=m</math> '''then return'''(true);
&nbsp;&nbsp;&nbsp;<math>i:=i+j-P'[j]</math>; <math>j:=\max(0,P'[j])</math>
+
5    <math>i:=i+j-P[j]</math>; <math>j:=\max(0,P[j])</math>
 +
6  '''end;'''
 
}}
 
}}
  
Operacją '''dominującą''' w algorytmie jest  operacja: <math>x[j+1]=y[i+j+1]</math>.
+
<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).
  
Udowodnimy, że algorytm KMP wykonuje 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ń w algorytmie KMP.
+
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.
  
  
Linia 130: Linia 136:
 
<flash>file=KMP.swf|width=450|height=220</flash></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.
+
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'''. 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.
+
'''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]]
 
<center>[[Grafika:Kmp.gif]]
Linia 143: Linia 148:
  
 
==Wersja on-line algorytmu KMP==
 
==Wersja on-line algorytmu KMP==
Przedstawimy teraz wersję on-line algorytmu KMP. Wczytujemy kolejne symbole <math>y</math> i wypisujemy on-line (nabieżąco) odpowiedż:
+
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,
 
* 0 - gdy dotychczas wczytany tekst nie zawiera x jako sufiks,
 
* 1 - jeśli zawiera
 
* 1 - jeśli zawiera
  
 
{{algorytm|On-Line-KMP|algorytm_online_KMP|
 
{{algorytm|On-Line-KMP|algorytm_online_KMP|
'''repeat forever'''<br>
+
0  <math> j:=0; </math>
&nbsp;&nbsp;&nbsp;read(<math>symbol</math>);<br>
+
'''repeat forever'''
&nbsp;&nbsp;&nbsp;'''while''' <math>j>-1</math> and <math>x[j+1]\ne symbol</math> '''do''' <math>j:=P'[j]</math>;<br>
+
2    read(<math>symbol</math>);
&nbsp;&nbsp;&nbsp;<math>j:=j+1</math>;<br>
+
3    '''while''' <math>j>-1</math> and <math>x[j+1]\ne symbol</math> '''do''' <math>j:=P'[j]</math>;
&nbsp;&nbsp;&nbsp;'''if''' <math>j=m</math> '''then''' <br>
+
4    <math>j:=j+1</math>;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;write(1); <math>j := P'[m]</math>;<br>
+
5    '''if''' <math>j=m</math> '''then'''  
&nbsp;&nbsp;&nbsp;'''else''' write(0);
+
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.
+
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|||
 
{{przyklad|||
Jeśli <math>x=aaaa\dots a</math> oraz <math>y=a^{m-1b</math>, to <math>delay(m)=O(1)</math>, <math>delay'(m)=\Theta(m) </math>.
+
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:
 
Z lematu o okresowości wynika, że zachodzi następujący fakt:
<center><math> delay(m)\ =\ \Theta(\log m)</math></center>
+
<center><math> delay(m)= \Theta(\log m)</math></center>
  
 
Uzasadnienie pozostawiamy jako ćwiczenie.
 
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 symbolu i daniem odpowiedzi jest O(1) niezależ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. Rysunek pokazuje relacje tego algorytmu do algorytmu KMP. Symbole z wejścia najpierw wędrują do kolejki.
 
<center>[[Grafika:Rtkmp.png]]<br>
 
Rysunek 2: Typowa konfiguracja w algorytmie real-time-KMP.</center>
 
  
  
{{algorytm|Real-Time-KMP|algorytm_rtkmp|
 
inicjalizacja:  <math>j:=0</math>; Kolejka <math>:= \emptyset</math>;<br>
 
'''repeat forever'''<br>
 
&nbsp;&nbsp;&nbsp;read(symbol);<br>
 
&nbsp;&nbsp;&nbsp;insert(symbol,Kolejka); <br>
 
&nbsp;&nbsp;&nbsp;'''write'''(OUTPUT(Kolejka, j));
 
}}
 
  
W celu skrócenia zapisów pojedynczych algorytmów rozbijamy algorytm na dwie części. Zasadnicza część jest zapisana jako osobna funkcja OUTPUT(Kolejka,  j). Funkcja ta liczy 0 lub 1, w zależności od tego czy ostatnio wczytany symbol kończy wystąpienie wzorca x. Zmienne Kolejka, j  są globalne.
 
  
Oczywistym jest że opóźnienie (czas reakcji) tego algorytmu jest O(1).
+
==Obliczanie Tablicy Silnych Prefikso-Sufiksów==
  
Pozostawiamy jako ćwiczenie uzasadnienie tego, że algorytm Real-Time-KMP jest poprawny.
 
  
{{algorytm|Real-Time-KMP: funkcja OUTPUT(Kolejka, j)|algorytm_rtkmp_fun|
+
Algorytm liczenia silnych prefikso-sufiksów bazuje na następującej relacji między P a P':
output <math>:=</math> 0;<br>
+
<center><math>(t=P[j]\ \text{oraz}\ x[t+1]\neq x[j+1])\ \Rightarrow\ P'[j]=t</math></center><br>
'''repeat 2 times'''<br>
 
&nbsp;&nbsp;&nbsp;'''if ''' Kolejka niepusta '''then'''<br>
 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'''if''' <math>j=-1</math> '''then''' <br>
 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;j <math>:=</math> 0; delete(Kolejka);<br>
 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'''else if'''  <math>x[j+1]\ne first(Kolejka)</math> '''then'''  <math>j:=P'[j]</math>;<br>
 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'''else''' <br>
 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>j:=j+1</math>; delete(Kolejka); <br>
 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;'''if''' <math>j=m</math><br>
 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;output <math>:= </math>1; j <math>:= P'[m]</math>; <br>
 
'''return'''(output);
 
  
}}
+
<center><math>(t=P[j],\ t\ge 0,\ \text{oraz}\ x[t+1]= x[j+1])\ \Rightarrow\ P'[j]=P'[t]</math></center><br>
  
==Wersja algorytmu KMP z 3/2.n  porównaniami==
+
Nie musimy obliczać tablicy P; potrzebna jest jedynie ostatnia wartość <math>t=P[j]</math>, którą obliczamy on-line.
  
Algorytm KMP wykonuje co najmniej 2n-m porównań symboli. Załóżmy, że są to operacje dominujące i spróbujmy zmniejszyć stały współczynnik 2 do <math>\frac{3}{2}</math>. Na początku załóżmy, że <math>x=ab</math>.Następujący algorytm znajduje wszystkie wystąpienia wzorca ab w tekście y.
 
  
{{algorytm|Szukanie-ab|algorytm_szukanie_ab|
+
{{algorytm|Silne-Prefikso-Sufiksy|algorytm_silne_prefikso_sufiksy|
wzorcem jest <math>ab</math> <br>
+
<math>P'[0]:=-1</math>; <math>t:=-1</math>;<br>
<math>i:=0</math>; <br>
+
2  '''for''' <math>j:=</math> 1 '''to''' <math>m</math> '''do''' <br>
'''while''' <math>i\leq n-m</math> '''do'''<br>
+
3    '''while''' <math>t\geq 0</math> '''and''' <math>x[t+1]\neq x[j]</math>'''do'''
&nbsp;&nbsp;&nbsp;'''while''' <math>y[i+2]\ne b</math> '''do'''<math>i=i+1</math>;<br>
+
4          <math>t:=P'[t]</math>;
&nbsp;&nbsp;&nbsp;'''if''' <math>y[i+1]= a</math> '''then''' <br>
+
5    <math>t:=t+1</math>;
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;wypisz-wystąpienie;i<math>:=</math>i+2
+
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>
Algorytm KMP dla wzorca ab wykonywał 2n-2 porównań symboli, nowy algorytm jest lepszy. Zachodzi fakt:
+
Gdy weźmiemy <math>x= aba^{m-2}</math> to
&nbsp;&nbsp;&nbsp; algorytm Szukanie-ab wykonuje co najwyżej n porównań w tym przypadku.
+
<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>
Uzasadnienie pozostawimay jako ćwiczenie.
+
Jest to jest pesymistyczny przypadek dla algorytmu Silne-Prefikso-Sufiksy, algorytm wykonuje wtedy <math>3m-5</math> porównań symboli.
 
 
Uogólnimy algorytm na dowolne wzorce. Niech x zawiera co najmniej dwa różne symbole,  <math>x=a^kb\alpha</math>, gdzie <math>a\ne b</math>.Oznaczmy <math>x'=b\alpha</math> ''skrócony wzorzec''
 
 
 
{{przyklad|||
 
<math>x\ =\ aaaabaaaababa</math>, wtedy <math>x'\ =\ baaaababa</math>, <math>\alpha\ =\ aaaababa</math>.
 
 
 
}}
 
 
 
 
 
Podamy nieformalny zarys działania oszczędniejszej wersji algorytmu KMP, w której osobno szukamy x' i osobno części <math>a^k</math>.
 
 
 
 
 
Niech <math>KMP'</math> będzie taką wersją algorytmu KMP w której jedynie szukamy wzorca <math>x'</math>, ale tablica <math>P'</math> jest policzona względem wzorca <math>x</math>.Jeśli <math>j>0</math> i <math>shift\le k</math> to wykonujemy przesunięcie potencjalnego początku i wzorca w y o k+1, gdzie <math>shift=j-P'[j]</math>. 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 <math>a^k</math>.
 
 
 
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|algorytm_okmp|
 
Znajdujemy wystąpienia x' w tekście <math>y[k+1..m]</math> algorytmem KMP';<br>
 
dla każdego wystąpienia x' sprawdzamy czy na lewo jest wystąpienie <math>a^k</math>;<br>
 
nie sprawdzamy tych pozycji w  y, których zgodność z pewną pozycją w x jest znana; <br>
 
<center>
 
[[Grafika:Okmp.png]]<br><br>
 
Rysunek 3:Typowa konfiguracja w algorytmie Oszczędny-KMP.
 
}}
 
</center>
 
 
 
Pozostawiamy jako ćwiczenie dokładny zapis algorytmu w pseudokodzie oraz dowód tego, że algorytm Oszczędny-KMP wykonuje co najwyżej <math>\frac{3}{2}n</math> porównan.
 
 
 
Ogólna idea jest przedstawiona na rysunku.
 
 
 
<center>[[Grafika:Okmp2.png]]<br><br>
 
Rysunek 4: Ilustracja tego, że liczba operacji dodatkowych jest ograniczona przez <math>\frac{1}{2}n</math>.</center>
 
 
 
Niech zasadniczymi operacjami będą operacje sprawdzania pierwszego b na danej pozycji tekstu y, oraz te sprawdzania symboli które sa z wynikiem pozytywnym. Takich operacji jest co najwyżej n. Pozostałe operacje to
 
 
 
(1) sprawdzanie w części <math>\alpha</math> z wynikiem negatywnym, wtedy przesuwamy wzorzec co najmniej o k,
 
 
 
(2) sprawdzanie części <math>a^k</math> na lewo od ''pozytywnego'' <math>b</math> (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 <math>w\le k</math> 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 <math>y</math> wynosi co najwyżej n, tak więc sumaryczna liczba  dodatkowych  operacji jest co najwyżej <math>\frac{1}{2}n</math>, a liczb wszstkich nie przekracza <math>\frac{3}{2}n</math>.
 
 
 
== Równoważność cykliczna słów ==
 
 
 
W poprzednich algorytmach porównywaliśmy symbole jedynie w sensie ich równości. Pokażemy teraz problem, który pokazuje użyteczność porządku liniowego na alfabecie.
 
 
 
Rotacją słowa <math>u=u[1..n]</math> jest kaz'rde słowo postaci <math>u^{(k)}\ =\ u[k+1.. n]u[1.. k]</math>. (w szczególności
 
<math>u^{(0)}=u^{(n)}=u)</math>. Niech <math>u,w</math> będą słowami długości <math>n</math>, mówimy, że są one cyklicznie równoważne
 
gdy  <math>u^{(i)}=w^{(j)}</math> dla pewnych  <math>i,j</math>.
 
 
 
Naturalnym algorytmem sprawdzania cyklicznej równoważności jest szukanie słowa <math>u</math> w słowie <math>ww</math>, ale podamy
 
algorytm znacznie prostszy bazujący na porządku leksykograficznym , który  będzie działał  w czasie liniowym i  ''w miejscu'' (dodatkowa
 
pamięć jest stała).   
 
 
 
W algorytmie rozszerzamy tablice  <math>u,w</math> na <math>uu,\ ww</math> ale robimy to jedynie dla
 
uproszczenia, w rzeczywistości możemy poruszać się cyklicznie po <math>u</math> i po <math>w</math>, pozostawiamy modyfikację jako
 
ćwiczenie.
 
 
 
{{algorytm|Równoważność-Cykliczna|algorytm_równoważność_cykliczna|
 
<math>x:=uu</math>; <math>y:=ww</math>;<br>
 
<math>i:=0</math>; <math>j:=0</math>;<br>
 
'''while''' <math>(i<n)</math> '''and''' <math>(j<n)</math> '''do'''<br>
 
&nbsp;&nbsp;&nbsp;<math>k:=1</math>;<br>
 
&nbsp;&nbsp;&nbsp;'''while'''<math>x[i+k]=y[j+k]</math> '''do''' <math>k:=k+1</math>;<br>
 
&nbsp;&nbsp;&nbsp;'''if''' <math>k>n</math> '''then return''' true;<br>
 
&nbsp;&nbsp;&nbsp;'''if''' <math>x[i+k]>y[i+k]</math> '''then'''<math>i:=i+k</math> '''else''' <math>j:=j+k</math>;<br>
 
'''return''' false;<br>
 
}}
 
 
 
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 <math>n</math>.
 

Aktualna wersja na dzień 12:51, 9 cze 2020

Algorytmy tekstowe I

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ą , elementami której są symbole ze skończonego zbioru A (zwanego alfabetem). Liczba 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 jest każda niezerowa liczba naturalna taka, że , dla każdego , 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 jest długością prefikso-sufiksu x. Jeśli to prefikso-sufiksem x jest słowo puste o długości zerowej.

Oznaczmy przez rozmiar prefikso-sufiksu . Zatem , gdzie .


Przykład

Dla mamy:

Wartość jest wartością sztuczną (przyjmiemy, że ).


Wprowadzimy również tablicę ‘’'silnych prefikso-sufiksów dla wzorca : jeśli , to , gdzie jest maksymalnym rozmiarem słowa będącego właściwym prefiksem i sufiksem i spełniającego dodatkowy warunek dla .
Jeśli takiego k nie ma, to przyjmujemy .
Przyjmujemy ponadto, że .
Wartości tablicy P' mogą być znacznie mniejsze niż wartości tablicy P.

Przykład

Dla mamy:

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:

Jeśli oraz , to

W algorytmie obliczania korzystamy z wartości , dla .

Algorytm Prefikso-Sufiksy


1  ; ;
2  for  to  do
3   begin
4    while  and  do 
5    ; ;
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 zmniejsza wartość t co najmniej o jeden. Proste zastosowanie zasady magazynu (lub potencjału) implikuje, że operacji 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 będzie rozmiarem minimalnego słowa pokrywającego tekst .

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

Minpokslowo.jpg

Rysunek 1: -ta iteracja algorytmu dla oraz słowa . Tuż przed rozpoczęciem tej iteracji mamy , . Zatem spełniony jest warunek . Po zakończeniu -tej iteracji mamy .

Algorytm Rozmiar-Minimalnego-Pokrycia


[[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];


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-matchingu:   obliczyć w w tekście wszystkie (lub pierwsze) wystąpienia danego tekstu , 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 , gdzie .

Zaczniemy od obliczania jedynie pierwszego wystąpienia. Algorytm MP przegląda tekst y od lewej do prawej, sprawdzając, czy jest zgodność na pozycji we wzorcu x oraz na pozycji 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


1  ; ;
2  while  do begin
3    while  and  do ;
4    if  then return(true);
5    ; 
6  end;


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.

Operacją dominującą w algorytmach KMP i MP jest operacja porównania symboli: . 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 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ń.
Poniższa animacja pokazuje przykładowe działanie algorytmu KMP.


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

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

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.

Kmp.gif



Rysunek 1: Jedna iteracja algorytmu KMP. Przesunięcie potencjalnego początku wystąpienia wzorca gdy .

Wersja on-line algorytmu KMP

Przedstawimy teraz wersję on-line algorytmu KMP. Wczytujemy kolejne symbole 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


0  
1  repeat forever
2    read();
3    while  and  do ;
4    ;
5    if  then 
6      write(1); ;
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.

Przykład

Jeśli oraz , to , .

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

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':



Nie musimy obliczać tablicy P; potrzebna jest jedynie ostatnia wartość , którą obliczamy on-line.


Algorytm Silne-Prefikso-Sufiksy


1  ; ;
2 for 1 to do
3 while and do 4 ; 5 ; 6 if or 7 then else ;


Gdy weźmiemy to
, , , oraz dla .
Jest to jest pesymistyczny przypadek dla algorytmu Silne-Prefikso-Sufiksy, algorytm wykonuje wtedy porównań symboli.