Szybkie wyszukiwanie wzorca algorytmem 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.

 

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(n2). 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:     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 ← Π[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
  ^    ^                                ^                ^   ^

 

Wyszukiwanie wzorca algorytmem MP
(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.