Rozdział 3: Wersje algorytmu Morrisa-Pratta szukania wzorca

Na początek zajmiemy sie obliczaniem 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

P[0] := -1;
t := -1;
for j := 1 to m do begin
    while (t >= 0) and (x[t+1] <> x[j]) do
        t := P[t];
    t := t + 1;
    P[j] := t;
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 $t$. Dowód poprawności pozostawiamy jako ćwiczenie.

Algorytmy Morrisa-Pratta i Knutha-Morrisa-Pratta

Przedstawimy klasyczne algorytmy Morrisa-Pratta (w skrócie MP) oraz Knutha-Morrisa-Pratta (w skrócie KMP) 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 właś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, o ile nie zwróci wcześniej true.

Algorytm MP

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

Algorytm dla $x=ab$, $y=aa..a$ wykonuje $2n-2$ porównań, 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: algorytm KMP

Algorytm KMP
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

Ze względów notacyjnych tablica $P'$ oznaczana jest przez Pp.

j := 0;
repeat forever
begin
    read(symbol);
    while (j > -1) and (x[j+1] <> symbol) do
        j := Pp[j];
    j := j + 1;
    if j = m then begin
        write('1');
        j := Pp[m];
    end else
        write('0');
end;

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.

Wersja real-time algorytmu Morrisa-Pratta

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. Zamiast KMP użyjemy algorytmu MP, którego preprocessing jest prostszy.

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 MP. Rysunek pokazuje relacje tego algorytmu do algorytmu MP. Symbole z wejścia najpierw wędrują do kolejki.

Rysunek: algorytm Real-Time KMP

Algorytm Real-Time KMP

Typowa konfiguracja w algorytmie real-time-MP.

Algorytm Real-Time-MP

j := 0;
Kolejka.clear();
repeat forever { niezmiennik: |Kolejka| <= m - j }
begin
    read(symbol);
    Kolejka.push(symbol);
    write(OUTPUT(Kolejka, j));
end;

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). Wynikiem funkcji jest 0 lub 1, w zależności od tego czy ostatnio wczytany symbol kończy wystąpienie wzorca $x$. Zmienne $Kolejka$, $j$ są globalne.

Procedura OUTPUT(Kolejka, j)

output := 0;
repeat 2 times
begin
    if not Kolejka.empty() then begin
        if j = -1 then begin
            j := 0;
            Kolejka.pop();
        end else if  x[j+1] <> Kolejka.front() then
            j := P[j];
        else begin
            j := j + 1;
            Kolejka.pop();
        end;
        if j = m then begin { w tym momencie Kolejka jest pusta }
            output := 1;
            j := P[m];
        end;
    end;
end;

Poniższy dowód został opracowany przez Jakuba Radoszewskiego.

Zastanówmy się nad poprawnością tego algorytmu. Problem jaki musimy rozwiązać to właściwość algorytmu, którą nazwiemy opóżnieniem. Polega ona na tym, że w danym kroku algorytm może wciąż jeszcze rozważać właściwy prefiks aktualnego słowa i nie dotrzeć w ogóle do rozważenia bieżącej litery. Pokażemy jednak, że w momencie, kiedy nastąpi wystąpienie wzorca, kolejka zostanie opróżniona, co wystarczy do dowodu poprawności algorytmu.

Dowód przeprowadzimy nie wprost - załóżmy, że w tym kroku kolejka się nie opróżni i że jest to pierwsze wystąpienie wzorca, którego algorytm nie zdąża wyśledzić. Zacznijmy rozważanie działania algorytmu od ostatniego miejsca wcześniejszego od bieżącego, w którym kolejka się opróżnia. W tym momencie zachodzi $j < m$ (nawet jeżeli w owym kroku było wystąpienie wzorca w tekście, to ten warunek i tak będzie po tym kroku spełniony) oraz $|Kolejka| = 0$. Pokażemy, że odtąd aż do miejsca wystąpienia wzorca zachodzić będzie niezmiennik $|Kolejka| < m - j$.

Zastanówmy się co się może wydarzyć w dowolnym, kolejnym kroku algorytmu, a co może zmienić wartość zmiennej $j$:

Może być dwukrotnie wywołana instrukcja j := P[j]. Wówczas $|Kolejka|$ wzrasta o 1, $m - j$ wzrasta co najmniej o 2, czyli niezmiennik dalej zachodzi.
Moze być raz wywołana instrukcja j := P[j], a raz j := j + 1 (w jakiejkolwiek kolejności). Wówczas $|Kolejka|$ się nie zmienia, $m - j$ pozostaje bez zmian lub wzrasta, co nie zaburza niezmiennika.
Mogą nastąpić dwie instrukcje powiększające $j$ o 1. Wówczas $|Kolejka|$ maleje o 2, $m - j$ także maleje o 2, zatem niezmiennik pozostaje zachowany.

Kolejka nie może się opróżnić, gdyż zakładamy, że to nie nastąpi przed aktualnie rozważanym wystąpieniem wzorca. Instrukcja j := P[m] również nie może wystąpić, ponieważ oznaczałoby to wcześniejsze od rozważanego niezauważone przez algorytm wystąpienie wzorca w tekście.

Zatem niezmiennik jest zachowany od ostatniego momentu opróżnienia kolejki do momentu niezauważonego wystąpienia wzorca. W chwili przetworzenia literki, która powoduje wystąpienie zachodzi $j = m$, czyli na mocy pokazanego niezmiennika $|Kolejka| < m - m = 0$, $|Kolejka| < 0$. To z kolei daje żądaną sprzeczność.

Oszczędna wersja algorytmu Morrisa-Pratta

Algorytm MP 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 $\frac{3}{2}$. Na początku załóżmy, że $x=ab$. Następujący algorytm znajduje wszystkie wystąpienia wzorca $ab$ w tekście $y$.

Algorytm Szukanie-ab

{ wzorcem jest 'ab' }
i := 0;
while i <= n - m do begin
    while y[i+2] <> 'b' do
        i := i + 1;
    if y[i+1] = 'a' then begin
        wypisz_wystąpienie;
        i := i + 2;
    end;
end;

Algorytm MP dla wzorca $ab$ i tekstu $aaa \ldots aa$ wykonywał $2n-2$ porównań symboli, nowy algorytm jest lepszy. Algorytm Szukanie-ab wykonuje co najwyżej $n$ porównań w tym przypadku, tak jest dla każdego tekstu w którym szukamy $aab$.

Pozostawiamy jako ćwiczenie policzenie maksymalnej liczby porównań dla tego algorytmu (wzorzec $ab$). Widać, że podstawowa idea to sprawdzanie najpierw pierwszego symbolu wzorca różnego od poprzednich.

Uogólnimy algorytm na dowolne wzorce. Niech $x$ zawiera co najmniej dwa różne symbole, $x=a^kx'$, gdzie $a\ne b$. Oznaczmy $x'=b\alpha$ ,,skrócony wzorzec''.

Przykład

$x = aaaabaaaababa$, wtedy $x' = baaaababa$, $\alpha = aaaababa$.

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

Niech MP' będzie taką wersją algorytmu MP, w której szukamy jedynie wzorca $x'$, ale tablica $P$ jest obliczona dla wzorca $x$. Jeśli $j > 0$ i $shift \le k$, to wykonujemy przesunięcie potencjalnego początku i wzorca w $y$ o $k+1$, gdzie $shift=j-P[j]$.

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 $a^k$.

Tak zmodyfikowany algorytm MP' zastosujemy jako część algorytmu Oszczędny-MP.

Algorytm Oszczędny-MP

wzorcem jest $x=a^kb\alpha$
znajdź wszystkie wystąpienia części $bz$ algorytmem MP zmodyfikowanym powyżej;
Dla każdego wystąpienia $b\alpha$ sprawdzamy, czy bezpośrednio na lewo jest $a^k$;
Pozycji tekstu sprawdzonych z wynikiem pozytywnym następny raz nie sprawdzamy.

Graficzna ilustracja działania algorytmu Oszczędny-MP jest pokazana na rysunku.

Rysunek: algorytm Oszczędny-MP

Znajdujemy wystąpienia $x'$ w tekście $y[k+1..m]$ algorytmem MP'; dla każdego wystąpienia $x'$ sprawdzamy, czy na lewo jest wystąpienie $a^k$; nie sprawdzamy tych pozycji w $y$, których zgodność z pewną pozycją w $x$ jest znana.

Oszczędny MP

Typowa konfiguracja w algorytmie Oszczędny-MP.

Pozostawiamy jako ćwiczenie dokładny zapis algorytmu oraz dokładniejszy dowód tego, że algorytm Oszczędny-MP wykonuje co najwyżej $\frac{3}{2}n$ porównan.

Ogólna idea jest przedstawiona na rysunku.

Rysunek: algorytm Oszczędny-MP

Oszczędny MP
Ilustracja tego, że liczba operacji dodatkowych jest ograniczona przez $\frac{1}{2}n$.

Niech zasadniczymi operacjami będą operacje sprawdzania pierwszego $b$ na danej pozycji tekstu $y$ oraz te sprawdzania symboli, które są z wynikiem pozytywnym. Takich operacji jest co najwyżej $n$. Pozostałe operacje to:

sprawdzanie w części $\alpha$ z wynikiem negatywnym; wtedy przesuwamy wzorzec co najmniej o $k$,
sprawdzanie części $a^k$ na lewo od ,,pozytywnego'' $b$ (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 $w \le k$ jest liczbą 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 $y$ wynosi co najwyżej $n$, sumaryczna liczba dodatkowych operacji jest więc co najwyżej $\frac{1}{2}n$, a liczba wszystkich operacji nie przekracza $\frac{3}{2}n$.

Dla tekstu $w\;=\;(a^kba^k)^r$ i wzorca $a^kba^k$ algorytm wykonuje okolo $\frac{3}{2}|w|$ porównań,
w granicy, gdy $k,r \rightarrow \infty $ otrzymujemy współczynnik $\frac{3}{2}$ .

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

Ze względów notacyjnych tablica $P'$ oznaczana jest przez Pp.

Pp[0] := -1;
t := -1;
for j := 1 to m do begin
    while (t >= 0) and (x[t+1] <> x[j]) do
        t := Pp[t];
    t := t+1;
    if (j = m) or (x[t+1] <> x[j+1]) then
        Pp[j] := t
    else
        Pp[j] := Pp[t];
end;

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