Algorytm Knutha-Morrisa-Pratta
Z Wikipedii
Algorytm Knutha-Morrisa-Pratta to algorytm przeszukiwania łańcuchów, który odnajduje wystąpienia "słowa" W wewnątrz głównego "łańcucha tekstowego" S angażując prostą obserwacje, polegającą na tym, że w przypadku wystąpienia niezgodności, słowo samo w sobie zawiera wystarczającą ilość informacji, by określić gdzie powinno zacząć się kolejne dopasowanie, zatem pomijając ponowną analizę uprzednio dopasowanych znaków.
Algorytm został wynaleziony przez Knuttha i Pratta i niezależnie przez J. H. Morrisa w 1977, ale wtedy opublikowali go wspólnie.
W tym artykule będziemy używać tablic indeksowanych od zera do przechowywania naszych łańcuchów znaków, zatem 'C' w W (pokazane poniżej) będzie zapisywane jako W[2]. Ogółem, zapis spełnia reguły składni C, która nie jest zbyt nielogiczna.
Spis treści |
[edytuj] Algorytm KMP
[edytuj] Opracowany przykład algorytmu szukającego
By uzasadnić szczegóły techniczne, przeanalizujemy (względnie sztuczny) przebieg algorytmu. W dowolnej chwili, algorytm jest w stanie opisanym dwiema zmiennymi m oraz i, które oznaczają odpowiednio pozycję wewnątrz S, który jest początkiem przewidywanego dopasowania w W, oraz indeksu w W oznaczającego aktualnie rozpatrywany znak. Na początku algorytmu określone są jako:
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ę po nich kolejno, jeśli pasują. Niemniej jednak, w czwartym kroku, dostajemy spację w S[3], a W[3]='D', niezgodność. Zamiast rozpoczynać poszukiwanie od S[1] zapamiętujemy, że żadne 'A' nie wystąpiło między pozycją 0 i 3, z wyjątkiem 0; dlatego sprawdziwszy uprzednio wszystkie te znaki wiemy, że nie ma szans na znalezienie początku dopasowania, jeśli sprawdzimy je ponownie. Zatem przesuwamy się do kolejnego znaku ustawiając m=4 oraz i=0.
m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456
Szybko otrzymujemy niemal kompletne dopasowanie "ABCDAB", gdy na W[6] (S[10]) znów mamy niezgodność. Niemniej jednak przed końcem bieżącego dopasowania cząstkowego, przeszliśmy przez "AB", które mogłoby być początkiem nowego dopasowania, więc musimy wziąć je pod uwagę. Jak już wiemy znaki 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. Zatem omijamy nie tylko poprzednio dopasowane znaki w S, ale również poprzednio dopasowane znaki W.
m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456
Szukanie zawodzi natychmiastowo, jednakże, jako że wzorzec wciąż nie zawiera spacji, to tak jak w pierwszym przebiegu, wracamy na początek W i zaczynamy szukanie od kolejnego znaku S: m = 11; 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, by rozpocząć na dwuznakowym łańcuchu "AB" prowadzącym do bieżącej pozycji, ustawiamy i=2, i kontynuujemy dopasowywanie od bieżącej pozycji.
m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456
Tym razem jesteśmy w stanie skompletować dopasowanie, którego pierwszy znak to S[15].
[edytuj] Opis i pseudokod algorytmu wyszukiwania
Powyższy przykład zawiera wszystkie elementy algorytmu. Chwilowo zakładamy istnienie tabeli "cząstkowego dopasowania" T, opisanej niżej, która wskazuje gdzie musimy szukać początku nowego dopasowania w przypadku, gdy bieżące zakończy się brakiem dopasowania. Wpisy w T są tak, że jeżeli mamy zaczynające się w S[m] dopasowanie, które zawiedzie gdy porównamy S[m + i] do 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). Wynikają z tego dwie kwestie: po pierwsze T[0] = -1, które wskazuje, że jeśli W[0] nie zostanie dopasowane, nie możemy się cofnąć i musimy po prostu sprawdzić następny znak, a po drugie, pomimo, że kolejne możliwe dopasowanie rozpocznie się w indeksie m + i - T[i], jak w powyższym przykładzie, nie musimy po tym właściwie sprawdzać żadnego znaku w T[i], więc kontynuujemy szukanie od W[T[i]]. Poniżej znajduje się przykładowy pseudokod algorytmu szukania KMP:
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 gdziekolwiek)
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, let i = T[i]
(jeśli dotrzemy tu, tzn., że przeszukaliśmy bezskutecznie cały S)
zwróć długość S
[edytuj] Wydajność algorytmu szukania
Zakładając wcześniejsze istnienie tabeli T, wyszukiwanie Knutha-Morrisa-Pratta ma złożoność O(k), gdzie k jest długością S. Z wyjątkiem stałych kosztów poniesionych przy wchodzeniu i opuszczaniu funkcji, całość obliczeń jest wykonywana w pętli while, obliczymy granicę ilości iteracji tej pętli; by to zrobić, dokonamy kluczowej obserwacji charakterystyki T. Z definicji jest konstruowana tak, że gdy dopasowanie, które rozpoczęło się na S[m] nie powiedzie się podczas porównywania S[m + i] do W[i], wtedy kolejne możliwie dopasowanie musi rozpocząć się w S[m + (i - T[i]]. W szczególności, następne możliwe dopasowanie musi mieć miejsce w wyższym niż m indeksie, więc T[i] < i.
Posługując się tym faktem, pokażemy, że pętla może wykonać się co najwyżej 2k razy. Dla każdej iteracji wykonywana jest jedna z dwóch gałęzi pętli. Pierwsza gałąź niezmiennie zwiększa i oraz nie zmienia m, więc indeks m + i obecnie analizowanego znaku w S jest zwiększany. Druga gałąź dodaje i - T[i] do m, i jak widzieliśmy, jest to zawsze liczba dodatnia. Zatem położenie m początku bieżącego potencjalnego dopasowania jest zwiększane. Teraz, pętla kończy się gdy m + i = k, zatem każda gałąź pętli może być wykonana co najwyżej k razy jako, że one odpowiednio zwiększają albo m + i lub m, oraz m ≤ m + i : jeżeli m = k, wtedy z pewnością m + i ≥ k, więc jak się zwiększa góra o jeden, musieliśmy otrzymać m + i = k, w którymś wcześniejszym miejscu, a zatem którykolwiek sposób powoduje zakończenie.
Zatem pętla wykonuje się co najwyżej 2k razy, pokazując że złożoność czasowa algorytmu poszukiwania to O(k).
[edytuj] Częściowe porównywanie tablic, znane też jako "metoda niepowodzeń"
Celem tej tabeli jest pozwolenie algorytmowi na nie przypasowanie żadnego znaku z S więcej niż raz. Kluczowa obserwacja natury liniowego poszukiwania, która pozwala, by to się działo, 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.
[edytuj] Opracowany przykład algorytmu budowania tabel
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, przypomnij, ż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 by zawierał 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 w 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 jak powyższej 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 |
[edytuj] Opis i pseudokod algorytmu budowania tabel
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
[edytuj] Złożoność obliczeniowa algorytmu opartego na tablicach jednowymiarowych
Złożoność algorytmu opartego na tablicy wynosi O(n), gdzie jest długością tablicy W. Poza czynnościami inicjalizacyjnymi, cała praca jest wykonywana w pętli. To w zupełności pokazuje, ż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ść i - j jest zachowana, a i oraz j są jednocześnie zwiększane, 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. Dopóki 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).
[edytuj] Wydajność algorytmu Knutha-Morrisa-Pratta
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 na raz 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 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.
[edytuj] Linki zewnętrzne
- Demonstracja działania algorytmu KMP (pl)
- An explanation of the algorithm (en)
- Knuth-Morris-Pratt algorithm (en)
[edytuj] 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 0262032937.
