Algorytmy i struktury danych/Algorytmy tekstowe I

From Studia Informatyczne

Algorytmy tekstowe I

Spis treści


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ą x[1,\ldots,n], elementami której są symbole ze skończonego 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, kombinatoryczne własności tekstów. Okresem tekstu x jest każda niezerowa liczba naturalna p taka, że x[i]=x[i+p], dla każdego i, 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 |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 wartością sztuczną (przyjmiemy, że P[0]=-1).


Wprowadzimy również tablicę ‘’'silnych prefikso-sufiksów dla wzorca x[1..m]: jeśli j<|x|, to P'[j]=k, gdzie k jest maksymalnym rozmiarem słowa będącego właściwym prefiksem i sufiksem x[1..j] i spełniającego dodatkowy warunek x[k+1]\ne x[j+1] dla j<n.
Jeśli takiego k nie ma, to przyjmujemy P'[j]=-1.
Przyjmujemy ponadto, że P'[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'[0..5]\ =\ [-1,\ 0,\ -1,\ 1,\ 0,\ 2\ ].

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 x[j]=x[t+1] oraz t=P[j-1], to P[j]= t+1

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

Algorytm Prefikso-Sufiksy


1  P[0]:=-1; t:=-1;
2  for j:=1 to m do
3   begin
4    while t\geq 0 and x[t+1]\neq x[j] do t:=P[t];
5    t:=t+1; P[j]:=t;
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 t:=P[t] zmniejsza wartość t co najmniej o jeden. Proste zastosowanie zasady magazynu (lub potencjału) implikuje, że operacji t:=P[t] 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 S[i] będzie rozmiarem minimalnego słowa pokrywającego tekst x[1..i].

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

Grafika:Minpokslowo.jpg

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

Algorytm Rozmiar-Minimalnego-Pokrycia


  1. for i:=2 to n do begin
  2. Zakres[i]=i; S[i]=i;
  3. end;
  4. for i:=2 to n do
  5. if P[i]>0 and i-Zakres[S[P[i]]] <= S[P[i]] then begin
  6. S[i] := S[P[i]]; Zakres[S[P[i]] := i
  7. end;
  8. 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 y wszystkie (lub pierwsze) wystąpienia danego tekstu x, 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 m=|x|, n=|y|, gdzie m\le n.

Zaczniemy od obliczania jedynie pierwszego wystąpienia. Algorytm MP 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 na końcu wartość false, jeśli nie zwróci wcześniej true.


Algorytm Algorytm MP


1  i:=0; j:=0;
2  while i\leq n-m do begin
3    while j<m and x[j+1]=y[i+j+1] do j=j+1;
4    if j=m then return(true);
5    i:=i+j-P[j]; j:=\max(0,P[j])
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: x[j+1]=y[i+j+1]. 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 i 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.




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. 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.
Grafika:Kmp.gif
Rysunek 1: Jedna iteracja algorytmu KMP. Przesunięcie shift=j-P'[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 (na bieżąco) odpowiedź:

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

Algorytm On-Line-KMP


0  j:=0;
1  repeat forever
2    read(symbol);
3    while j>-1 and x[j+1]\ne symbol do j:=P'[j];
4    j:=j+1;
5    if j=m then 
6      write(1); j := P'[m];
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 x=aaaa\dots a oraz y=a^{m-1}b, to delay(m)=O(1), delay'(m)=\Theta(m).

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

delay(m)\ =\ \Theta(\log m)

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

(t=P[j]\ \textrm{oraz}\ x[t+1]\neq x[j+1])\ \Rightarrow\ P'[j]=t

(t=P[j],\ t\ge 0,\ \textrm{oraz}\ x[t+1]= x[j+1])\ \Rightarrow\ P'[j]=P'[t]

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


Algorytm Silne-Prefikso-Sufiksy


1  P'[0]:=-1; t:=-1;
2 for j:= 1 to m do
3 while t\geq 0 and x[t+1]\neq x[j]do 4 t:=P'[t]; 5 t:=t+1; 6 if j=m or x[t+1]\neq x[j+1] 7 then P'[j]:=t else P'[j]:=P'[t];


Gdy weźmiemy x\ =\ aba^{m-2} to
P'[0]=-1, P'[1]=0, P'[2]=-1, oraz dla 3\leq j\leq m P'[j]=1.
Jest to jest pesymistyczny przypadek dla algorytmu Silne-Prefikso-Sufiksy, algorytm wykonuje wtedy 3m-5 porównań symboli.