Algorytm Knutha-Morrisa-Pratta

Algorytm Knutha-Morrisa-Pratta to metoda służąca do wyszukiwania wzorca w tekście.

== Przykład działania ==

Przyjrzyjmy się przykładowi, w którym poszukujemy wzorca ABCDABD w tekście ABC ABCDAB ABCDABCDABDE.

=== Tablica niepowodzeń (prefix table) ===

Pierwszym krokiem algorytmu jest stworzenie tablicy niepowodzeń (ang. failure function), która dla każdego znaku we wzorcu określa najdłuższy prefiks, który jest jednocześnie sufiksem.

Dla wzorca ABCDABD tablica prezentuje się następująco:

=== Działanie na tekście ===

Podczas przeszukiwania tekstu, w przypadku napotkania niezgodności znaków, algorytm korzysta z tablicy niepowodzeń, aby przesunąć wzorzec bez cofania się w tekście, co pozwala na zminimalizowanie liczby porównań.

W rezultacie algorytm przeprowadza wyszukiwanie w czasie O(n + m), gdzie n to długość tekstu, a m to długość wzorca.

=== Pseudokod ===

Poniżej przedstawiono uproszczoną wersję pseudokodu algorytmu:

Algorytm działa na podstawie wykrywania różnic pomiędzy wzorcem a tekstem, gdzie wzorzec wskazuje na dalsze różnice. Kluczowym elementem algorytmu jest wstępne przetworzenie wzorca w celu obliczenia tzw. tablicy przesunięć, co pozwala uniknąć niepotrzebnych porównań i przyspiesza proces wyszukiwania.

Złożoność czasowa algorytmu Knutha-Morrisa-Pratta wynosi O(n + m), gdzie n to długość przeszukiwanego tekstu, a m to długość wzorca. Dzięki temu algorytm jest efektywny, nawet w przypadku długich tekstów, co czyni go przydatnym w systemach wymagających szybkiego przetwarzania danych, takich jak wyszukiwarki internetowe, systemy baz danych czy bioinformatyka.

Algorytm został opracowany w 1977 roku przez Donalda Knutha oraz Vaughana Pratta, a także niezależnie przez Jamesa H. Morrisa. Publikacja, w której przedstawiono algorytm, była wspólnym dziełem tej trójki. 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, że indeksowanie tablic, które przechowują ciągi znaków, zaczyna się od zera. Ten zapis jest zgodny z składnią języka C.

Aby zobrazować działanie algorytmu, rozważmy wzorzec W = „ABCDABD” oraz tekst S = „ABC ABCDAB ABCDABCDABDE”. W każdej chwili algorytm znajduje się w stanie opisanym przez dwie liczby całkowite:

m, numer pozycji w S, od której zaczyna się aktualna próba dopasowania wzorca W,

i, numer pozycji aktualnie rozpatrywanego znaku wzorca W.

Algorytm porównuje znaki wzorca W z znakami tekstu S na odpowiadających im pozycjach, przechodząc do kolejnego znaku i zwiększając i, gdy są one zgodne. W powyższym przykładzie, w czwartej iteracji S[3] = ’ ’ nie odpowiada W[3] = 'D’. Ponieważ 'A’ nie występuje na pozycjach 1 i 2 w S, próby dopasowania wzorca zakończą się niepowodzeniem, jeśli rozpoczniemy od pozycji m < 3. Algorytm zatem ustawia m = 3 oraz i = 0. Ta próba dopasowania kończy się niepowodzeniem już przy pierwszym znaku, dlatego algorytm przesuwa wzorzec na następną pozycję, ustawiając m = 4 oraz i = 0. W tym miejscu udaje się dopasować prefiks "ABCDAB", zwiększając 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 zauważa, że przed końcem bieżącego częściowego dopasowania napotkaliśmy podciąg "AB", który mógłby być początkiem nowego dopasowania. Litery te odpowiadają dwóm znakom przed bieżącą pozycją, które 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 wcześniej dopasowane w S, lecz także te z W. Gdy algorytm dociera do spacji, próba odnalezienia wzorca natychmiast się kończy. Jak w 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. Kolejna próba m = 10 również kończy się niepowodzeniem. Algorytm sprawdza następnie m = 11 i i = 0. Ponownie odnajduje dopasowanie "ABCDAB", jednak kolejny znak, 'C', nie odpowiada ostatniemu znakowi 'D' wzorca W. Podobnie jak wcześniej, algorytm ustawia m = 15 oraz i = 2 i kontynuuje poszukiwania.

1 2

m: 01234567890123456789012

S: ABC ABCDAB ABCDABCDABDE

W: ABCDABD

i: 0123456

Tym razem algorytm skutecznie odnajduje 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. Na chwilę skupimy się wyłącznie na wyszukiwaniu – zakładając, że dysponujemy tablicą częściowego dopasowania T. Tablica ta wskazuje, gdzie należy szukać początku nowego dopasowania, gdy próba odnalezienia wzorca na obecnej pozycji zakończy się niepowodzeniem. Tablicę T wykorzystujemy w następujący sposób: jeżeli mamy dopasowanie zaczynające się w S[m], 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] to liczba kroków wstecz, które musimy wykonać, gdy brak jest dopasowania).

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 również zauważyć, że skoro po niepowodzeniu na pozycji m + i kolejne możliwe dopasowanie rozpocznie się od indeksu m + i – T[i], kontynuujemy z W[T[i]].

Poniżej znajduje się opis części szukającej algorytmu KMP w formie pseudokodu.

algorytm kmp_search:

wejście:

tablica znaków, S (przeszukiwany tekst)

tablica znaków, W (szukane słowo)

wyjście:

liczba całkowita (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żeli dotrzemy tu, to przeszukaliśmy bezskutecznie cały S)

zwróć długość S

== Wydajność części szukającej algorytmu ==

Zakładając, że tablica T została już obliczona, zamortyzowany koszt algorytmu Knutha-Morrisa-Pratta wynosi

(

)

{\displaystyle O(k),}

gdzie k jest długością tekstu S. Ponieważ większość obliczeń odbywa się w pętli (dopóki), wystarczy oszacować maksymalną liczbę jej przebiegów. Rozważmy najpierw najgorszy przypadek:

Gdy dla danych

S=AAAAAABAC….

W=AAAAAA

algorytm po znalezieniu częściowego dopasowania A6 (zaczynającego się na pozycji 0) napotka na B (na pozycji 6), spróbuje odrzucić pierwsze A i rozpocznie z A5 (na pozycji 1), gdzie spróbuje dopasować A6. Wciąż napotyka na B, więc będzie sukcesywnie cofał się krok po kroku aż do A1 (na pozycji 5). Dopiero po tej próbie, gdy i ta próba dopasowania również zakończy się niepowodzeniem, przejdzie do następnego znaku. Taka sytuacja wymaga

(

)

{\displaystyle \mathrm {O} (n)}

operacji, gdzie 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. Należy jednak zauważyć, że algorytm, aby móc cofnąć się o jedno miejsce, musi wcześniej przeczytać przynajmniej jeden znak, dlatego sytuacje takie mogą wystąpić jedynie w k/m przypadkach. Z tej prostej obserwacji wynika, że zamortyzowany koszt działania algorytmu wynosi około 2*k, co mieści się w

(

)

{\displaystyle O(k).}

== Tablica częściowych dopasowań ==

Tablica ta ma na celu umożliwienie algorytmowi unikania niedopasowywania któregokolwiek znaku z S więcej niż raz. Kluczową obserwacją dotyczącą liniowego wyszukiwania, która to umożliwia, jest to, że mając porównany pewien segment głównego ciągu znaków z początkowym fragmentem wzorca, dokładnie wiemy, w których miejscach mogłoby się zacząć nowe potencjalne dopasowanie przed bieżącą pozycją. Innymi słowy, występuje tutaj „wstępne przeszukiwanie” samego wzorca i zebranie zestawu wszelkich możliwych pozycji do powrotu, które pomijają błędne wybory i zwiększają 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, który wskazuje (ale nie zawiera) tę pozycję, inny niż całe segmenty zaczynające się w W[0], które nie dały się dopasować; to definiuje, jak daleko należy się cofnąć w poszukiwaniu 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. Gdy występuje rozbieżność na samym początku wzorca, to jest to szczególny przypadek (nie ma już możliwości wycofywania się), ustawiamy T[0]= -1.

=== Przykład algorytmu budowania tabeli T ===

Rozważmy wzorzec W = „ABCDABD”. Zobaczymy, że algorytm działa w dużej mierze zgodnie z głównym schematem wyszukiwania i jest z podobnych powodów wydajny. Ustawiamy T[0] = -1. Aby wyznaczyć T[1], musimy znaleźć sufiks „A”, który jest także prefiksem W. Jednak nie ma właściwych sufiksów „A”, więc ustawiamy T[1] = 0. Podobnie T[2] = 0. Kontynuując dla T[3], możemy szybciej sprawdzić wszystkie sufiksy: 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 również jest właściwym prefiksem samego wzorca W, a zarazem samego siebie, i kończy się w W[1], co nie może wystąpić. Zatem nie musimy nawet rozważać wzorców o długości 2 i podobnie jak w poprzednim przypadku odpada jedynie ten o długości 1, więc T[3] = 0.

Przechodząc do następnego znaku W[4], czyli 'A’, ten sam sposób rozumowania pokazuje, że najdłuższy wzorzec, który musimy rozważyć, ma długość 1 i mimo że w tym przypadku 'A’ jest odpowiednie, pamiętajmy, że szukamy segmentów kończących się przed bieżącym znakiem, zatem również T[4] = 0.

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

Na koniec zauważamy, że następny znak w kolejnym segmencie, rozpoczynającym się w W[4] = 'A’, byłby 'B’, i rzeczywiście jest to także W[5]. Dalej, ten sam argument co powyżej uzasadnia, że nie musimy zaglądać poza W[4], aby odnaleźć segment dla W[6], więc to jest to, i otrzymujemy T[6] = 2.

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

=== Opis i pseudokod algorytmu budowania tabeli T ===

Powyższy przykład ilustruje ogólną technikę zapełniania tabeli przy minimalnym wysiłku. Kluczem 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. Niemniej jednak metoda, która jest poprawna w dalszej części łańcucha, może powodować błędne generowanie ciągów znaków na początku łańcucha. Można to naprawić poprzez wprowadzenie prostego kodu inicjującego.

algorytm kmp_table:

Dane wejściowe:

tablica znaków, W (słowo do analizy)

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 w tablicy T)

liczba całkowita, j = 0

(indeks tablicy W, w której ma być umieszczona kolejna litera szukanego ciągu znaków)

(pierwsze 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

(

)

{\displaystyle \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

(

)

{\displaystyle \mathrm {O} (n),}

jednocześnie badając wartości i oraz i – j. W pierwszej pętli wartość różnicy i – j jest zachowywana, ponieważ 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, więc różnica i – j wzrasta. 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, oznacza to, ż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, ponieważ i – 1 zaczyna się od 1. Tak więc złożoność algorytmu wynosi

(

)

{\displaystyle \mathrm {O} (n).}

== Wydajność algorytmu Knutha-Morrisa-Pratta ==

Algorytm składa się z dwóch części, z czego pierwsza ma złożoność

(

)

{\displaystyle O(k),}

a druga

(

)

{\displaystyle O(n),}

więc całkowita złożoność algorytmu wynosi

(

)

{\displaystyle O(k+n).}

Jest jasne, że w analizowanym przykładzie algorytm zyska największą przewagę nad algorytmem naiwnym, gdy może jednocześnie pomijać większą część znaków tekstu. Oznacza to, że im mniej musi się cofać, tym szybciej przebiega wyszukiwanie, co jest odzwierciedlone przez obecność zer w tabeli T. Na przykład wzorzec taki jak W = „ABCDEFG” jest korzystnym przypadkiem dla tego algorytmu, ponieważ nie zawiera powtórzeń swojego początku, więc jego tabela T składa się z samych zer, z -1 jedynie na początku. Dla kontrastu, wzorzec W = „AAAAAA” będzie działał gorzej, ponieważ jego tabela ma postać:

Jest to najgorszy możliwy rodzaj wzorca dla T, i może być 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” rośnie. Chociaż dla tego tekstu metoda tablicowa jest szybka (nie występuje tutaj cofanie), przebiega tylko raz dla danego wzorca W, podczas gdy procedura poszukiwania może przebiegać go wiele razy. Jeżeli za każdym razem tekst S będzie przeszukiwany pod kątem wzorca, 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. Niemniej jednak algorytm KMP gwarantuje, że poszukiwanie będzie przeprowadzone w liniowym czasie, zarówno w najlepszym, jak i najgorszym przypadku, podczas gdy algorytm Boyera-Moore’a osiąga

(

)

{\displaystyle O(n+m)}

dla najlepszego przypadku, gdy wzorzec nie występuje w tekście, oraz

(

⋅

)

{\displaystyle 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.

== Przypisy ==

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

Szybkie wyszukiwanie wzorca algorytmem Knutha-Morrisa-Pratta [online] [dostęp 2024-11-16] (pol.).