Algorytm Knutha-Morrisa-Pratta

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

Algorytm Knutha-Morrisa-Pratta

Rodzaj	wyszukiwanie wzorca
Struktura danych	tekst
Złożoność
Czasowa	· przetw. wstępne: $\Theta (m)$ · wyszukiwanie: $\Theta (n)$ gdzie: $m$ – długość wzorca, $n$ – długość tekstu
Pamięciowa	$\mathrm {O} (m)$

Algorytm ten wykorzystuje fakt, że w przypadku wystąpienia niezgodności ze wzorcem, sam wzorzec zawiera w sobie informację pozwalającą określić, gdzie powinna zacząć się kolejna próba dopasowania. Pozwala to na pominięcie ponownego porównywania już dopasowanych znaków. Dzięki temu złożoność algorytmu Knutha-Morrisa-Pratta jest liniowa względem sumy długości przeszukiwanego tekstu i wzorca, co przekłada się na wydajne wyszukiwanie nawet w długich tekstach.

Algorytm został wynaleziony przez Donalda Knutha i Vaughana Pratta oraz niezależnie przez Jamesa H. Morrisa w 1977 roku, ale opublikowany został w jednej pracy, której autorami jest cała trójka. Był to pierwszy algorytm wyszukiwania wzorca w tekście o liniowej złożoności czasowej.

Algorytm KMP

Przykład działania

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.

Aby zilustrować szczegóły algorytmu, rozważmy przebieg algorytmu dla wzorca W= "ABCDABD" i tekstu S= "ABC ABCDAB ABCDABCDABDE". W każdym momencie algorytm znajduje się w stanie opisanym przez dwie liczby całkowite:

• m, numer pozycji w S, od której rozpoczyna się aktualna próba dopasowania wzorca W,
• i, numer pozycji aktualnie rozpatrywanego znaku wzorca W.

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

Algorytm kolejno porównuje znaki wzorca W do znaków tekstu S na odpowiadających pozycjach, przechodząc do kolejnego znaku i zwiększając i, gdy są zgodne. W powyższym przykładzie dla czwartej iteracji S[3] = ' ' nie odpowiada W[3] = 'D'. Ponieważ 'A' nie występuje na pozycjach 1 i 2 w S, z racji częściowego dopasowania wzorca, próby dopasowania wzorca nie powiodą się, jeśli rozpoczniemy od pozycji m < 3. Algorytm przyjmuje zatem m = 3 oraz i = 0.

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

Ta próba dopasowania okazuje się nieskuteczna już przy pierwszym znaku, stąd algorytm przesuwa wzorzec na następną pozycję, ustawiając m = 4 oraz i = 0

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

W tym miejscu skutecznie udaje się dopasować prefiks ciąg "ABCDAB", zwiększając przy tym indeks i do i = 6. Jednak W[6] i S[10] nie są zgodne, więc dopasowanie wzorca nie powiodło się. Następnie algorytm bierze pod uwagę, że przed końcem bieżącego częściowego dopasowania natrafiliśmy na podciąg "AB", który mógłby być początkiem nowego dopasowania. Litery te odpowiadają dwóm znakom przed bieżącą pozycją, których nie musimy ponownie sprawdzać. Algorytm ustawia m = 10 oraz i = 2 i kontynuuje porównywanie od kolejnego znaku. W ten sposób omija nie tylko znaki poprzednio dopasowane w S, lecz również te poprzednio dopasowane z W.

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

Ta próba odnalezienia wzorca natychmiast kończy się porażką, kiedy algorytm trafia na spację. Podobnie jak przy pierwszej próbie, wraca on na początek W i rozpoczyna nową próbę dopasowania od pozycji niedopasowanego znaku w S, ustawiając m = 10 oraz i = 0.

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

Kolejna próba m = 10 również kończy się niepowodzeniem. Algorytm sprawdza następnie m = 11 i i = 0.

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

Algorytm ponownie natrafia na dopasowanie "ABCDAB", lecz kolejny znak, 'C', nie odpowiada ostatniemu znakowi 'D' słowa W. Rozumując jak poprzednio, algorytm ustawia m = 15 oraz i = 2 i kontynuuje poszukiwania.

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

Tym razem udaje się odnaleźć pełne wystąpienie wzorca zaczynające się od pozycji m = 15.

Opis części szukającej algorytmu

Powyższy przykład zawiera wszystkie elementy algorytmu. Chwilowo opiszemy tylko wyszukiwanie – przy założeniu, że dysponujemy tablicą częściowego dopasowania T. Tablica częściowych dopasowań 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 liczbą 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, rób:
       jeżeli W[i] = S[m + i]
           niech i = i + 1
           jeżeli i równe jest długości W, zwróć m
       przeciwnie
           niech m = m + i – T[i]
           jeśli i > 0, niech i = T[i]
   (jeśli dotrzemy tu, to przeszukaliśmy bezskutecznie cały S)
   zwróć długość S

Wydajność części szukającej algorytmu

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 (dopóki), wystarczy, że oszacujemy maksymalną liczbę 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 A⁶ (zaczynającego się na pozycji 0) natrafi na B (na pozycji 6), spróbuje odrzucić pierwsze A i rozpocznie z A⁵ (na pozycji 1), gdzie spróbuje dopasować A⁶. Wciąż jednak natrafia na B, będzie więc sukcesywnie cofał się krok po kroku aż do A¹ (na pozycji 5). Dopiero potem, gdy i ta próba dopasowania zakończy się porażką, przejdzie do następnego znaku. Taka sytuacja wymaga $\mathrm {O} (n)$ operacji, gdy n jest długością wzorca. Gdy pomnożymy n przez k wyjdzie na to, że algorytm KMP 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ń

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 zwiększają 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, jak daleko należy 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 ma już żadnej możliwości wycofywania się), ustawia T[0]= -1.

Przykład algorytmu budowania tabeli T

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	2

Opis i pseudokod algorytmu budowania tabeli T

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ąć)
         przeciwnie
             jeśli j > 0, niech j = T[j]
             (trzeci przypadek: wyczerpuje się zasób kandydatów, Zauważ, że j=0)
             przeciwnie
                 niech T[i] = 0, i = i + 1

Złożoność obliczeniowa algorytmu budowania tabeli T

Złożoność algorytmu budowania tablicy wynosi $\mathrm {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 $\mathrm {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 $\mathrm {O} (n).$

Wydajność algorytmu Knutha-Morrisa-Pratta

Algorytm składa się z dwóch części, z czego pierwsza ma złożoność $O(k),$ a druga $\mathrm {O} (n),$ więc całkowita złożoność algorytmu wynosi $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 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 liczba 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 najlepszego przypadku, gdy wzorzec nie występuje w tekście, oraz $O(n\cdot m)$ dla najgorszego przypadku, gdy wzorzec występuje w tekście.

Zobacz też

• algorytm Boyera i Moore’a
• algorytm Karpa-Rabina

Bibliografia

• 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

• Sprawdź swój program na SPOJ-u [online] [dostęp 2015-02-20]  (pol.).
• An explanation of the algorithm [online] [dostęp 2015-02-20]  (ang.).
• Knuth-Morris-Pratt algorithm [online] [dostęp 2015-02-20]  (ang.).