Algorytmy i struktury danych/Algorytmy tekstowe I

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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.