Algorytm Knutha-Morrisa-Pratta

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
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. 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 od 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 J. 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 konwencję tablic indeksowanych od zera 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 indeksu w W oznaczającego następny rozpatrywany znak wzorca. Niech w naszym przykładzie wyglądają tak:

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ą. Niemniej jednak, w czwartej iteracji, dostajemy w S[3] spację, zamiast W[3]='D' - 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ść. Niemniej 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 resetujemy 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ńcuchu "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źc 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ę w indeksie 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ę w indeksie 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, zaamortyzowany 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 żadnego 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 zacząć się nowe potencjalne dopasowanie przed bieżącą pozycją. Inaczej mówiąc, występuje tutaj "wstępne poszukiwanie" samego wzoru i zestawu wszelkich możliwych pozycji do powrotu, które pomijają złe wybory, nie zabierając zasobów.

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 wzoru. Zatem T[i] jest dokładnie 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 wzoru, to jest to szczególna okoliczność (nie mamy już żadnej możliwości wycofywania się), ustawiamy T[0]= -1, jak już wcześniej to przedyskutowaliśmy.

Opracowany przykład algorytmu budowania tabel[edytuj | edytuj kod]

Najpierw rozważmy przykład W = "ABCDABD". Zobaczymy, że zachowuje się w dużym stopniu według schematu głównego wyszukiwania i jest z podobnych powodów wydajny. Ustawiamy T[1] = 0. Podobnie T[2] = 0. Kontynuując do T[3], zauważymy, że jest krótszy sposób sprawdzenia wszystkich końcowych wzorców: powiedzmy, że odkryliśmy właściwy wzorzec początkowy zakończony w W[2] o długości 2 (maksymalna możliwa); wtedy jego pierwszy znak jest właściwym początkowym wzorcem właściwego początkowego wzorca W, więc samego siebie, i kończy się w W[1], który - 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 zawodzi jedynie ten o długości 1, więc T[3] = 0.

Przekazujemy następny w kolejności W[4], 'A'. Ta sama logika 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], którym jest 'B', przećwiczymy następującą logikę: 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ępny znak w kolejnym segmencie, rozpoczynającym się w W[4] = 'A' byłby 'B', i w rzeczy samej jest to także W[5]. Dalej, ten sam argument co powyżej pokazuje, że nie musimy zaglądać za 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 2

Opis i pseudokod algorytmu budowania tabel[edytuj | edytuj kod]

Powyższy przykład ilustruje ogólną technikę zapełniania tabeli przy najmniejszym wysiłku. Zasadą takiego wyszukiwania jest to, że większość pracy została wykonana podczas docierania do aktualnej pozycji, więc nie trzeba wiele robić aby ją opuścić. Jedyną drobną komplikacją jest to, że logika, która jest poprawna w dalszej części łańcucha błędnie generuje niewłaściwe ciągi znaków na początku. Wymaga to odrobiny 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 nalezy przekazac poprzez argumenty wywolania programu (1. ciag do przeszukania 2. ciag do znalezienia)
int main(int argc, char** argv)
{
   if(argc != 3) {cout << "Nieprawidlowa liczba argumentow" << 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 wystepowania zadanego ciagu
    return 0;    
}

Złożoność obliczeniowa algorytmu opartego na tablicach jednowymiarowych[edytuj | edytuj kod]

Złożoność algorytmu opartego na tablicy wynosi O(n), gdzie n jest długością tablicy W. Poza czynnościami inicjalizacyjnymi, cała praca jest wykonywana w pętli. To wystarcza, aby 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 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 przerwie się, gdy i = n, musi przerwać 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, bo może naraz opuszczać większą część znaków. To znaczy: im mniej musi się cofać, tym szybciej się wykonuje, co jest odzwierciedlone przez obecność zer w tabeli T. Słowo takie jak "ABCDEFG" dobrze działa z tym algorytmem, bo nie zawiera powtórzeń swojego początku, więc jego tabelka to po prostu same zera z -1 na początku. Dla kontrastu, W = "AAAAAA" zadziała strasznie, 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 wzorzec dla T, i może zostać wyczerpany przez słowo takie, jak: S = "AAAAAABAAAAAABAAAAAAA", gdzie algorytm będzie próbował dopasować każde 'A' do 'B' przed zakończeniem działania. To skutkuje w maksymalnej liczbie powtórzeń, podwajając liczbę S, gdyż ilość powtórzeń "AAAAAAB" wzrasta. Chociaż dla tego słowa metoda tablicowa jest szybka (nie ma tutaj żadnego cofania), to przebiega tylko raz dla danego słowa W, kiedy to procedura poszukiwania potencjalnie może przebiegać wiele razy. Jeżeli za każdym razem wyraz główny będzie przeszukany w poszukiwaniu wzorca S, 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 Boyera-Moore'a w przeszukiwaniu ciągu znaków. Jakkolwiek, 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 najlepszy przypadek wielkim kosztem, w najgorszym czasie.

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]