Algorytmy i Struktury Danych - Wyszukiwanie wzorca algorytmem MP

Problem

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

Zadanie znajdowania wzorca w łańcuchu rozwiązuje algorytm opracowany przez J. H. Morrisa i V. R. Pratta w 1977 roku. Algorytm działa w czasie liniowym O(n + m), gdzie n jest długością przeszukiwanego łańcucha, a m jest długością poszukiwanego wzorca. W algorytmie Morrisa-Pratta (w skrócie algorytm MP) wykorzystuje się tablicę Π, której tworzenie opisane jest w rozdziale o wyszukiwaniu maksymalnego prefikso-sufiksu. Korzysta się przy tym z następującej własności łańcuchów tekstowych:

Załóżmy, iż poszukujemy pierwszego wystąpienie wzorca p w danym łańcuchu tekstowym s. W trakcie porównywania kolejnych znaków łańcucha ze znakami wzorca natrafiliśmy na sytuację, w której pewien prefiks wzorca p, o długości b znaków, pasuje do prefiksu okna w łańcuchu s przed pozycją i-tą, jednakże znak s[i] (oznaczony na rysunku symbolem A) różni się od znaku p[b] (oznaczony symbolem B), który znajduje się we wzorcu tuż za pasującym prefiksem:

Algorytm N w takiej sytuacji przesuwa okno wzorca o jedną pozycję w prawo względem przeszukiwanego tekstu i rozpoczyna od początku porównywanie znaków wzorca p ze znakami okna nie korzystając zupełnie z faktu zgodności części znaków. To marnotrawstwo prowadzi w efekcie do klasy złożoności obliczeniowej O(n²). Tymczasem okazuje się, iż wykorzystując fakt istnienia pasującego prefiksu, możemy pominąć pewne porównania znaków bez żadnej szkody dla wyniku poszukiwań. Otóż po stwierdzeniu niezgodności okno wzorca przesuwamy tak, aby przed znakiem s[i] znalazł się maksymalny prefikso-sufiks prefiksu wzorca p:

Dzięki temu podejściu pomijamy niepotrzebne porównania znaków oraz unikamy cofania się indeksu i (przesuwa się jedynie okno wzorca).

Dla każdego prefiksu wzorca szerokość maksymalnego prefikso-sufiksu można wyznaczyć przed rozpoczęciem wyszukiwania – do tego właśnie celu generujemy tablicę Π algorytmem MP podanym w poprzednim rozdziale. Dla danej długości prefiksu b możemy z tej tablicy odczytać szerokość maksymalnego prefikso-sufiksu tego prefiksu. W naszym przypadku będzie to:

bb = Π[b]

Teraz porównujemy znak wzorca p[bb] (oznaczony na rysunku symbolem C) ze znakiem s[i] (symbol A). Jeśli wciąż mamy niezgodność, to procedurę powtarzamy, aż do wyczerpania się prefikso-sufiksów – w takim przypadku okno wzorca oraz indeks i przesuwamy o jedną pozycję w prawo.

Jeśli otrzymamy zgodność, to pasujący prefiks zwiększa swoją długość o 1 znak. Przesuwamy również indeks i o 1, ponieważ znak na tej pozycji został już całkowicie wykorzystany przez algorytm MP.

Jeśli prefiks obejmie cały wzorzec (b = |s|), to znaleziona zostanie pozycja wzorca w s i będzie ona równa i - b + 1. W przeciwnym razie poszukiwania kontynuujemy.

Zwróć uwagę, iż algorytm MP nigdy nie cofa indeksu i. Dzięki tej własności algorytm umożliwia przetwarzanie danych sekwencyjnych – np. wyszukiwanie położenia wzorca w dużym pliku, który fizycznie może nie mieścić się w pamięci operacyjnej komputera – każdy znak pliku jest odczytywany tylko jeden raz.

Algorytm Morrisa-Pratta wyszukiwania wzorca

Wejście

s	–	łańcuch znakowy
p	–	poszukiwany wzorzec

Wyjście:

Kolejne pozycje wystąpienia wzorca w łańcuchu. Wartość -1 nie wskazuje żadnej pozycji wzorca i oznacza, iż wzorzec nie występuje 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 N, 0 ≤ b ≤ \|p\|.
Π	–	tablica o indeksach od 0 do \|p\|, przechowująca długości maksymalnych prefikso-sufiksów kolejnych prefiksów wzorca p, Π C.

Lista kroków:

K01:	Wyznacz tablicę Π	; wyznaczamy tablicę maksymalnych prefikso-sufiksów
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 ← Π[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 ← Π[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

Uwaga: Porównaj algorytm MP wyszukiwania wzorca z algorytmem wyznaczania tablicy Π[0] i wyciągnij wnioski.

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 MP
// Data:  3.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;
  PI : 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ę PI[]

  PI[0] := -1;
  b := -1;
  for i := 1 to M do
  begin
    while (b > -1) and (p[b + 1] <> p[i]) do b := PI[b];
    inc(b); PI[i] := 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 := PI[b];
    inc(b);
    if b = M then
    begin
      while pp < i - b do
      begin
        write(' '); inc(pp);
      end;
      write('^'); inc(pp);
      b := PI[b];
    end
  end;
  writeln;
end.

Code::Blocks

// Wyszukiwanie wzorca algorytmem MP
// Data:  3.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 PI[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ę PI[]

  PI[0] = b = -1;
  for(i = 1; i <= M; i++)
  {
    while((b > -1) && (p[b] != p[i - 1])) b = PI[b];
    PI[i] = ++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 = PI[b];
    if(++b == M)
    {
      while(pp < i - b + 1)
      {
        cout << " "; pp++;
      }
      cout << "^"; pp++;
      b = PI[b];
    }
  }
  cout << endl;
  return 0;
}

Free Basic

' Wyszukiwanie wzorca algorytmem MP
' Data:  3.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 PI(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[]

PI(0) = -1: b = -1
For i = 1 To M
  While (b > -1) And (Mid(p,b + 1,1) <> Mid(p,i,1)): b = PI(b): Wend
  b += 1: PI(i) = b
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 = PI(b): Wend
  b += 1
  If b = M Then
    While pp < i - b
      Print " ";: pp += 1
    Wend
    Print "^";: pp += 1
    b = PI(b)
  End If
Next
Print
End

Wynik

BABBB
AABABBBBABBBBABABAAABBBAABBBABABBABABBAABABBBBBAABAAAAAAABABBBABBBABAABBBBAAAABB
^ ^ ^ ^ ^