Algorytmy i Struktury Danych - Wyszukiwanie wzorca pełnym algorytmem BM

Uproszczony algorytm Boyera-Moore'a reaguje tylko na niezgodność znaku wykorzystując wyliczoną wcześniej tablicę Last do znalezienia przesunięcia okna wzorca p w obrębie przeszukiwanego tekstu s. Postępowanie to nazywamy heurystyką niepasującego znaku (ang. bad character heuristics). Zupełnie nie korzystamy tutaj z informacji, iż pewien sufiks b wzorca p pasował do przeszukiwanego tekstu:

Pełna wersja algorytmu nie wyrzuca do kosza tej informacji. Rozważmy możliwe dwa przypadki:

Pasujący sufiks b powtarza się wewnątrz wzorca. Dodatkowo żądamy, aby znak C bezpośrednio poprzedzający ten fragment tekstu był różny od znaku B (B jest oznaczeniem symbolicznym, a nie konkretną literą!), gdyż w przeciwnym razie otrzymamy natychmiastową niezgodność z przeszukiwanym tekstem. Okno wzorca przesuwamy, tak aby uzyskać pokrycie pasującego fragmentu b z pasującym do niego fragmentem b przeszukiwanego tekstu.

Pasujący sufiks b nie powtarza się wewnątrz wzorca. Jednakże istnieje prefikso-sufiks bb wzorca zawarty w pasującym sufiksie b (porusz algorytm KMP). W takim przypadku okno wzorca przesuwamy, tak aby uzyskać pokrycie prefikso-sufiksów we wzorcu i w przeszukiwanym tekście:

Jeśli prefikso-sufiks jest pusty, to okno wzorca można przesunąć o całą długość wzorca beż żadnej straty dla wyników poszukiwań. W efekcie uzyskujemy bardzo ciekawą własność algorytmu Boyera-Moore'a – im wzorzec p jest dłuższy, tym szybciej przebiega wyszukiwanie, ponieważ algorytm przeskakuje większe partie tekstu.

Opisana w tych dwóch punktach strategia postępowania nosi nazwę heurystyki pasującego sufiksu (ang. good suffix heuristics). W wyniku jej zastosowania otrzymujemy przesunięcie okna wzorca bez pomijania możliwych wystąpień w przeszukiwanym tekście.

Pełny algorytm Boyera-Moore'a wykorzystuje obie heurystyki – nie pasującego znaku (opisana w poprzednim rozdziale) oraz pasującego sufiksu, a wynikowe przesunięcie okna wzorca jest większym z tych dwóch wyliczonych przesunięć.

do podrozdziału do strony

Do wyznaczenia przesunięcia w przypadku heurystyki pasującego sufiksu będzie nam potrzebna tablica BMNext zawierająca wartości przesunięć dla poszczególnych sufiksów wzorca (tablica ta jest niejako odwróceniem tablicy KMPNext obecnej w algorytmie KMP). Wyznaczamy ją w dwóch etapach.

Etap 1

Ten etap jest bardzo podobny do przetwarzania wzorca w algorytmie KMP. Pasujący sufiks bb jest prefikso-sufiksem pewnego sufiksu b wzorca p:

Musimy ustalić prefikso-sufiksy sufiksów wzorca, jednakże w porównaniu z algorytmem KMP będzie obowiązywało odwrotne odwzorowanie pomiędzy prefikso-sufiksem a najkrótszym sufiksem zawierającym ten prefikso-sufiks. Jednocześnie musimy zagwarantować, iż dany prefikso-sufiks nie może być rozszerzalny w lewo (patrz znaki B i C we wzorcu) przez znak B, który spowodował niezgodność z przeszukiwanym tekstem. W przeciwnym razie po przesunięciu okna wzorca otrzymalibyśmy natychmiastową niezgodność, ponieważ w tym samym miejscu znów znalazłby się niezgodny znak B.

W etapie 1 obliczana jest pomocnicza tablica П o elementach indeksowanych od 0 do m (m = |p|). Element П[i] zawiera początkową pozycję maksymalnego prefikso-sufiksu sufiksu wzorca rozpoczynającego się na pozycji i-tej.

Przykład:

Dla wzorca ABBABBBA tablicę П wyznaczymy następująco:

Tworzenie tablicy П	Opis
i: 0 1 2 3 4 5 6 7 8 p: A B B A B B B A П: . . . . . . . . 9	Na pozycji m = 8 jest sufiks pusty, Ponieważ nie posiada on prefikso-sufiksu, do П[8] wpisujemy 9.
i: 0 1 2 3 4 5 6 7 8 p: A B B A B B B A П: . . . . . . . 8 9	Na pozycji 7 jest sufiks A. Posiada on prefikso-sufiks pusty rozpoczynający się na pozycji 8.
i: 0 1 2 3 4 5 6 7 8 p: A B B A B B B A П: . . . . . . 8 8 9	Sufiks BA również posiada prefikso-sufiks pusty.
i: 0 1 2 3 4 5 6 7 8 p: A B B A B B B A П: . . . . . 8 8 8 9	Sufiks BBA posiada prefikso-sufiks pusty.
i: 0 1 2 3 4 5 6 7 8 p: A B B A B B B A П: . . . . 8 8 8 8 9	Sufiks BBBA posiada prefikso-sufiks pusty.
i: 0 1 2 3 4 5 6 7 8 p: A B B A B B B A П: . . . 7 8 8 8 8 9	Sufiks ABBBA posiada prefikso-sufiks A rozpoczynający się na pozycji 7.
i: 0 1 2 3 4 5 6 7 8 p: A B B A B B B A П: . . 6 7 8 8 8 8 9	Sufiks BABBBA rozszerza prefikso-sufiks poprzedniego sufiksu do prefikso-sufiksu BA rozpoczynającego się na pozycji 6.
i: 0 1 2 3 4 5 6 7 8 p: A B B A B B B A П: . 5 6 7 8 8 8 8 9	Sufiks BBABBBA znów rozszerza prefikso-sufiks poprzedniego sufiksu do prefikso-sufiksu BBA rozpoczynającego się na pozycji 5.
i: 0 1 2 3 4 5 6 7 8 p: A B B A B B B A П: 7 5 6 7 8 8 8 8 9	Sufiks ABBABBBA redukuje prefikso-sufiks do A na pozycji 7.

Tablica П służy do wstępnej generacji właściwej tablicy BMNext. Na początku zerujemy wszystkie komórki tej tablicy. Następnie wyznaczamy kolejne wartości tablicy П. Jeśli prefikso-sufiks poprzedniego sufiksu wzorca nie może być rozszerzony w lewo na prefikso-sufiks sufiksu rozpoczynającego się na pozycji i-tej, to odnotowujemy ten fakt w elemencie:

BMNext[pozycja prefikso-sufiksu]

o ile nie zawiera on już jakiejś wartości różnej od 0 (dotyczy to prefikso-sufiksu mniejszego sufiksu, który ma preferencje). Do elementu tablicy BMNext wpisujemy różnicę pozycji nie rozszerzalnego prefikso-sufiksu oraz i, czyli:

BMNext[pozycja prefikso-sufiksu] = pozycja prefikso-sufiksu – pozycja sufiksu

W efekcie otrzymujemy wartość przesunięcie okna wzorca p w łańcuchu s, po którym zrównują się pozycje pasującego prefikso-sufiksu we wzorcu i w oknie. Prześledźmy teraz tworzenie obu tablic dla wzorca ABBABBBA:

Tworzenie tablic П i BMNext	Opis
i: 0 1 2 3 4 5 6 7 8 p: A B B A B B B A П: . . . . . . . . 9 BMNext: 0 0 0 0 0 0 0 0 0	Inicjujemy П[8] = 9, zerujemy BMNext
i: 0 1 2 3 4 5 6 7 8 p: A B B A B B B A П: . . . . . . . 8 9 BMNext: 0 0 0 0 0 0 0 0 1	Na pozycji 7 jest sufiks A. Posiada on prefikso-sufiks pusty rozpoczynający się na pozycji 8. Prefikso-sufiks tego sufiksu nie daje się rozszerzyć w lewo. W BMNext[8] wpisujemy 8 - 7 = 1
i: 0 1 2 3 4 5 6 7 8 p: A B B A B B B A П: . . . . . . 8 8 9 BMNext: 0 0 0 0 0 0 0 0 1	Sufiks BA również posiada prefikso-sufiks pusty. Prefikso-sufiks nie jest rozszerzalny, ale w BMNext[8] już mamy wpis 1.
i: 0 1 2 3 4 5 6 7 8 p: A B B A B B B A П: . . . . . 8 8 8 9 BMNext: 0 0 0 0 0 0 0 0 1	Sufiks BBA posiada prefikso-sufiks pusty i nie jest rozszerzalny. Tablicy BMNext nie modyfikujemy.
i: 0 1 2 3 4 5 6 7 8 p: A B B A B B B A П: . . . . 8 8 8 8 9 BMNext: 0 0 0 0 0 0 0 0 1	Sufiks BBBA posiada prefikso-sufiks pusty i jest rozszerzalny. Tablicy BMNext nie modyfikujemy.
i: 0 1 2 3 4 5 6 7 8 p: A B B A B B B A П: . . . 7 8 8 8 8 9 BMNext: 0 0 0 0 0 0 0 0 1	Sufiks ABBBA posiada prefikso-sufiks A, który rozpoczyna się na pozycji 7 i jest rozszerzalny. Tablicy BMNext nie modyfikujemy.
i: 0 1 2 3 4 5 6 7 8 p: A B B A B B B A П: . . 6 7 8 8 8 8 9 BMNext: 0 0 0 0 0 0 0 0 1	Sufiks BABBBA posiada prefikso-sufiks BA , który rozpoczyna się na pozycji 6 i jest rozszerzalny. Tablicy BMNext nie modyfikujemy.
i: 0 1 2 3 4 5 6 7 8 p: A B B A B B B A П: . 5 6 7 8 8 8 8 9 BMNext: 0 0 0 0 0 4 0 0 1	Sufiks BBABBBA posiada prefikso-sufiks BBA, który rozpoczyna się na pozycji 5 i nie jest rozszerzalny. W BMNext[5] wpisujemy 5 - 1 = 4
i: 0 1 2 3 4 5 6 7 8 p: A B B A B B B A П: 7 5 6 7 8 8 8 8 9 BMNext: 0 0 0 0 0 4 0 0 1	Sufiks ABBABBBA redukuje prefikso-sufiks do A na pozycji 7.

Algorytm etapu nr 1 tworzenia tablicy BMNext dla pełnego algorytmu Boyera-Moore'a

Wejście:

p : wzorzec

Wyjście:

BMNext : tablica m+1 elementowa przesunięć okna wzorca, częściowo zapełniona, elementy BMNext ∈ C.
П : pomocnicza tablica m+1 elementowa położeń prefikso-sufiksów sufiksów wzorca, П ∈ C.

Elementy pomocnicze:

i : indeksowanie elementów tablic, i ∈ N.
m : długość wzorca p; m ∈ N.
b : położenie prefikso-sufiksu aktualnego sufiksu, b ∈ N.

Lista kroków:

K01: m ← |p| ; wyznaczamy długość wzorca
K02: Dla i = 0, 1, …, m: ; zerujemy elementy tablicy BMNext
     wykonuj BMNext[i] ← 0
K03: i ← m ; ustawiamy indeks elementów dla tablicy П
K04: b ← m+1 ; wstępne położenie prefikso-sufiksu poza pustym sufiksem
K05: П[i] ← b ; inicjujemy ostatni element tablicy
K06: Dopóki i > 0: ; pętla wypełniająca komórki tablicy П
     wykonuj kroki K07…K12
K07: Dopóki (b ≤ m)  (p[i-1] ≠ p[b-1]): ; pętla obsługuje sytuację, 
     wykonuj kroki K08…K09 ; gdy bieżący prefikso-sufiks istnieje i nie
     ; daje się rozszerzyć w lewo.
K08:   Jeśli BMNext[b] = 0, ; odnotowujemy taki prefikso-sufiks w tablicy
       to BMNext[b] ← b-i ; BMNext o ile nie został już odnotowany przez
       ; wcześniejszy sufiks.
K09:   b ← П[b] ; w b umieszczamy położenie prefikso-sufiksu wewnętrznego
       ; i kontynuujemy pętlę K07
K10: b ← b-1 ; prefikso-sufiks jest rozszerzalny lub nie istnieje
K11: i ← i-1 ; przesuwamy się na kolejną pozycję w lewo.
K12: П[i] ← b ; położenie prefikso-sufiksu zapamiętujemy w tablicy П
K13: Zakończ

Etap 2

Po zakończeniu etapu 1 otrzymujemy wypełnioną tablicę П, zawierającą położenia prefikso-sufiksów kolejnych sufiksów wzorca oraz częściowo wypełnioną tablicę BMNext zawierającą przesunięcia okna wzorca dla kolejnych sufiksów. W etapie 2 sprawdzamy, czy istnieje największy prefikso-sufiks wzorca zawarty w całości w pasującym sufiksie. Wzorzec można wtedy przesunąć tak daleko, jak pozwoli na to pasujący prefikso-sufiks:

Dlatego wyznaczymy teraz dla każdego sufiksu najdłuższy prefikso-sufiks wzorca, który jest zawarty w tym sufiksie. Pozycja startowa najszerszego prefikso-sufiksu wzorca jest zawarta w П[0]. Dla naszego wzorca ABBABBBA jest to 7, ponieważ prefikso-sufiks A rozpoczyna się od pozycji 7:

     i: 0 1 2 3 4 5 6 7 8 
     p: A B B A B B B A
     П: 7 5 6 7 8 8 8 8 9 
BMNext: 0 0 0 0 0 4 0 0 1

Wartość ta zostaje umieszczona w kolejnych, wolnych elementach tablicy BMNext. Jednakże gdy sufiks wzorca stanie się krótszy od prefikso-sufiksu wzorca (czyli gdy go już nie może zawierać), to kolejnym prefikso-sufiksem stanie się jego prefikso-sufiks wewnętrzny. W efekcie otrzymamy pełną tablicę BMNext:

     i: 0 1 2 3 4 5 6 7 8 
     p: A B B A B B B A
     П: 7 5 6 7 8 8 8 8 9 
BMNext: 7 7 7 7 7 4 7 7 1

Algorytm etapu nr 2 tworzenia tablicy BMNext dla pełnego algorytmu Boyera-Moore'a

Wejście:

p : wzorzec.
m : długość wzorca (z poprzedniego etapu), m ∈ N.
BMNext : tablica m+1 elementowa przesunięć okna wzorca częściowo zapełniona w etapie nr 1. BMNext ∈ C.
П : pomocnicza tablica m+1 elementowa położeń prefikso-sufiksów sufiksów wzorca, utworzona w etapie nr 1, П ∈ C.

Wyjście:

BMNext : kompletna tablica m+1 elementowa przesunięć okna wzorca.

Elementy pomocnicze:

i : indeksowanie elementów tablic, i ∈ N.
b : położenie prefikso-sufiksu aktualnego sufiksu, b ∈ N.

Lista kroków:

K01: b ← П[0] ; najdłuższy prefikso-sufiks
K02: Dla i = 0, 1, …, m: ; indeksujemy kolejne komórki tablicy BMNext
     wykonuj kroki K03…K04
K03:   Jeśli BMNext[i] = 0, ; w wolnych elementach umieszczamy
       to BMNext[i] ← b     ; położenie prefikso-sufiksu
K04:  Jeśli i = b, ; jeśli sufiks nie mieści prefikso-sufiksu, 
       to b ← П[b]  ; to bierzemy kolejny prefikso-sufiks
K05: Zakończ

do podrozdziału do strony

Algorytm BM składa się z etapu przetwarzania wzorca, w którym wyznacza się dwie tablice:

Last zawierającą ostatnie położenia znaków alfabetu we wzorcu.
BMNext zawierającą przesunięcia dla pasujących sufiksów wzorca.

Po wyznaczeniu tych tablic następuje właściwy etap wyszukiwania.

Pełny algorytm Boyera-Moore'a wyszukiwania wzorca

Wejście:

s : przeszukiwany łańcuch.
p : poszukiwany wzorzec.
z_p: kod pierwszego znaku alfabetu.
z_k: kod ostatniego znaku alfabetu

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:

i : położenie okna wzorca p w przeszukiwanym łańcuchu s; i ∈ N.
j : położenie porównywanego znaku we wzorcu p; j ∈ N.
m : długość wzorca p – wyznaczane w trakcie wyliczania tablic Last i BMNext; m ∈ N.
n : długość łańcucha s – wyznaczane w trakcie wyliczania tablic Last i BMNext; n ∈ N.
Last : tablica ostatnich wystąpień znaków alfabetu we wzorcu p. Indeksy od 0 do z_k-z_p; Last ∈ C.
BMNext : tablica przesunięć okna wzorca dla pasujących sufiksów. Indeksy od 0 do m; BMNext ∈ C.
pp : znalezione pozycje wzorca p w łańcuchu s; pp ∈ N.
max(a, b) : zwraca większą z liczb a lub b.

Lista kroków::

K01: Wyznacz tablicę Last ; wyznaczamy ostatnie położenia znaków alfabetu we wzorcu
     ; dla p, z_p i z_kK02: Wyznacz tablicę BMNext ; wyznaczamy przesunięcia okna wzorca dla pasujących
     ; sufiksów dla p
K03: pp ← -1 ; ustawiamy pozycję wzorca na "nie znaleziono"
K04: i ← 0 ; okno wzorca umieszczamy na początku łańcucha s
K05: Dopóki i ≤ n-m, ; dopóki okno wzorca mieści się wewnątrz łańcucha
     wykonuj kroki K06…K13
K06:   j ← m-1 ; porównywanie znaków wzorca z łańcuchem rozpoczynamy od końca
K07:   Dopóki (j > -1)  (p[j] = s[i+j]): ; pętla wykonuje się, gdy pozycja j jest
       wykonuj j ← j-1 ; w obrębie wzorca oraz znak wzorca pasuje do znaku okna
       ; wzorca w łańcuchu s.
K08:   Jeśli j = -1, ; cały wzorzec pasuje do okna?
       to idź do kroku K11
K09:   i ← i+max(BMNext[j+1], j-Last[kod(s[i+j])-z_p]) ; jeśli nie, to pozycję okna wzorcaa
       ; zwiększamy o większe z przesunięć pasującego sufiksu lub do ostatniej pozycji
       ; nie pasującego znaku
K10:   Następny obieg pętli K05
K11:   pp ← i ; tutaj jesteśmy, gdy wzorzec pasuje do okna
K12:   Pisz pp ; wyprowadzamy pozycję wzorca p w łańcuchu s
K13:   i ← i+BMNext[0] ; przesuwamy okno na następną możliwą pozycję i kontynuujemy
K14: Jeśli pp = -1, ; sprawdzamy, czy znaleziono pozycję wzorca. Jeśli nie, to wynik -1
     to pisz -1
K15: 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 pełnym algorytmem BM
// Data:  10.06.2008
// (C)2020 mgr Jerzy Wałaszek
//-----------------------------------------

program prg;

uses Math;

const
  N  = 79; // długość łańcucha s
  M  =  5; // długość wzorca p
  zp = 65; // kod pierwszego znaku alfabetu
  zk = 66; // kod ostatniego znaku alfabetu

var
  s, p : ansistring;
  Last : array [0..zk-zp] of integer;
  BMNext, Pi : array [0..M] of integer;
  b, i, j, pp : integer;

begin
  randomize;

  // generujemy łańcuch s
  s := '';
  for i := 1 to N do
    s := s+chr(zp+random(zk-zp+1));

  // generujemy wzorzec p
  p := '';
  for i := 1 to M do
    p := p+chr(zp+random(zk-zp+1));

  // wypisujemy wzorzec
  writeln(p);

  // wypisujemy łańcuch
  writeln(s);

  // dla wzorca obliczamy tablicę Last
  for i := 0 to zk-zp do
    Last[i] := 0;
  for i := 1 to M do
    Last[ord(p[i])-zp] := i;

  // Etap I obliczania tablicy BMNext
  for i := 0 to M do
    BMNext[i] := 0;
  i := M; b := M+1; Pi[i] := b;
  while i > 0 do
  begin
    while(b <= M) and (p[i] <> p[b]) do
    begin
      if BMNext[b] = 0 then
        BMNext[b] := b-i;
      b := Pi[b];
    end;
    dec(b); dec(i); Pi[i] := b;
  end;

  // Etap II obliczania tablicy BMNext
  b := Pi[0];
  for i := 0 to M do
  begin
    if BMNext[i] = 0 then
      BMNext[i] := b;
    if i = b then
      b := Pi[b];
  end;

  // szukamy pozycji wzorca w łańcuchu
  pp := 1; i := 1;
  while i <= N-M+1 do
  begin
    j := M;
    while(j > 0) and (p[j] = s[i+j-1]) do
      dec(j);
    if j = 0 then
    begin
      while pp < i do
      begin
        write(' '); inc(pp);
      end;
      write('^'); inc(pp);
      inc(i, BMNext[0]);
    end
    else
      inc(i, max(BMNext[j], j-Last[ord(s[i+j-1])-zp]));
  end;
  writeln;
end.

C++

// Wyszukiwanie wzorca pełnym algorytmem BM
// Data:  10.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
const int zp = 65; // kod pierwszego znaku alfabetu
const int zk = 66; // kod ostatniego znaku alfabetu

int main()
{
  string s, p;
  int Last[zk-zp+1], BMNext[M+1], Pi[M+1], b, i, j, pp;

  srand(time(NULL));

  // generujemy łańcuch s
  s = "";
  for(i = 0; i < N; i++)
    s += zp+rand() % (zk-zp+1);

  // generujemy wzorzec p
  p = "";
  for(i = 0; i < M; i++)
    p += zp+rand() % (zk-zp+1);

  // wypisujemy wzorzec
  cout << p << endl;

  // wypisujemy łańcuch
  cout << s << endl;

  // dla wzorca obliczamy tablicę Last
  for(i = 0; i <= zk-zp; i++)
    Last[i] = -1;
  for(i = 0; i < M; i++)
    Last[p[i]-zp] = i;

  // Etap I obliczania tablicy BMNext
  for(i = 0; i <= M; i++)
    BMNext[i] = 0;
  i = M; b = M+1; Pi[i] = b;
  while(i > 0)
  {
    while((b <= M) && (p[i-1] != p[b-1]))
    {
      if(BMNext[b] == 0) BMNext[b] = b-i;
      b = Pi[b];
    }
    Pi[--i] = --b;
  }

  // Etap II obliczania tablicy BMNext
  b = Pi[0];
  for(i = 0; i <= M; i++)
  {
    if(BMNext[i] == 0) BMNext[i] = b;
    if(i == b) b = Pi[b];
  }

  // szukamy pozycji wzorca w łańcuchu
  pp = i = 0;
  while(i <= N-M)
  {
    j = M-1;
    while((j > -1) && (p[j] == s[i+j]))
      j--;
    if(j == -1)
    {
      while(pp < i)
      {
        cout << " "; pp++;
      }
      cout << "^"; pp++;
      i += BMNext[0];
    }
    else
      i += max(BMNext[j+1], j-Last[s[i+j]-zp]);
  }
  cout << endl;
  return 0;
}

Basic

' Wyszukiwanie wzorca pełnym algorytmem BM
' Data:  10.06.2008
' (C)2020 mgr Jerzy Wałaszek
'-----------------------------------------

Const N  = 79 ' długość łańcucha s
Const M  =  5 ' długość wzorca p
Const zp = 65 ' kod pierwszego znaku
Const zk = 66 ' kod ostatniego znaku

' Funkcja wyznacza większą z dwóch liczb
'---------------------------------------
Function max (Byval a As Integer, _
              Byval b As Integer) _
              As Integer
  If a > b Then
    max = a
  Else
    max = b
  End If
End Function

Dim As String s, p
Dim As Integer Last(zk-zp), BMNext(M), Pi(M)
Dim As Integer b, i, j, pp

Randomize

' generujemy łańcuch s
s = ""
For i = 1 To N
  s += Chr(zp+Cint(Rnd*(zk-zp)))
Next

' generujemy wzorzec p
p = ""
For i = 1 To M
  p += Chr(zp+Cint(Rnd*(zk-zp)))
Next

' wypisujemy wzorzec
Print p

' wypisujemy łańcuch
Print s

' dla wzorca obliczamy tablicę Last
For i = 0 To zk-zp
  Last(i) = 0
Next
For i = 1 To M
  Last(Asc(Mid(p, i, 1))-zp) = i
Next

' Etap I obliczania tablicy BMNext
For i = 0 To M: BMNext(i) = 0: Next
i = M: b = M+1: Pi(i) = b
While i > 0
  While(b <= M) And _
       (Mid(p, i, 1) <> Mid(p, b, 1))
    If BMNext(b) = 0 Then _
      BMNext(b) = b-i
    b = Pi(b)
  Wend
  b -= 1: i -= 1: Pi(i) = b
Wend

' Etap II obliczania tablicy BMNext
b = Pi(0)
For i = 0 To M
  If BMNext(i) = 0 Then _
    BMNext(i) = b
  If i = b Then _
    b = Pi(b)
Next

' szukamy pozycji wzorca w łańcuchu
pp = 1: i = 1
While i <= N-M+1
  j = M
  While (j > 0) And _
        (Mid(p, j, 1) = Mid(s, i+j-1, 1))
    j -= 1
  Wend
  If j = 0 Then
    While pp < i
      Print " ";: pp += 1
    Wend
    Print "^";: pp += 1
    i += BMNext(0)
  Else
    i += max(BMNext(j), _
             j-Last(Asc(Mid(s, i+j-1, 1))-zp))
  End If
Wend
Print
End

Python (dodatek)

# Wyszukiwanie wzorca pełnym algorytmem BM
# Data:  10.03.2024
# (C)2024 mgr Jerzy Wałaszek
#-----------------------------------------

import random

N  = 79 # długość łańcucha s
M  =  5 # długość wzorca p
ZP = 65 # kod pierwszego znaku alfabetu
ZK = 66 # kod ostatniego znaku alfabetu

# generujemy łańcuch s
s = ""
for i in range(N):
    s += chr(random.randrange(ZP, ZK+1))
# generujemy wzorzec p
p = ""
for i in range(M):
    p += chr(random.randrange(ZP, ZK+1))
# wypisujemy wzorzec
print(p)
# wypisujemy łańcuch
print(s)
# dla wzorca obliczamy tablicę Last
t_last = [-1]*(ZK-ZP+1)
for i in range(M):
    t_last[ord(p[i])-ZP] = i
# Etap I obliczania tablicy BMNext
t_bmnext = [0]*(M+1)
t_pi = [0]*(M+1)
i = M
b = M+1
t_pi[i] = b
while i > 0:
    while (b <= M) and (p[i-1] != p[b-1]):
        if t_bmnext[b] == 0:
            t_bmnext[b] = b-i
        b = t_pi[b]
    i -= 1
    b -= 1
    t_pi[i] = b
# Etap II obliczania tablicy BMNext
b = t_pi[0]
for i in range(M+1):
    if t_bmnext[i] == 0:
        t_bmnext[i] = b
    if i == b:
        b = t_pi[b]

# szukamy pozycji wzorca w łańcuchu
pp, i = 0, 0
while i <= N-M:
    j = M-1
    while (j > -1) and (p[j] == s[i+j]):
        j -= 1
    if j == -1:
        while pp < i:
            print(" ", end="")
            pp += 1
        print("^", end="")
        pp += 1
        i += t_bmnext[0]
    else:
        i += max(t_bmnext[j+1],
                 j-t_last[ord(s[i+j])-ZP])
print()
print()

Wynik:

BABAA
AABBABABAAAABBBABBAABABAABBBBBAABBAAAABABAABBABBBBBABBABBBABABBBABAABBBAABBABBA
     ^              ^                 ^                        ^

JavaScript

<html>
  <head>
    <title>
      BM
    </title>
  </head>
  <body>

<div style="overflow-x: auto;"
     align="center">
  <table
  border="0"
  cellpadding="4"
  style="border-collapse:
         collapse">
    <tr>
      <td nowrap>
        <form
        name="frm"
        style="text-align: center;
               background-color:
               #E7E7DA">
          <b>Wyszukiwanie wzorca<br>
          pełnym algorytmem BM
          </b><br/>
          &nbsp;
          (C)2026 mgr Jerzy Wałaszek
          &nbsp;&nbsp;
          <hr>
          <input
          type="button"
          value="Wykonaj"
          name="B2"
          onclick="main()">
          <hr>
          <b>Wyniki:</b>
          <div align="center">
            <table
            border="0"
            cellpadding="4"
            style="border-collapse:
                   collapse">
              <tr>
                <td id="out">
                  &nbsp;
                </td>
              </tr>
            </table>
          </div>
        </form>
      </td>
    </tr>
  </table>
</div>

<script type=text/javascript
        language=javascript>

// Wyszukiwanie wzorca
// pełnym algorytmem BM
// Data:  10.06.2008
// (C)2008 mgr Jerzy Wałaszek
//---------------------------

function main()
{
  // długość łańcucha s
  var N  = 79;
  // długość wzorca p
  var M  =  5;
  // kod pierwszego
  // znaku alfabetu
  var zp = 65;
  // kod ostatniego
  // znaku alfabetu
  var zk = 66;
  var s, p, b, i, j, pp, t;
  var Last = new Array(zk - zp + 1);
  var BMNext = new Array(M + 1);
  var Pi = new Array(M + 1);

  // generujemy łańcuch s
  s = "";
  for(i = 0; i < N; i++)
    s += String.fromCharCode(
         zp + Math.floor(
         Math.random() *
         (zk - zp + 1)));

  // generujemy wzorzec p
  p = "";
  for(i = 0; i < M; i++)
    p += String.fromCharCode(
         zp + Math.floor(
         Math.random() *
         (zk - zp + 1)));

  // wypisujemy wzorzec
  // i łańcuch
  t = "<pre>" + p + "<br/>" +
      s + "<br/><span style=" +
      "'color:red'>";

  // dla wzorca obliczamy
  // tablicę Last[]
  for(i = 0; i <= zk - zp; i++)
    Last[i] = -1;
  for(i = 0; i < M; i++)
    Last[p.charCodeAt(i) - zp] = i;

  // Etap I obliczania
  // tablicy BMNext[]
  for(i = 0; i <= M; i++)
    BMNext[i] = 0;
  i = M;
  b = M + 1;
  Pi[i] = b;
  while(i>0)
  {
    while((b <= M) &&
          (p.charAt(i - 1) !=
          p.charAt(b - 1)))
    {
      if(BMNext[b] == 0)
        BMNext[b] = b - i;
      b = Pi[b];
    }
    Pi[--i] = --b;
  }

// Etap II obliczania
// tablicy BMNext[]

  b = Pi[0];
  for(i = 0; i <= M; i++)
  {
    if(BMNext[i] == 0)
      BMNext[i] = b;
    if(i == b)
      b = Pi[b];
  }

  // szukamy pozycji
  // wzorca w łańcuchu
  pp = i = 0;
  while(i < N -  M)
  {
    j = M - 1;
    while((j>-1) &&
          (p.charAt(j) ==
           s.charAt(i + j)))
      j--;
    if(j == -1)
    {
      while(pp < i)
      {
        t += " "; pp++;
      }
      t += "^"; pp++;
      i += BMNext[0];
    }
    else
      i += Math.floor(
           Math.max(
           BMNext[j + 1],
           j - Last[
           s.charCodeAt(i + j) -
           zp]));
  }
  t += "</span></pre>";
  document.getElementById("out")
  .innerHTML = t;
}

</script>

  </body>
</html>

do podrozdziału do strony

Szybkie wyszukiwanie wzorca pełnym algorytmem Boyera-Moore'a

Problem

Heurystyki algorytmu Boyera-Moore'a

Wyznaczanie tablicy przesunięć BMNext

Etap 1

Algorytm etapu nr 1 tworzenia tablicy BMNext dla pełnego algorytmu Boyera-Moore'a

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Etap 2

Algorytm etapu nr 2 tworzenia tablicy BMNext dla pełnego algorytmu Boyera-Moore'a

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Algorytm Boyera-Moore'a wyszukiwania wzorca

Pełny algorytm Boyera-Moore'a wyszukiwania wzorca

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków::

Przykładowe programy