Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2021 mgr Jerzy Wałaszek
I LO w Tarnowie

Szybkie wyszukiwanie wzorca algorytmem Knutha-Morrisa-Pratta

SPIS TREŚCI
Tematy pomocnicze

Problem

W łańcuchu s  należy wyznaczyć wszystkie wystąpienia wzorca p.

Rozwiązanie

Profesor Donald Knuth przeanalizował dokładnie algorytm Morrisa-Pratta i zauważył, iż można go jeszcze ulepszyć. Ulepszenie to polega na nieco innym sposobie wyznaczania tablicy Π w stosunku do algorytmu MP. Otóż oryginalnie tablica ta zawiera maksymalne szerokości prefikso-sufiksów kolejnych prefiksów wzorca. Załóżmy, iż w trakcie porównania dochodzi do niezgodności na pozycji znaku A w łańcuchu przeszukiwanym ze znakiem B we wzorcu (A, B i C oznaczają nie konkretne literki, ale różne znaki łańcucha i wzorca) :

obrazek

W celu uniknięcia po przesunięciu okna wzorca natychmiastowej niezgodności musimy dodatkowo zażądać, aby znak C leżący tuż za prefikso-sufiksem prefiksu we wzorcu był różny od znaku B, który poprzednio wywołał niezgodność. Algorytm MP nie sprawdzał tej cechy.

Tablicę szerokości prefikso-sufiksów uwzględniającą tę cechę będziemy nazywali tablicą KMPNext. Kolejne jej elementy są maksymalnymi szerokościami prefikso-sufiksów prefiksu wzorca. Jeśli dany prefikso-sufiks nie istnieje (nawet prefikso-sufiks pusty ), to element tablicy ma wartość -1 ( w poprzedniej wersji algorytmu wartownik występował tylko w elemencie o indeksie 0 ).

Przykład:

Wyznaczymy tablicę KMPNext dla wzorca ABACABAB – identyczny wzorzec jak w rozdziale o tworzeniu tablicy Π.

Lp. Tworzona tablica Next Opis
1.
s        :   A B A C A B A
i        : 0 1 2 3 4 5 6 7 8
KMPNext[]:-1 ? ? ? ? ? ? ? ?
Element KMPNext [ 0 ] jest zawsze równy -1. Pełni on rolę wartownika, dzięki któremu upraszcza się algorytm wyznaczania kolejnych elementów tablicy.
2.
s        :   A B A C A B A B
i        : 0 1 2 3 4 5 6 7 8
KMPNext[]:-1 0 ? ? ? ? ? ? ?
Prefiks jednoznakowy A posiada zawsze prefikso-sufiks pusty. Dodatkowo znak A leżący tuż za prefikso-sufiksem oraz znak B leżący za prefiksem są różne. Zatem istnieje prefikso-sufiks pusty o szerokości 0 i to wpisujemy do tablicy.
3.
s        :   A B A C A B A B 
i        : 0 1 2 3 4 5 6 7 8
KMPNext[]:-1 0-1 ? ? ? ? ? ?
Prefikso-sufiks prefiksu dwuznakowego AB ma szerokość 0. Jednakże znak A leżący tuż za prefikso-sufiksem pustym oraz znak A leżący tuż za prefiksem jest tym samym znakiem. Skoro tak, to prefikso-sufiks nie istnieje - wpisujemy -1.
4.
s        :   A B A C A B A B
i        : 0 1 2 3 4 5 6 7 8
KMPNext[]:-1 0-1 1 ? ? ? ? ?
Prefikso-sufiks prefiksu ABA ma szerokość 1 (obejmuje pierwszą i ostatnią literkę A ). Znak B leżący tuż za prefikso-sufiksem oraz znak C leżący za prefiksem są różne. Zatem do tablicy wprowadzamy 1.
5.
s        :   A B A C A B A B  
i        : 0 1 2 3 4 5 6 7 8
KMPNext[]:-1 0-1 1-1 ? ? ? ?
Prefiks ABAC ma prefikso-sufiks pusty o szerokości 0. Jednakże za prefikso-sufiksem i za prefiksem występuje ten sam znak. Zatem w tablicy umieszczamy -1.
6.
s        :   A B A C A B A B
i        : 0 1 2 3 4 5 6 7 8
KMPNext[]:-1 0-1 1-1 0 ? ? ?
Prefiks ABACA posiada prefikso-sufiks o szerokości 1 (pierwsza i ostatnia litera A ). Jednakże za prefikso-sufiksem i prefiksem występuje ten sam znak B. Z tablicy odczytujemy szerokość następnego prefikso-sufiksu - KMPNext [ 1 ] = 0. Jest to prefikso-sufiks pusty. W tym przypadku za prefikso-sufiksem wystąpi litera A, która różni się od litery B za prefiksem. Jest to zatem poszukiwany prefikso-sufiks i szerokość 0 wpisujemy do tablicy.
7.
s        :   A B A C A B A B
i        : 0 1 2 3 4 5 6 7 8
KMPNext[]:-1 0-1 1-1 0-1 ? ?
Prefiks ABACAB posiada prefikso-sufiks o szerokości 2 (AB z przodu i z tyłu ). Jednakże za prefikso-sufiksem i za prefiksem występuje ten sam znak A. Odczytujemy z tablicy szerokość następnego prefikso-sufiksu KMPNext [ 2 ] = -1. Prefikso-sufiks nie istnieje, zatem w tablicy umieszczamy -1.
8.
s        :   A B A C A B A B
i        : 0 1 2 3 4 5 6 7 8
KMPNext[]:-1 0-1 1-1 0-1 3 ?
Prefiks ABACABA posiada prefikso-sufiks o szerokości 3 ( ABA ). Znak C za prefikso-sufiksem jest różny od znaku B za prefiksem, zatem w tablicy umieszczamy 3.
9.
s        :   A B A C A B A B 
i        : 0 1 2 3 4 5 6 7 8 
KMPNext[]:-1 0-1 1-1 0-1 3 2 
Cały wzorzec ABACABAB posiada prefikso-sufiks o szerokości 2 ( AB ). Ponieważ nie ma już możliwości sprawdzenia znaku A leżącego tuż za prefikso-sufiksem ze znakiem leżącym za wzorcem, to w tablicy umieszczamy 2. Tablica KMPNext jest gotowa.

Porównajmy tablicę  Π z tablicą KMPNext:

wzorzec   A B A C A B A B
indeks 0 1 2 3 4 5 6 7 8
Π -1 0 0 1 0 1 2 3 2
KMPNext -1 0 -1 1 -1 0 -1 3 2

Algorytm KMP wyszukiwania wzorca wykorzystujący tablicę KMPNext jest identyczny z algorytmem MP wykorzystującym tablicę Π. W algorytmie KMP zastępujemy jedynie odwołania do tablicy Π odwołaniami do tablicy KMPNext [ ], która pozwala bardziej efektywnie wyszukiwać wystąpienia wzorców, ponieważ pomijane są puste przebiegi. Klasa złożoności obliczeniowej jest równa O ( m  + n  ), gdzie m  jest długością wzorca p, a n  jest długością przeszukiwanego łańcucha s.

Algorytm Knutha-Morrisa-Pratta tworzenia tablicy KMPNext

Wejście:

s  –  łańcuch znakowy.

Wyjście:

Tablica KMPNext [ ] z długościami prefikso-sufiksów kolejnych prefiksów łańcucha s. Elementy KMPNext  ∈ C.

Zmienne pomocnicze:

KMPNext  –  tablica długości prefikso-sufiksów kolejnych prefiksów łańcucha s, KMPNext  ∈ C.
b  – długość prefikso-sufiksu, b  ∈ C.
i  – indeks, i  ∈ N.

Lista kroków:

K01: KMPNext [ 0 ] ← -1 na początku tablicy KMPNext wstawiamy wartownika
K02: b  ← -1 początkowo długość prefikso-sufiksu ustawiamy na -1
K03: Dla i  = 1, 2, ..., | s |:
wykonuj kroki K04...K06
wyznaczamy długości prefikso-sufiksów dla prefiksów łańcucha s
K04:     Dopóki ( b  > -1 ) obrazek ( s [ b  ] ≠ s [ i  - 1 ] ),
    wykonuj b  ← KMPNext [ b  ]
w pętli K04 szukamy prefikso-sufiksu b prefiksu wzorca, który da się rozszerzyć. Z pętli wychodzimy, jeśli natrafimy na wartownika lub prefikso-sufiks jest rozszerzalny
K05:     b  ← b  + 1 rozszerzamy prefikso-sufiks
K06:     Jeśli i  = |s| obrazek s [ i  ] ≠ s [ b  ],
    to KMPNext [ i  ] ← b,
    inaczej KMPNext [ i  ] ← KMPNext [ b  ]
Jeśli następny znak wzorca różni się od znaku tuż za prefikso-sufiksem,
to w tablicy KMPNext umieszczamy szerokość prefikso-sufiksu.
Inaczej w  KMPNext umieszczamy zredukowaną szerokość prefikso-sufiksu
K07: Zakończ  

Algorytm Knutha-Morrisa-Pratta wyszukiwania wzorca

Wejście:

s  –  łańcuch znakowy
p  – poszukiwany wzorzec

Wyjście:

Kolejne pozycje wystąpień wzorca w łańcuchu. Wartość -1 nie wskazuje żadnej pozycji wzorca i oznacza, iż wzorzec nie pojawia się w przeszukiwanym łańcuchu.

Zmienne pomocnicze:

pp  – zawiera wyznaczane pozycje wzorca, pp  ∈ C
i  –  pozycja porównywanego znaku w łańcuchu tekstowym s, i  ∈ N, 0 ≤ i  ≤ | s |
b  – długość prefiksu wzorca p  pasującego do prefiksu okna wzorca w łańcuchu s, b  ∈ C, 0 ≤ b  ≤ | p |
KMPNext  – tablica o indeksach od 0 do |p|, przechowująca długości maksymalnych prefikso-sufiksów kolejnych prefiksów wzorca p, KMPNext  ∈ C

Lista kroków:

K01: Wyznacz tablicę KMPNext wyznaczamy tablicę maksymalnych prefikso-sufiksów algorytmem KMP
K02: pp  ← -1 wstępna pozycja wzorca ustawiona na -1
K03: b  ← 0 wstępną długość prefikso-sufiksu ustawiamy na 0
K04: Dla i  = 0, 1, ... | s | - 1:
wykonuj kroki K05...K10
pętla wyznacza znaki łańcucha do porównania ze znakami wzorca
K05:     Dopóki ( b  > -1 ) obrazek ( p [ b  ] ≠ s [ i  ] ),
    wykonuj b  ← KMPNext [ b  ]
Szukamy we wzorcu p rozszerzalnego prefiksu pasującego do prefiksu okna wzorca. Pętlę K05 przerywamy, jeśli znajdziemy rozszerzalny prefiks lub napotkamy wartownika -1
K06:     b  ← b  + 1 Rozszerzamy prefiks o 1 znak. Jeśli prefiks był wartownikiem, to otrzymuje wartość 0.
K07:     Jeśli b  < | p |,
    to następny obieg pętli K04
Jeśli prefiks nie obejmuje całego wzorca, to kontynuujemy pętlę K04, czyli porównujemy znak p [ b ] z kolejnym znakiem łańcucha s.
K08:     pp  ← i  - b  + 1 wyznaczamy pozycję wzorca p w łańcuchu s
K09:     Pisz pp wyprowadzamy tę pozycję
K10:     b  ← KMPNext [ b  ] redukujemy b do długości prefikso-sufiksu wzorca
K11: Jeśli pp  = -1,
to pisz -1
jeśli wzorzec p nie występuje w s, wyprowadzamy -1
K12: Zakończ  

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program generuje 79 znakowy łańcuch zbudowany z pseudolosowych kombinacji liter A i B oraz 5 znakowy wzorzec wg tego samego schematu. Następnie program wyznacza tablicę długości maksymalnych prefikso-sufiksów kolejnych prefiksów wzorca i wykorzystuje ją do znalezienia wszystkich wystąpień wzorca w łańcuchu.
Pascal
// Wyszukiwanie wzorca algorytmem KMP
// Data:  4.06.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

program prg;

const
  N = 79;  // długość łańcucha s
  M =  5;  // długość wzorca p

var
  s, p : ansistring;
  KMPNext : array [ 0..M ] of integer;
  i, b, pp : integer;

begin
  randomize;

  // generujemy łańcuch s

  s := '';
  for i := 1 to N do s := s + chr ( 65 + random ( 2 ) );

  // generujemy wzorzec

  p := '';
  for i := 1 to M do p := p + chr ( 65 + random ( 2 ) );

  // dla wzorca obliczamy tablicę KMPNext [ ] 

  KMPNext [ 0 ] := -1;
  b := -1;
  for i := 1 to M do
  begin
    while( b > -1 ) and ( p [ b + 1 ] <> p [ i ] ) do b := KMPNext [ b ];
    inc ( b );
    if( i = M ) or ( p [ i + 1 ] <> p [ b + 1 ] ) then KMPNext [ i ] := b
    else KMPNext [ i ] := KMPNext [ b ];
  end;

  // wypisujemy wzorzec p

  writeln ( p );

  // wypisujemy łańcuch s

  writeln ( s );

  // poszukujemy pozycji wzorca w łańcuchu

  pp := 0; b := 0;
  for i := 1 to N do
  begin
    while( b > -1 ) and ( p [ b + 1 ] <> s [ i ] ) do b := KMPNext [ b ];
    inc ( b );
    if b = M then
    begin
      while pp < i - b do
      begin
        write ( ' ' ); inc ( pp );
      end;
      write ( '^' ); inc ( pp );
      b := KMPNext [ b ];
    end
  end;
  writeln;
end.
C++
// Wyszukiwanie wzorca algorytmem KMP
// Data:  4.06.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------

#include <iostream>
#include <string>
#include <cstdlib>
#include <time.h>

using namespace std;

const int N = 79;  // długość łańcucha s
const int M =  5;  // długość wzorca p

int main( )
{
  string s, p;
  int KMPNext [ M + 1 ], i, b, pp;

  srand ( ( unsigned )time ( NULL ) );

  // generujemy łańcuch s

  s = "";
  for( i = 0; i < N; i++ ) s += 65 + rand( ) % 2;

  // generujemy wzorzec

  p = "";
  for( i = 0; i < M; i++ ) p += 65 + rand( ) % 2;

  // dla wzorca obliczamy tablicę Next [ ] 

  KMPNext [ 0 ] = b = -1;
  for( i = 1; i <= M; i++ )
  {
    while( ( b > -1 ) && ( p [ b ] != p [ i - 1 ] ) ) b = KMPNext [ b ];
    ++b;
    if( ( i == M ) || ( p [ i ] != p [ b ] ) ) KMPNext [ i ] = b;
    else KMPNext [ i ] = KMPNext [ b ];
  }

  // wypisujemy wzorzec

  cout << p << endl;

  // wypisujemy łańcuch s

  cout << s << endl;

  // poszukujemy pozycji wzorca w łańcuchu

  pp = b = 0;
  for( i = 0; i < N; i++ )
  {
    while( ( b > -1 ) && ( p [ b ] != s [ i ] ) ) b = KMPNext [ b ];
    if( ++b == M )
    {
      while( pp < i - b + 1 )
      {
        cout << " "; pp++;
      }
      cout << "^"; pp++;
      b = KMPNext [ b ];
    }
  }
  cout << endl;
  return 0;
}
Basic
' Wyszukiwanie wzorca algorytmem KMP
' Data:  4.06.2008
' (C)2020 mgr Jerzy Wałaszek
'-----------------------------

Const N = 79 ' długość łańcucha s
Const M =  5 ' długość wzorca p

Dim As String s, p
Dim As Integer KMPNext ( M ), i, b, pp

Randomize

' generujemy łańcuch s

s = ""
For i = 1 To N: s += Chr ( 65 + Cint ( Rnd ) ): Next

' generujemy wzorzec

p = ""
For i = 1 To M: p += Chr ( 65 + Cint ( Rnd ) ): Next

' dla wzorca obliczamy tablicę PI [ ] 

KMPNext ( 0 ) = -1: b = -1
For i = 1 To M
  while( b > -1 ) And ( Mid ( p, b + 1, 1 ) <> Mid ( p, i, 1 ) ): b = KMPNext ( b ): Wend
  b += 1:
  if( i = M ) Or ( Mid ( p, i + 1, 1 ) <> Mid ( p, b + 1, 1 ) ) Then
      KMPNext ( i ) = b
  Else
      KMPNext ( i ) = KMPNext ( b )
  End If
Next

' wypisujemy wzorzec p

Print p

' wypisujemy łańcuch s

Print s

' poszukujemy pozycji wzorca w łańcuchu

pp = 0: b = 0
For i = 1 To N
  while( b > -1 ) And ( Mid ( p, b + 1, 1 ) <> Mid ( s, i, 1 ) ): b = KMPNext ( b ): Wend
  b += 1
  If b = M Then
    While pp < i - b
      Print " ";: pp += 1
    Wend
    Print "^";: pp += 1
    b = KMPNext ( b )
  End If
Next
Print
End
Wynik:
BABBB
AABABBBBABBBBABABAAABBBAABBBABABBABABBAABABBBBBAABAAAAAAABABBBABBBABAABBBBAAAAB
  ^    ^                                ^                ^   ^
Wyszukiwanie wzorca algorytmem KMP
(C)2020 mgr Jerzy Wałaszek


...

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2021 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.