Algorytmy i struktury danych/Algorytmy tekstowe I

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ą $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]\neq 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.

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]]\leq S[P[i]]$. Po zakończeniu $i$-tej iteracji mamy $S[15]=3,Zakres[3]=15$.

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 $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\leq 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.

<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. 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.

Rysunek 1: Jedna iteracja algorytmu KMP. Przesunięcie $shift=j-P'[j]$ potencjalnego początku wystąpienia wzorca gdy $x[j+1]\neq 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]\neq 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]\ {\text{oraz}}\ x[t+1]\neq x[j+1])\ \Rightarrow \ P'[j]=t$

$(t=P[j],\ t\geq 0,\ {\text{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.