Algorytmy i struktury danych/Algorytmy tekstowe I

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Algorytmy tekstowe I

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 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 liczba naturalna niezerowa 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 x) prefiks tekstu x będący jednocześnie sufiksem x. 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 potem ).

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:

W algorytmie obliczania korzystamy z wartości dla .

Algorytm Prefikso-Sufiksy


; ;
for to do
   while and do
   ; ;

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 tablicy 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 dla prefiksu . Następujący algorytm oblicza długość minimalnego słowa pokrywającego tekstu x. Obliczamy wartości najmniejszej długości minimalnego słowa pokrywającego dla każdego . W -tej iteracji algorytm pamięta jaki jest ``znany zakres każdego minimalnego słowa pokrywającego.

Minpokslowo.jpg

Rysunek 3: -ta iteracja algorytmu dla oraz słowa . Tuż przed rozpoczęciem tej iteracji mamy , , . Po zakończeniu -tej iteracji

mamy , ponieważ .

Algorytm Rozmiar-Minimalnego-Pokrycia


for to do
   

for to do
   if oraz then
      ; ;

return ;

Poprawność jest pozostawiona jako ćwiczenie.

Tablica Silnych Prefikso-Sufiksów

Wprowadzimy silną tablicę 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:


Algorytm 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;
for 1 to do //
   while and do
      ;
   ;
   if or
      then else ;

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

String-matching: algorytm Knutha-Morrisa-Pratta

Przedstawimy klasyczny algorytm Knutha-Morrisa-Pratta (w skrócie KMP) dla problemu string-matchingu:   obliczyć w w tekście wszystkie (lub pierwsze) wystąpienia danego tekstu , zwanego wzorcem (ang. pattern).

Oznaczmy , gdzie .

Operacją dominującą w algorytmie jest porównanie dwóch symboli.

Zaczniemy od obliczania jedynie pierwszego wystąpienia. Algorytm KMP 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. Pozostawiamy dowód poprawności (określenie niezmienników) jako ćwiczenie.


Algorytm Algorytm KMP


; ;
while do
   while and do ;
   if then return(true);
   ;

Operacją dominującą w algorytmie jest operacja: .

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


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


repeat forever
   read();
   while and do ;
   ;
   if then
      write(1); ;
   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.

Wersja real-time algorytmu KMP

Pokażemy teraz wersję algorytmu on-line, która działa w czasie rzeczywistym, tzn. czas reakcji między wczytaniem symbolu a 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.

Rtkmp.png
Rysunek 2: Typowa konfiguracja w algorytmie real-time-KMP.


Algorytm Real-Time-KMP


inicjalizacja: ; Kolejka ;
repeat forever
   read(symbol);
   insert(symbol,Kolejka);
   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.

Oczywiste jest, że opóźnienie (czas reakcji) tego algorytmu jest O(1).

Pozostawiamy jako ćwiczenie uzasadnienie tego, że algorytm Real-Time-KMP jest poprawny.

Algorytm Real-Time-KMP: funkcja OUTPUT(Kolejka, j)


output 0;
repeat 2 times
   if Kolejka niepusta then
      if then
         j 0; delete(Kolejka);
      else if then ;
      else
         ; delete(Kolejka);
         if
            output 1; j ;
return(output);


Wersja algorytmu KMP z 3n/2 porównaniami

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 . Na początku załóżmy, że . Następujący algorytm znajduje wszystkie wystąpienia wzorca ab w tekście y.

Algorytm Szukanie-ab


wzorcem jest
;
while do
   while do;
   if then
      wypisz-wystąpienie;ii+2

Algorytm KMP dla wzorca ab wykonywał 2n-2 porównań symboli, nowy algorytm jest lepszy. Zachodzi fakt:     algorytm Szukanie-ab wykonuje co najwyżej n porównań w tym przypadku.

Uzasadnienie pozostawiamy jako ćwiczenie.

Uogólnimy algorytm na dowolne wzorce. Niech x zawiera co najmniej dwa różne symbole, , gdzie .Oznaczmy skrócony wzorzec

Przykład

, wtedy , .


Podamy nieformalny zarys działania oszczędniejszej wersji algorytmu KMP, w której osobno szukamy x' i osobno części .


Niech będzie taką wersją algorytmu KMP, w której szukamy jedynie wzorca , ale tablica jest obliczona dla wzorca . Jeśli i , to wykonujemy przesunięcie potencjalnego początku i wzorca w y o k+1, gdzie . Inaczej mówiąc, nie szukamy wszystkich wystąpień x', ale jedynie takich, które mają sens z punktu widzenia potencjalnego znalezienia na lewo ciągu .

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


Znajdujemy wystąpienia x' w tekście algorytmem KMP';
dla każdego wystąpienia x' sprawdzamy, czy na lewo jest wystąpienie ;
nie sprawdzamy tych pozycji w y, których zgodność z pewną pozycją w x jest znana;

Okmp.png

Rysunek 3:Typowa konfiguracja w algorytmie Oszczędny-KMP.

Pozostawiamy jako ćwiczenie dokładny zapis algorytmu w pseudokodzie oraz dowód tego, że algorytm Oszczędny-KMP wykonuje co najwyżej porównan.

Ogólna idea jest przedstawiona na rysunku.

Okmp2.png

Rysunek 4: Ilustracja tego, że liczba operacji dodatkowych jest ograniczona przez .

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 z wynikiem negatywnym; wtedy przesuwamy wzorzec co najmniej o k,

(2) sprawdzanie części na lewo od pozytywnego (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 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 wynosi co najwyżej n, tak więc sumaryczna liczba dodatkowych operacji jest co najwyżej , a liczba wszystkich operacji nie przekracza .

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 jest każde słowo postaci . (W szczególności . Niech będą słowami długości ; mówimy, że są one cyklicznie równoważne, gdy dla pewnych .

Naturalnym algorytmem sprawdzania cyklicznej równoważności jest szukanie słowa w słowie , 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 na ale robimy to jedynie dla uproszczenia, w rzeczywistości możemy poruszać się cyklicznie po i po ; modyfikację pozostawiamy jako ćwiczenie.

Algorytm Równoważność-Cykliczna


; ;
; ;
while and do
   ;
   while do ;
   if then return true;
   if then else ;
return false;

Problem poprawności pozostawiamy jako ćwiczenie.

Liczba porównań jest oczywiście liniowa. Pozostawiamy jako ćwiczenie wyprowadzenie dokładnego wzoru na maksymalną liczbę porównań symboli dla tekstów długości .