Algorytm Knutha-Morrisa-Pratta

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Algorytm Knutha-Morrisa-Pratta
Rodzaj Wyszukiwanie wzorca
Struktura danych tekst
Złożoność
Czasowa Przetwarzanie wstępne: \Theta(m)

Wyszukiwanie: \Theta(n)

m – długość wzorca

n – długość tekstu

Pamięciowa O(m)

Algorytm Knutha-Morrisa-Pratta – algorytm wyszukiwania wzorca w tekście.

Algorytm wykorzystuje fakt, że w przypadku wystąpienia niezgodności ze wzorcem, sam wzorzec zawiera w sobie informację pozwalającą określić, gdzie powinna się zacząć kolejna próba dopasowania, pomijając ponowne porównywanie już dopasowanych znaków. Dzięki temu właściwy algorytm działa w czasie liniowym względem długości przeszukiwanego tekstu i wzorca (co dla dużych wzorców ma znaczenie).

Algorytm został wynaleziony przez Donalda Knutha i Vaughana Pratta i niezależnie przez Jamesa H. Morrisa w 1977, ale wszyscy trzej opublikowali go wspólnie.

Algorytm KMP[edytuj | edytuj kod]

Przykład działania[edytuj | edytuj kod]

W tym artykule przyjęto jako konwencję indeksowanie od zera tablic służących do przechowywania łańcuchów znaków. Zapis taki jest zgodny ze składnią języka C.

By lepiej zobrazować, jak działa algorytm, przeanalizujmy jego przebieg. Niech dane będą wzorzec W i tekst S. W dowolnej chwili stan algorytmu opisują dwie zmienne: m oraz i, które oznaczają odpowiednio pozycję w S, od której rozpoczyna się aktualne częściowe dopasowanie, oraz indeks w W, oznaczającego następny rozpatrywany znak wzorca. Niech w naszym przykładzie dane są następujące:

m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456

Rozpoczynamy porównując kolejne znaki W do "równoległych" znaków S, przemieszczając się dalej, jeśli pasują. Jednak w czwartej iteracji, dostajemy w S[3] spację, zamiast W[3]='D', czyli mamy niezgodność. Ponieważ 'A' nie występuje na pozycjach 1-3, wiemy, że próby dopasowania wzorca nie powiodą się wcześniej niż na czwartej pozycji. Zatem przesuwamy się tam, ustawiając m=4 oraz i=0.

m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:     ABCDABD
i:     0123456

Szybko otrzymujemy niemal kompletne dopasowanie "ABCDAB", jednak dla W[6] (S[10]) znów mamy niezgodność. Jednak przed końcem bieżącego dopasowania częściowego, natrafiliśmy na "AB", które mogłoby być początkiem nowego dopasowania, musimy więc wziąć je pod uwagę. Jak już wiemy litery te odpowiadają dwóm znakom przed bieżącą pozycją, nie musimy ich ponownie sprawdzać; po prostu ustawiamy m=8, i=2 i kontynuujemy dopasowywanie kolejnego znaku. W ten sposób omijamy nie tylko znaki poprzednio dopasowane w S, ale również te poprzednio dopasowane z W.

m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:         ABCDABD
i:         0123456

Próba odnalezienia wzorca natychmiast kończy się porażką, trafiamy bowiem na spację. Podobnie jak po pierwszej porażce, wracamy na początek W i zaczynamy szukanie od kolejnego znaku ustawiającS: m = 11 oraz zerujemy i=0.

m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:            ABCDABD
i:            0123456

Jeszcze raz, natychmiast natrafiamy na dopasowanie "ABCDAB", lecz kolejny znak, 'C', nie odpowiada ostatniemu znakowi 'D' słowa W. Rozumując jak poprzednio, ustawiamy m=15 oraz (by rozpocząć od dwuznakowego łańcucha "AB") i=2, i rozpoczynamy dopasowywanie od bieżącej pozycji.

m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:                ABCDABD
i:                0123456

Tym razem udało się odnaleźć pełne wystąpienie wzorca; jego pozycja to S[15].

Opis części szukającej algorytmu[edytuj | edytuj kod]

Powyższy przykład zawiera wszystkie elementy algorytmu. Chwilowo opiszemy tylko wyszukiwanie – przy założeniu, że dysponujemy tabelą "cząstkowego dopasowania" T. Jak stworzyć taką tablicę, opisane jest nieco niżej. Tablica ta wskazuje, gdzie musimy szukać początku nowego dopasowania w przypadku, gdy próba odnalezienia wystąpienia wzorca na obecnej pozycji zakończy się niepowodzeniem. Tablicy T używamy w następujący sposób: jeżeli mamy zaczynające się w S[m] dopasowanie, które zawiedzie podczas porównywania S[m + i] z W[i], wtedy następne możliwe dopasowanie rozpocznie się od indeksu m + i – T[i] w S (tj. T[i] jest ilością kroków wstecz, które musimy wykonać, gdy nie istnieje dopasowanie). Dla wygody ustawiamy więc T[0] = -1 – jeśli W[0] nie zostanie dopasowane, nie możemy się cofnąć i musimy po prostu sprawdzić następny znak. Należy też zauważyć, że skoro po niepowodzeniu na pozycji m+i kolejne możliwe dopasowanie rozpocznie się od indeksu m + i – T[i], kontynuujemy więc szukanie od W[T[i]]. Poniżej znajduje się opis części szukającej algorytmu KMP zapisany w pseudokodzie .

algorytm kmp_search:
   wejście:
       tablica znaków, S (przeszukiwany tekst)
       tablica znaków, W (szukane słowo)
   wyjście:
       liczba całkowita (liczona od zera pozycja w S, na której znaleziono W)
   zdefiniowane zmienne:
       liczba całkowita,          m = 0 (początek bieżącego dopasowania w S)
       liczba całkowita,          i = 0 (pozycja bieżącego znaku w W)
       tabela liczb całkowitych,  T (tabela liczona gdzie indziej)
   dopóki m + i jest mniejsze niż długość S, wykonuj:
       jeżeli W[i] = S[m + i], niech i = i + 1
        jeżeli i równe jest długości W, zwróć m
       w przeciwnym przypadku,
      niech m = m + i – T[i], oraz jeśli i > 0, niech i = T[i]
   (jeśli dotrzemy tu, tzn., że przeszukaliśmy bezskutecznie cały S)
   zwróć długość S

Wydajność części szukającej algorytmu[edytuj | edytuj kod]

Przy założeniu, że tablica T była już wyliczona, zamortyzowany koszt algorytmu Knutha-Morrisa-Pratta wynosi O(k), gdzie k jest długością tekstu S. Ponieważ większa część obliczeń wykonywana jest w pętli while, wystarczy, że oszacujemy maksymalną ilość jej przebiegów. Rozpatrzmy najpierw najgorszy przypadek. Łatwiej będzie opisać go na przykładzie. Gdy dla danych

S=AAAAAABAC....
W=AAAAAA

algorytm po znalezieniu częściowego dopasowania A6 (zaczynającego się na pozycji 0) natrafi na B (na pozycji 6), spróbuje odrzucić pierwsze A i rozpocznie z A5 (na pozycji 1), gdzie spróbuje dopasować A6. Wciąż jednak natrafia na B, będzie więc sukcesywnie cofał się krok po kroku aż do A1 (na pozycji 5). Dopiero potem, gdy i ta próba dopasowania zakończy się porażką, przejdzie do następnego znaku. Taka sytuacja wymaga O(n) operacji, gdy n jest długością wzorca. Gdy pomnożymy n przez k wyjdzie na to, że algorytm KMP wcale nie jest szybszy od naiwnego algorytmu wyszukiwania wzorca. Zauważmy jednak, że algorytm, aby móc cofnąć się o jedno miejsce, musi wcześniej przeczytać przynajmniej jeden znak, zatem sytuacje takie jak ta mogą wystąpić jedynie w k/m przypadkach. Z tej prostej obserwacji wynika, że zamortyzowany koszt działania algorytmu wynosi około 2*k, a więc mieści się w O(k).

Tablica częściowych dopasowań[edytuj | edytuj kod]

Celem tej tabeli jest umożliwienie algorytmowi niedopasowywania któregokolwiek znaku z S więcej niż raz. Kluczową obserwacją natury liniowego poszukiwania, która na to pozwala, polega na tym, że mając porównany pewien segment głównego ciągu znaków z początkowym fragmentem wzorca, wiemy dokładnie, w których miejscach mogłoby się zacząć nowe potencjalne dopasowanie przed bieżącą pozycją. Inaczej mówiąc, występuje tutaj "wstępne przeszukiwanie" samego wzorca i zebranie zestawu wszelkich możliwych pozycji do powrotu, które pomijają złe wybory i zwiekszają przez to efektywność wyszukiwania wzorca w tekście.

Chcemy mieć możliwość wyszukania, dla każdej pozycji w W, długości najdłuższego możliwego początkowego segmentu W wskazującego (ale nie zawierającego) tę pozycję, inną niż całe segmenty zaczynające się w W[0], których nie dało się dopasować; to wyznacza nam, jak daleko mamy się cofnąć w znajdowaniu kolejnego dopasowania. Zatem T[i] jest długością najdłuższego możliwego początkowego segmentu W, który jest także podciągiem kończącym się w W[i-1]. Zakładamy, że pusty ciąg ma długość 0. Kiedy występuje rozbieżność na samym początku wzorca, to jest to szczególna okoliczność (nie mamy już żadnej możliwości wycofywania się), ustawiamy T[0]= -1.

Przykład algorytmu budowania tabeli T[edytuj | edytuj kod]

Najpierw rozważmy przykład W = "ABCDABD". Zobaczymy, że algorytm zachowuje się w dużym stopniu według schematu głównego wyszukiwania i jest z podobnych powodów wydajny. Ustawiamy T[0] = -1. Aby wyznaczyć T[1] musimy znaleźć właściwy sufiks "A", który jest również prefiksem W. Jednakże nie ma właściwych sufiksów "A", więc ustawiamy T[1] = 0. Podobnie T[2] = 0. Kontynuując dla T[3], zauważymy, że jest szybszy sposób sprawdzenia wszystkich sufiksów: załóżmy, że znaleźliśmy właściwy sufiks, który jest jednocześnie właściwym prefiksem, zakończonym w W[2] o długości 2 (maksymalna możliwa); wtedy jego pierwszy znak jest też właściwym prefiksem samego wzorca W, a zarazem samego siebie, i kończy się w W[1], co – jak już określiliśmy – nie może wystąpić. Zatem nie potrzebujemy nawet zajmować się wzorcami o długości 2, i jak w poprzednim przypadku odpada jedynie ten o długości 1, więc T[3] = 0.

Przekazujemy następny w kolejności znak W[4], czyli 'A'. Ta sam sposób rozumowania pokazuje, że najdłuższy wzorzec, który musimy rozważyć ma długość 1 i pomimo że w tym przypadku 'A' zadziała, należy pamiętać, że szukamy segmentów kończących się przed bieżącym znakiem, zatem również T[4] = 0.

Rozważając teraz kolejny znak, W[5], czyli 'B', prześledźmy następujące rozumowanie: jeśli mielibyśmy znaleźć wzorzec zaczynający się przed poprzednim znakiem W[4], kontynuując do bieżącego W[5], wtedy w szczególności on sam zawierałby właściwy segment początkowy kończący się w W[4], zaczynający się przed nim, co zaprzecza faktowi, że już znaleźliśmy to 'A', które jest najwcześniejszym wystąpieniem właściwego segmentu kończącego się w W[4]. Zatem nie musimy patrzeć za łańcuch końcowy dla W[5]. Faktycznie sprawdzając go, odkryjemy, że jest to 'A', to samo jak w W[0]. Zatem T[5] = 1.

Ostatecznie zauważamy, że następnym znakiem w kolejnym segmencie, rozpoczynającym się w W[4] = 'A' byłoby 'B', i w rzeczy samej jest to także W[5]. Dalej, ten sam argument co powyżej uzasadnia, że nie musimy zaglądać poza W[4], by odnaleźć segment dla W[6], więc to jest to, i otrzymujemy T[6] = 2.

W ten sposób otrzymujemy następującą tabelę:

i 0 1 2 3 4 5 6
W[i] A B C D A B D
T[i] -1 0 0 0 0 1 -1

Opis i pseudokod algorytmu budowania tabeli T[edytuj | edytuj kod]

Powyższy przykład ilustruje ogólną technikę zapełniania tabeli przy najmniejszym wysiłku. Podstawą dla takiego podejścia jest to, że większość pracy zostaje wykonana podczas docierania do aktualnej pozycji, więc nie trzeba wiele robić przy przechodzeniu do następnej pozycji. Jednakże metoda, która jest poprawna w dalszej części łańcucha, powoduje błędne generowanie ciągów znaków na początku łańcucha. Można to naprawić dzięki wprowadzeniu niezbyt rozbudowanego kodu inicjującego.

algorytm kmp_table:
   Dane wejściowe:
       tablica znaków,            W (słowo, które będzie analizowane)
       tablica liczb całkowitych, T (która ma być zapełniona)
   Dane wyjściowe:
       nic (ale podczas działania zapełniana jest tablica wejściowa)
   Zdefiniowane zmienne:
       liczba całkowita, i = 2 (aktualna pozycja, jaką przetwarzamy w tablicy T)
       liczba całkowita, j = 0
       (liczony od zera indeks tablicy W, w której ma być umieszczona kolejna litera szukanego ciągu znaków)
       (pierwszych kilka wartości to stałe, ale inne, niż algorytm mógłby sugerować)
         niech T[0] = -1, T[1] = 0
       dopóki i jest mniejsze od długości w, rób:
       (pierwsza opcja: ciąg znaków jest dłuższy)
         jeżeli W[i – 1] = W[j], niech T[i] = j + 1, i = i + 1, j = j + 1
       (druga opcja: ciąg znaków nie jest dłuższy, ale nie możemy się cofnąć)
       w przeciwnym przypadku,
          jeśli j > 0, niech j = T[j]
        (trzeci przypadek: wyczerpuje się zasób kandydatów, Zauważ, że j=0)
       w przeciwnym przypadku,
          niech T[i] = 0, i = i + 1

Przykład implementacji w języku C++[edytuj | edytuj kod]

#include <string>
#include <vector>
#include <iostream>
 
using namespace std;
// po kompilacji parametry należy przekazać poprzez argumenty wywołania programu (1. ciąg do przeszukania 2. ciąg do znalezienia)
int main(int argc, char** argv)
{
   if(argc != 3) {cout << "Nieprawidłowa liczba argumentów" << endl;return 1;}
   string napis;
   napis = argv[1];
   string wzorzec;
   wzorzec = argv[2];
   unsigned int m, i, k;
   vector<int> T;                             // tablica częściowego dopasowania
   vector<int> places;
   cout << "Wzorzec: " << wzorzec.length() << endl;
   cout << "Napis: " << napis << endl;
   for(i=0 ; napis[i]!='\0' ; i++)
     cout << "napis[" << i << "] = " << napis[i] << endl;
   for(i=0 ; napis[i]!='\0' ; i++) {
     if( napis[i] == wzorzec[0] )
        T.push_back(i);
   }
   for(i=0 ; i < T.size() ; i++)
     cout << "T[" << i << "] = " << T[i]<< endl;
   for( i=0, k=0, m=T[k] ; (m+i) <= napis.length() ; i++ )
    {
     if( wzorzec[i] != napis[m+i] ){  // nie pasuje
        m=T[++k];
        i=0;
       }
       if( i == wzorzec.length()-1 ){             // pasuje
        places.push_back(T[k]);
           m=T[++k];
        i=0;
       }
    }
   for(i=0 ; i < places.size() ; i++)
     cout << "Places[" << i << "] = " << places[i]<< endl; // wypisz miejsca występowania żądanego ciągu
   return 0;
}

Złożoność obliczeniowa algorytmu budowania tabeli T[edytuj | edytuj kod]

Złożoność algorytmu budowania tablicy wynosi O(n), gdzie n jest długością tablicy W. Poza inicjacją, cała praca jest wykonywana w pętli. Wystarczy więc pokazać, że ta pętla wykonuje się w czasie O(n), jednocześnie badając wartości i oraz i-j. W pierwszej pętli wartość różnicy i – j jest zachowana, jako że i oraz j są zwiększane jednocześnie, ale naturalnie to i jest zwiększane. W drugiej pętli j jest zastępowane przez T[j], które – jak widzieliśmy wcześniej – jest zawsze mniejsze od j, zatem zwiększa się różnica i – j. W trzeciej pętli i jest zwiększane, j pozostaje bez zmian, a więc zarówno i oraz i – j wzrasta. Ponieważ i ≥ i – j, to znaczy, że na każdym etapie albo i albo dolna granica i się zwiększa; zatem, gdy algorytm zakończy się, gdy i = n, musi zakończyć się po najwyżej 2n iteracjach pętli, bo i – 1 zaczyna się od 1. Więc złożoność algorytmu to O(n).

Wydajność algorytmu Knutha-Morrisa-Pratta[edytuj | edytuj kod]

Skoro algorytm składa się z dwóch części, z czego pierwsza ma złożoność O(k) a druga O(n), to całkowita złożoność jest równa sumie złożoności częściowych, czyli O(k+n).

Jest oczywiste, że w opracowanym przykładzie algorytm będzie miał największą przewagę nad algorytmem naiwnym, gdy może naraz opuszczać większą część znaków tekstu. To znaczy: im mniej musi się cofać, tym szybciej się wykonuje się wyszukiwanie, co jest odzwierciedlone przez obecność zer w tabeli T. Przykładowo wzorzec taki jak W = "ABCDEFG" jest korzystnym przykładem dla tego algorytmu, bo nie zawiera powtórzeń swojego początku, więc jego tabela T to po prostu same zera z -1 jedynie na początku. Dla kontrastu, dla wzorca W = "AAAAAA" algorytm zadziała gorzej, bo jego tabela ma postać:

i 0 1 2 3 4 5 6
W[i] A A A A A A A
T[i] -1 0 1 2 3 4 5

Jest to najgorszy możliwy rodzaj wzorca dla T, i może zostać użyty dla tekstu takiego, jak: S = "AAAAAABAAAAAABAAAAAAA", gdzie algorytm będzie próbował dopasować każde 'A' do 'B' przed zakończeniem działania. To skutkuje maksymalną liczbą powtórzeń, gdy ilość powtórzeń segmentu "AAAAAAB" wzrasta. Chociaż dla tego tekstu metoda tablicowa jest szybka (nie ma tutaj żadnego cofania), to przebiega tylko raz dla danego wzorca W, kiedy to procedura poszukiwania potencjalnie może przebiegać go wiele razy. Jeżeli za każdym razem tekst S będzie przeszukany w poszukiwaniu wzorca, to ogólna wydajność będzie najgorsza z możliwych. Wybierając sposób porównywania, to szczególne połączenie będzie znakomitym przypadkiem do zastosowania algorytmu algorytm Boyera-Moore'a. Jednakże algorytm KMP gwarantuje, że poszukiwanie zostanie wykonane w liniowym czasie, zarówno w najlepszym i najgorszym przypadku, podczas gdy algorytm Boyera-Moore'a osiąga O(n+m) dla najgorszego przypadku, gdy wzorzec nie występuje w tekście, oraz O(nm) dla najgorszego przypadku, gdy wzorzec występuje w tekście.

Zobacz też[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

  • Donald Knuth; James H. Morris, Jr, Vaughan Pratt (1977). "Fast pattern matching in strings". SIAM Journal on Computing 6 (2): 323-350.
  • Thomas H. Cormen; Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2001). “Section 32.4: The Knuth-Morris-Pratt algorithm”, Introduction to Algorithms, Second edition, MIT Press and McGraw-Hill, 923-931. ISBN 0-262-03293-7.

Linki zewnętrzne[edytuj | edytuj kod]