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

©2024 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 wciąż 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, BC 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 B
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 0 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 AA 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, 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.

Elementy 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|: ; wyznaczamy długości prefikso-sufiksów
     wykonuj kroki K04…K06 ; dla prefiksów łańcucha s
K04: Dopóki (b > -1) obrazek (s[b] ≠ s[i-1]): ; w pętli K04 szukamy prefikso-sufiksu b
     wykonuj b ← KMPNext[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], ; Jeśli następny znak wzorca różni się od
     to KMPNext[i] ← b, ; znaku tuż za prefikso-sufiksem, to w tablicy KMPNext
     inaczej KMPNext[i] ← KMPNext[b] ; 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.

Elementy pomocnicze:

pp : zawiera wyznaczane pozycje wzorca; pp ∈ C.
: 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: ; pętla wyznacza znaki łańcucha do
     wykonuj kroki K05…K10 ; porównania ze znakami wzorca.
K05:   Dopóki (b > -1) obrazek (p[b] ≠ s[i]): ; Szukamy we wzorcu p
       wykonuj b ← KMPNext[b] ; rozszerzalnego prefiksu pasującego
       ; do prefiksu okna wzorca. Pętlę K05 przerywamy, jeśli
       ; znajdziemy rozszerzalny prefiks lub napotkamy wartownika -1.
K06:   bb+1 ; Rozszerzamy prefiks o 1 znak. Jeśli prefiks był
       ; wartownikiem, to otrzymuje wartość 0.
K07:   Jeśli b < |p|, ; Jeśli prefiks nie obejmuje całego wzorca,
       to następny obieg pętli K04 ; to kontynuujemy pętlę K04,
       ; czyli porównujemy znak p[b] z kolejnym znakiem łańcucha s.
K08:   ppi-b+1 ; wyznaczamy pozycję wzorca p w łańcuchu s.
K09:   Pisz pp ; wyprowadzamy tę pozycję.
K10:   bKMPNext[b] ; redukujemy b do długości prefikso-sufiksu
       ; wzorca.
K11: Jeśli pp = -1, ; jeśli wzorzec p nie występuje w s,
     to pisz -1 ; to 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 AB 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));

  // 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 <ctime>

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

  // obliczamy tablicę KMPNext
  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

' obliczamy tablicę KMPNext
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
Python (dodatek)
# Wyszukiwanie wzorca algorytmem KMP
# Data:  8.03.2024
# (C)2024 mgr Jerzy Wałaszek
#-----------------------------------

import random

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

# generujemy łańcuch s
s = ""
for i in range(N):
    s += chr(random.randrange(65,67))

# generujemy wzorzec p
p = ""
for i in range(M):
    p += chr(random.randrange(65,67))

# obliczamy tablicę KMPNext
KMPNext = [-1]
b = -1
for i in range(1,M+1):
    while(b > -1) and (p[b] != p[i-1]):
        b = KMPNext[b]
    b += 1
    if(i == M) or (p[i] != p[b]):
        KMPNext.append(b)
    else:
        KMPNext.append(KMPNext[b])

# wypisujemy wzorzec p
print(p)

# wypisujemy łańcuch s
print(s)

# poszukujemy pozycji wzorca w łańcuchu
pp = 0
b = 0
for i in range(N):
    while(b > -1) and (p[b] != s[i]):
        b = KMPNext[b]
    b += 1
    if b == M:
        while pp < i-b+1:
            print(" ", end="")
            pp += 1
        print("^", end="")
        pp += 1
        b = KMPNext[b]
print()
print()
Wynik:
BBBAB
BAAABBBABBAABAAABAAAABBBBAABABAABBABBBABAABABAAABBAABBABBAABABAABBBABBAAAAAAAAA
    ^                              ^                            ^

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
©2024 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.