Szybkie wyszukiwanie wzorca algorytmem Knutha-Morrisa-Pratta


Tematy pokrewne
Łańcuchy znakowe
Podstawowe pojęcia dotyczące przetwarzania tekstów
Podstawowe operacje na łańcuchach znakowych
Naiwne wyszukiwanie wzorca w tekście
Wyszukiwanie maksymalnego prefikso-sufiksu
Szybkie wyszukiwanie wzorca algorytmem Morrisa-Pratta
Szybkie wyszukiwanie wzorca algorytmem Knutha-Morrisa-Pratta
Szybkie wyszukiwanie wzorca uproszczonym algorytmem Boyera-Moore'a
Szybkie wyszukiwanie wzorca pełnym algorytmem Boyera-Moore'a
Wyszukiwanie wzorca algorytmem Karpa-Rabina
Zliczanie słów w łańcuchu
Dzielenie łańcucha na słowa
Wyszukiwanie najdłuższego słowa w łańcuchu
Wyszukiwanie najdłuższego wspólnego podłańcucha
Wyszukiwanie najdłuższego wspólnego podciągu
Wyszukiwanie najkrótszego wspólnego nadłańcucha
Wyszukiwanie słów podwójnych
Wyszukiwanie palindromów
MasterMind – komputer kontra człowiek
MasterMind – człowiek kontra komputer
Szyfr Cezara
Szyfrowanie z pseudolosowym odstępem
Szyfry przestawieniowe
Szyfr Enigmy
Szyfrowanie RSA
Dodawanie dużych liczb
Mnożenie dużych liczb
Potęgowanie dużych liczb
Duże liczby Fibonacciego
Haszowanie
Wbudowane generatory liczb pseudolosowych
Generowanie liczb pseudolosowych
Podstawowe operacje na tablicach
Wyszukiwanie liniowe
Wyszukiwanie liniowe z wartownikiem

 

Problem

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

 

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) :

 

 

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. 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| wykonuj K04...K06 ; wyznaczamy długości prefikso-sufiksów dla prefiksów łańcucha s
K04:     Dopóki b > -1 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:     bb + 1 ; rozszerzamy prefikso-sufiks
K06:     Jeśli i = |s| 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.

Elementy 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 K05...K10 ; pętla wyznacza znaki łańcucha do porównania ze znakami wzorca
K05:     Dopóki (b > -1) (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:     bb + 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:     ppi - 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, pisz -1 ; jeśli wzorzec p nie występuje w s, wyprowadzamy -1
K12: Zakończ  

 

Program

Ważne:

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 80 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.

 

Lazarus
// Wyszukiwanie wzorca algorytmem KMP
// Data:  4.06.2008
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------

program prg;

const
  N = 80;  // 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

  write(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.
Code::Blocks
// Wyszukiwanie wzorca algorytmem KMP
// Data:  4.06.2008
// (C)2012 mgr Jerzy Wałaszek
//-----------------------------

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

using namespace std;

const int N = 80;  // 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;

  // 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;
}
Free Basic
' Wyszukiwanie wzorca algorytmem KMP
' Data:  4.06.2008
' (C)2012 mgr Jerzy Wałaszek
'-----------------------------

Const N = 80 ' 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
AABABBBBABBBBABABAAABBBAABBBABABBABABBAABABBBBBAABAAAAAAABABBBABBBABAABBBBAAAABB
  ^    ^                                ^                ^   ^

 

Wyszukiwanie wzorca algorytmem KMP
(C)2012 mgr Jerzy Wałaszek


...

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.