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

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

Wyszukiwanie wzorca uproszczonym algorytmem Boyera-Moore'a

SPIS TREŚCI W KONSERWACJI
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. BoyerJ. 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 = + - Last[D] = 0 + 2 - (-1) = 3
2.
 i: 02 3 4 5 6 7 8 .
 s: ? ? ? ? C ? ? ? ? ?
 p: A B C A B 
 j: 0 1 2 3 4 
    → → A BA 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
zp : kod pierwszego znaku alfabetu.
zk : kod ostatniego znaku alfabetu

Wyjście:

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

Elementy pomocnicze:

i – zmienna licznikowa pętli, i ∈ C.

Lista kroków:

K01: Dla i = 0,1,…,zk-zp:  ; wypełniamy całą tablicę Last wartościami -1
     wykonuj Last[i] ← -1
K02: Dla i = 0,1,…,|p|- 1: ; przeglądamy wzorzec wprowadzając do tablicy
     wykonuj Last[kod(p[i])-zp] ← i ; 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.
zp : kod pierwszego znaku alfabetu.
zk : 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:

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 zp i zk:        ; przygotowujemy tablicę ostatnich
     oblicz tablicę Last ; 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 in - m:     ; pętlę wykonujemy dopóki okno wzorca mieści
     wykonuj kroki K07…K14 ; 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]): ; sprawdzamy od końca zgodność
       wykonuj j ← j - 1                  ; znaków wzorca z oknem
K09:   Jeśli j > -1, ; wzorzec pasuje do okna?
       to idź do kroku K14
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])-zp]) ; przesuwamy okno wzorca
       ; wykorzystując tablicę Last
K15: Jeśli pp = -1, ; w razie nieznalezienia pozycji wzorca wypisujemy -1
     to pisz -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
  zk = 66;  // kod ostatniego znaku

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 <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
const int zk = 66;  // kod ostatniego znaku

int main()
{
  string s, p;
  int Last[zk-zp+1], 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 = "";
  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
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 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
Python (dodatek)
# Wyszukiwanie wzorca algorytmem BM
# Data:  9.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
zk = 66 # kod ostatniego znaku

# generujemy łańcuch s

s = ""
for i in range(N):
    s += chr(random.randrange(zp,zk+1))

# generujemy wzorzec

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

Last = [0] * (zk - zp + 1)
for i in range(M):
    Last[ord(p[i]) - zp] = i

# szukamy pozycji wzorca w łańcuchu

pp = 0
i = 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 += 1
    else:
        i += max(1,j-Last[ord(s[i+j])-zp])
print()
print()
Wynik:
ABBBA
AABBAABAAAABAABBABABBBAAAABBBBAABBBABBAAAAAAABBABBBAAAABABBBBAAAABBBAAABBBABABB
                  ^            ^               ^                ^     ^

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
©2024 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.