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

©2021 mgr Jerzy Wałaszek
I LO w Tarnowie

Wyszukiwanie wzorca uproszczonym algorytmem Boyera-Moore'a

SPIS TREŚCI
Tematy pomocnicze

Problem

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

Rozwiązanie

Opisany w poprzednim rozdziale algorytm Knutha-Morrisa-Pratta, chociaż bardzo sprytny, jednak wciąż wymaga przeglądnięcia kolejnych znaków przeszukiwanego łańcucha tekstowego. W stosunku do algorytmu naiwnego zaletą algorytmu KMP jest to, iż nie cofamy się w przeszukiwanym tekście w przypadku stwierdzenia niezgodności ze wzorcem.

W roku 1975 Robert S. Boyer i J. Strother Moore wynaleźli znacznie lepszy algorytm, który uważa się za najszybszy, praktyczny algorytm wyszukiwania wzorca, stosowany obecnie w prawie każdym edytorze tekstu przy wyszukiwaniu tekstów. Jako ciekawostkę możemy podać, iż algorytm BM zaimplementowano w języku FreeBasic. Najpierw opiszemy uproszczoną wersję tego algorytmu.

Algorytm Boyera-Moore'a ( w skrócie algorytm BM) rozpoczyna porównywanie od ostatniego znaku wzorca, czyli odwrotnie niż opisane poprzednio algorytmy. Co nam to daje? Bardzo wiele. Na przykład jeśli ostatni znak wzorca nie zgadza się ze znakiem w przeszukiwanym tekście i dodatkowo wiemy, iż znak z przeszukiwanego tekstu nie występuje dalej we wzorcu, to okno wzorca możemy od razu przesunąć o tyle pozycji, ile znaków zawiera wzorzec. W przeciwnym razie wzorzec pozycjonujemy tak, aby zgrać pozycje znaku występującego jednocześnie w przeszukiwanym tekście i we wzorcu. Algorytmy naiwny i KMP nie pomijają w ten sposób znaków w przeszukiwanym tekście. Dzięki temu algorytm BM zwykle dużo szybciej dochodzi do rozwiązania – mówimy, iż dla typowych danych posiada on podliniową klasę złożoności obliczeniowej. Dla oddania sprawiedliwości należy jednakże zauważyć, iż algorytm KMP nie wymaga buforowania przeglądanego tekstu (jest to bardzo korzystne w przypadku wykonywania poszukiwań np. w dużych plikach przechowywanych na zewnętrznym nośniku danych – tekst wczytujemy znak po znaku i przetwarzamy ), tymczasem w algorytmie BM takie buforowanie jest konieczne. Jeśli przeszukiwany tekst znajduje się w całości w pamięci operacyjnej komputera, to ograniczenie powyższe nie jest kłopotliwe.

Przykład:

Dla przykładu wyszukajmy wzorzec ABCAB w tekście ACBADBABCABD.

Lp. Wyszukiwanie wzorca Opis
1.
 A C B A D B A B C A B D 
 A B C A B 
Okno wzorca umieszczamy na początku przeszukiwanego tekstu.
2.
 A C B A D B A B C A B D 
 A B C A B 
Porównanie rozpoczynamy od ostatniego znaku wzorca. Znaki są różne. Dodatkowo znak D z tekstu nie występuje we wzorcu.
3.
 A C B A D B A B C A B D 
    → → A B C A B 
Dlatego okno wzorca możemy od razu przesunąć o 5 pozycji (z tylu znaków składa się cały wzorzec ).
4.
 A C B A D B A B C A B D 
           A B C A B 
Znów porównujemy ostatni znak wzorca ze znakiem tekstu. Jest niezgodność. Lecz w tym przypadku litera A tekstu występuje we wzorcu.
5.
 A C B A D B A B C A B D 
            A B C A B 
Okno wzorca przesuwamy tak, aby litera A z tekstu i ostatnia litera A ze wzorca zrównały się pozycjami.
6.
 A C B A D B A B C A B D 
             A B C A B 
Teraz porównanie daje zgodność wszystkich znaków wzorca – zadanie zostało wykonane.

Do wykonywania przesunięcia okna wzorca względem przeszukiwanego tekstu wykorzystamy tablicę Last. W tablicy tej indeksy poszczególnych elementów odpowiadają kodom znaków alfabetu. Elementy natomiast określają ostatnie położenie danej litery we wzorcu. Jeśli litery nie ma we wzorcu, to reprezentujący ją element w tablicy Last ma wartość -1.

Przykład:

Załóżmy, iż alfabet składa się z 4 znaków ABCD, Tablica Last będzie zawierała cztery elementy. Dla podanego we wcześniejszym przykładzie wzorca ABCAB  tablica ta przyjmie następującą postać:

Last [ A: ( 3 ), B: ( 4 ), C: ( 2 ), D: ( -1 ) ]

W trakcie wyszukiwania może zajść jeden z trzech poniższych przypadków:

Niech i  oznacza pozycję początku okna wzorca p  w przeszukiwanym tekście s, a j  pozycję we wzorcu, na której występuje niezgodność ze znakiem tekstu.

Lp. Możliwe przypadki Opis
1.
 i: 0 1 2 3 4 5 6 7 8 .
 s: ? ? D A B ? ? ? ? ?
 p: A B C A B   
 j: 0 1 2 3 4   
    → → → A B C A B 
Litera D nie występuje we wzorcu p. Okno wzorca możemy przesunąć na pozycję:
i  = i  + j  - Last [ D ] = 0 + 2 - ( -1 ) = 3
2.
 i: 0 1 2 3 4 5 6 7 8 .
 s: ? ? ? ? C ? ? ? ? ?
 p: A B C A B 
 j: 0 1 2 3 4 
    → → A B C A B 
Litera C jest we wzorcu na pozycji 2. Okno możemy przesunąć na pozycję:
i  = i  + j  - Last [ C ] = 0 + 4 - 2 = 2
3.
 i: 0 1 2 3 4 5 6 7 8 .
 s: ? A C A B ? ? ? ? ?
 p: A B C A B 
 j: 0 1 2 3 4
A B C A B ← ←
     A B C A B
W tym przypadku zastosowanie powyższej reguły daje ujemny przesuw okna wzorca - okno cofa się w lewo, zamiast przesunąć się w prawo
i
  = i  + j  - Last [ A ] = 0 + 1 - 3 = -2

Rozwiązaniem jest zastosowanie reguły, iż w przypadku niezgodności okno wzorca przesuwamy zawsze o większą z dwóch liczb:
1 oraz j  - Last [ X ], czyli max ( 1, j  - Last [ X ] )

Wtedy:
i  = i  + max ( 1, j  - Last [ A ] )
i  = 0 + max ( 1, 1 - 3 ) = 0 + max ( 1, -2 ) = 0 + 1 = 1

Algorytm tworzenia tablicy Last [ ] dla algorytmu Boyera-Moore'a

Tablica Last jest dodatkową strukturą danych wykorzystywaną w uproszczonym algorytmie Boyera-Moore'a. Przechowuje pozycje ostatnich wystąpień we wzorcu p  wszystkich możliwych znaków alfabetu. Jeśli danego znaku nie ma we wzorcu, to pozycja ustawiana jest na -1.

Wejście:

p – wzorzec
z p  – kod pierwszego znaku alfabetu.
z k  – kod ostatniego znaku alfabetu

Wyjście:

Last – tablica o indeksach od 0 do z k - z p. Każdy element Last [ z k - z i ]  ∈ C i określa ostatnie położenie znaku o kodzie z i  we wzorcu. Takie podejście jest konieczne dla języka C++, który wymaga, aby indeksy tablic rozpoczynały się od 0.

Zmienne pomocnicze:

i  – zmienna licznikowa pętli, i  ∈ N

Lista kroków:

K01: Dla i  = 0, 1, ..., z k  - z p:
wykonuj Last [ i  ] ← -1
wypełniamy całą tablicę Last wartościami -1
K02: Dla i  = 0, 1, ..., |p| - 1:
wykonuj Last [ kod ( p [ i  ] ) - z p  ] ← i
przeglądamy wzorzec wprowadzając do tablicy Last położenia kolejno napotkanych liter. Ponieważ poprzednie wpisy są nadpisywane, w efekcie otrzymamy ostatnie położenia znaków występujących we wzorcu. Komórki nie zapisane przechowują wartość -1, która pochodzi z pętli K01.
K03: Zakończ  

Uproszczony algorytm  Boyera-Moore'a wyszukiwania wzorca

Wejście:

s  – łańcuch znakowy do przeszukania
p  – wzorzec, którego wystąpień poszukujemy w łańcuchu s
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.

Zmienne pomocnicze:

Last  –  tablica ostatnich pozycji wszystkich znaków alfabetu we wzorcu p, elementy Last  ∈ C
i  – pozycja okna wzorca w łańcuchu s, i  ∈ N
j  – pozycja znaku we wzorcu p, który porównujemy ze znakiem łańcucha s, j  ∈ N
max ( a, b  )  – funkcja zwracająca większą z liczb a  i b.
pp  – zawiera pozycję wzorca p  w łańcuchu s, pp  ∈ N
m  – długość wzorca p, m  ∈ N
n  – długość łańcucha s, n  ∈ N

Lista kroków:

K01: Dla z p  i z k,
oblicz
tablicę Last
przygotowujemy tablicę ostatnich pozycji znaków we wzorcu
K02: m  ← | p  | zapamiętujemy w m długość wzorca
K03: n  ← | s  | a w n długość łańcucha
K04: pp  ← -1 pozycję łańcucha p w s wstępnie ustawiamy na -1
K05: i  ← 0 okno wzorca umieszczamy na początku łańcucha s
K06: Dopóki i  ≤ n  - m,
wykonuj kroki K07...K14
pętlę wykonujemy dopóki okno wzorca mieści się w łańcuchu
K07:     j  ← m  - 1 w j ostatnia pozycja znaku we wzorcu p
K08:     Dopóki ( j  > -1 ) ∧ ( p [ j  ] = s [ i + j  ] ),
    wykonuj j  ← j  - 1
sprawdzamy od końca zgodność znaków wzorca z oknem
K09:     Jeśli j  > -1,
    to idź do kroku K14
wzorzec pasuje do okna?
K10:     pp  ← i zapamiętujemy pozycję okna
K11:     Pisz pp wyprowadzamy znalezioną pozycję
K12:     i  ← i  + 1 przesuwamy pozycję okna
K13:     Kontynuuj pętlę K06 i szukamy dalej
K14:     i  ← i  + max ( 1, j  - Last [ kod ( s [ i  + j  ] ) - z p  ] ) - przesuwamy okno wzorca wykorzystując tablicę Last
K15: Jeśli pp  = -1,
to pisz -1
w razie nie znalezienia pozycji wzorca wypisujemy -1
K16: 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 algorytmem BM
// Data:  6.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;
  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 := '';
  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;

  // 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 );
    end
    else inc ( i, max ( 1, j - Last [ ord ( s [ i+j-1 ] ) - zp ] ) );
  end;
  writeln;
end.
C++
// Wyszukiwanie wzorca algorytmem BM
// Data:  6.06.2008
// (C)2020 mgr Jerzy Wałaszek
//----------------------------------

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

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 ], i, j, pp;

  srand ( ( unsigned )time ( NULL ) );

  // generujemy łańcuch s

  s = "";
  for( i = 0; i < N; i++ ) s += zp + rand( ) % ( zk - zp + 1 );

  // generujemy wzorzec

  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;

  // 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++;
    }
    else i += max ( 1, j - Last [ s [ i + j ] - zp ] );
  }
  cout << endl << endl;
  return 0;
}
Basic
' Wyszukiwanie wzorca algorytmem BM
' Data:  6.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 alfabetu
Const zk = 66  ' kod ostatniego znaku alfabetu

' 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 Function

Dim As String s, p
Dim As Integer Last ( zk-zp ), 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 = ""
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

' 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 += 1
  Else
    i += max ( 1, j - Last ( Asc ( Mid ( s, i + j - 1, 1 ) ) - zp ) )
  End If
Wend
Print
End
Wynik:
AAABB
ABABAAAAABBBAAAAABABAABABAAABBBABAAAABABBABBAABABBBBAAAABBAABBBAAAAABBBBAAAAABA
      ^                  ^                           ^           ^
Wyszukiwanie wzorca uproszczonym algorytmem BM
(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
©2021 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.