Wyszukiwanie wzorca uproszczonym algorytmem Boyera-Moore'a


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.

 

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
zp – kod pierwszego znaku alfabetu.
zk – kod ostatniego znaku alfabetu

Wyjście:

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

Elementy pomocnicze:

i – zmienna licznikowa pętli, i N

Lista kroków:
K01: Dla i = 0,1,..., zk - zp, wykonuj Last[i] ← -1 ; wypełniamy całą tablicę Last wartościami -1
K02: Dla i = 0,1,...,|p| - 1, wykonuj Last[kod(p[i]) - zp] ← 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
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, 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 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 in - m, wykonuj K07...K14 ; pętlę wykonujemy dopóki okno wzorca mieści się w łańcuchu
K07:     jm - 1 ; w j ostatnia pozycja znaku we wzorcu p
K08:     Dopóki (j > -1) ∧ (p[j] = s[i+j]),
    wykonuj jj - 1
; sprawdzamy od końca zgodność znaków wzorca z oknem
K09:     Jeśli j > -1, to idź do K14 ; wzorzec pasuje do okna?
K10:     ppi ; zapamiętujemy pozycję okna
K11:     Pisz pp ; wyprowadzamy znalezioną pozycję
K12:     ii + 1 ; przesuwamy pozycję okna
K13:     Kontynuuj pętlę K06 ; i szukamy dalej
K14:     ii + max(1,j - Last[kod(s[i + j]) - zp]) - 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  

 

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 BM
// Data:  6.06.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------------

program prg;

uses Math;

const
  N  = 80;  // 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

  write(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.
Code::Blocks
// Wyszukiwanie wzorca algorytmem BM
// Data:  6.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
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;

  // 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;
}
Free Basic
' Wyszukiwanie wzorca algorytmem BM
' Data:  6.06.2008
' (C)2012 mgr Jerzy Wałaszek
'----------------------------------

Const N  = 80  ' 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
ABABAAAAABBBAAAAABABAABABAAABBBABAAAABABBABBAABABBBBAAAABBAABBBAAAAABBBBAAAAABAA
      ^                  ^                           ^           ^

 

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