Algorytm Knuth–Morris–Pratt


W jednym z poprzednich wpisów pokazałem naiwną metodę wyszukiwania wzorca w tekście. Teraz zastanówmy się, jaki jest problem z podejściem naiwnym oraz jak można by je poprawić.

Wizualizacja problemów z metodą naiwną

naiwne.prop

W pierwszym kroku znaleźliśmy trzy kolejne pasujące znaki i dopiero na pozycji czwartej znajdowało się pierwsze niedopasowanie. Wiemy, że nasze trzy pierwsze znaki są różne, a ponieważ pasowały do trzech pierwszych znaków tekstu przeszukiwanego, to z tego faktu możemy wyprowadzić wniosek, że dla przesunięcia równego jeden oraz dwa znaki nie uda nam się dopasować wzorca. Pomimo takiej obserwacji metoda naiwna stara się dopasować wzorzec (krok 2 i 3).

W tym wpisie przedstawię, jak możemy wstępnie przetworzyć wzorzec, tak aby poznać jego strukturę (samo podobieństwo) i dzięki temu być w stanie w pewnych sytuacjach zwiększyć przesunięcie o więcej niż jedno pole. Pokażę algorytm, który wykorzysta cechy wzorca i będzie zdolny do przejścia z kroku 1 bezpośrednio do kroku 5.

img2

Oczywiście jeśli we wzorcu znajdują się powtórzenia (prefikso-sufiks), to dopasowujemy wzorzec zgodnie z najdłuższym możliwym prefikso-sufiksem.

Image3

 

Wizualizacja oraz właściwości prefikso-sufiksu

Poniższy obrazek pokazuje prefikso-sufiksy dla różnych podciągów wzorca.

Image4

Aby efektywnie wyliczyć prefikso-sufiks przy pomocy technik programowania dynamicznego, powinniśmy znać dwie jego właściwości:

  • rozszerzalność prefikso-sufiksu,
  • redukcja prefikso-sufiksu.

Rozszerzalność prefikso-sufiksu

Jeśli do łańcucha tekstowego S o długości N, który posiada prefikso-sufiks o długości K, dodamy kolejny znak, to jeśli nowy znak będzie identyczny ze znakiem S[k]. Wówczas najdłuższy prefikso-sufiks nowego łańcucha tekstowego będzie miał długość K+1.

Image5

Redukcja prefikso-sufiksu

Jeśli łańcuch S posiada prefikso-sufiks PS1 oraz PS1, posiada swój własny prefikso-sufiks PS2. Wówczas PS2 jest również prefikso-sufiksem łańcucha S.

Image6

Jeśli PS1 jest maksymalnym prefikso-sufiksem S, oraz PS2 jest maksymalnym prefikso-sufiksem PS1, to wówczas nie istnieje żaden prefikso-sufiks S dłuższy niż PS2 inny niż PS1.

Implementacja algorytmu Morrisa-Pratta

Przekształcenie wzorca

Stosujemy tu programowanie dynamiczne. Dla każdego prefikso-sufiksu sprawdzamy prefikso-sufiks o jeden mniejszy i próbujemy go rozszerzyć. Jeśli rozszerzenie poprzedniego prefikso-sufiksu się nie udało, to szukamy kandydata wśród kolejnych zagnieżdżonych prefikso-sufiksów.

Przykładowe wyniki przekształcenia wzorca wg algorytmu Morrisa-Pratta

Wyszukiwanie wzorca wg algorytmu Morrisa-Pratta

Jeśli podczas próby dopasowania wzorca natrafimy na niedopasowanie, to możemy przesunąć wzorzec nie o jedno pola jak w algorytmie naiwnym, ale o całą długość dopasowanej cześć wzorca minus długość najdłuższego prefikso-sufiksu. Dzięki temu usprawnieniu pomijamy pewne niepotrzebne porównania.

Algorytm Knuth–Morris–Pratt

Algorytm Knuth-Morris-Pratt

Sam algorytm Morris-Pratt wprowadza znaczne zwiększenie wydajności w stosunku do podejścia naiwnego, jednak Donald Knuth odkrył, jak można jeszcze dalej ulepszyć ten algorytm – tak powstał Algorytm Knuth-Morris-Pratt, nazywany również algorytmem KMP.  Samo wyszukiwanie jest identyczne jak w metodzie MP, różnica jest tylko w sposobie przetworzenia wzorca. A Metodzie KMP wyznaczamy tablice KMPNext zamiast MPNext.

Ulepszenie wprowadzone przez Donalda Knutha pozwalało zmniejszyć ilość przypadków, kiedy po przesunięciu nieudanego dopasowania częściowego mieliśmy różnicę znaków już przy pierwszym nowym porównaniu.

Rozważmy następujący przypadek:

Algorytm Knuth–Morris–Pratt

Zgodnie z podejściem MP przesuwamy wzorzec i natychmiast natrafiamy na niedopasowanie za pierwszym porównaniem. W tym miejscu algorytm KMP wprowadza ulepszenie – korzysta on z faktu, że to niedopasowanie możemy przewidzieć z samej struktury wzorca.  Po wystąpieniu ciągu „AB” kolejny znak „C” jest taki sam jak trzeci znak w ciągu „C”, więc za każdym razem, gdy znajdziemy niedopasowanie na pozycji siódmej, możemy przesunąć wzorzec o całe siedem pozycji, a nie tylko o pięć jak w algorytmie MP.

Algorytm Knuth–Morris–Pratt

Algorytm obliczania tablicy KMPNext sprawdza, czy następny znak po sufiksie jest różny od znaku następującego po prefiksie. Jeśli znaki są różne, to wstawiamy do tabeli -1, co optymalizuje nam algorytm.

Porównanie tablicy KMPNext  oraz MPNext

Implementacja Algorytmu KMP

Wyszukiwanie wzorca jest zaimplementowane identycznie jak w przypadku algorytmu MP, jedynie korzysta z innej tablicy przesunięć.

Samo wyznaczanie tablicy przesunięć różni się tylko jednym dodatkowym warunkiem w stosunku do algorytmu MP.

Dalsza lektura

Dodaj komentarz

Twój adres email nie zostanie opublikowany.