Cautarea de siruri Boyer-Moore

Cautarea de siruri Boyer-Moore

Metoda ingenioasa de cautare KMP conduce la beneficii numai daca nepotrivirea dintre sir si model a fost precedata de o potrivire partiala de o anumita lungime.

Numai in acest caz deplasarea modelului se realizeaza peste mai mult de o pozitie.

Din pacate aceasta situatie in realitate este mai degraba exceptia decat regula; potrivirile apar mult mai rar ca si nepotrivirile.

In consecinta, beneficiile acestei metode sunt reduse in marea majoritate a cautarilor normale de texte.

Metoda de cautare inventata in 1975 de R.S. Boyer si J.S. Moore imbunatateste performanta atat pentru situatia cea mai defavorabila cat si in general.

Cautarea BM, dupa cum mai este numita, este bazata pe ideea neobisnuita de a incepe compararea caracterelor de la sfarsitul modelului si nu de la inceput.

Ca si in cazul metodei KMP, modelul este precompilat anterior intr-un tablou d.

Astfel, pentru fiecare caracter x al setului de caractere, se noteaza cu  d_x distanta dintre cea mai din dreapta aparitie a lui  x  in cadrul modelului si sfarsitul modelului (fig.4.3.4.a.).

modelul p:

0 1 2

Fig. 4.3.4.a. Determinarea valorii  d_x  corespunzatoare caracterului  x  al
modelului

Valoarea  d_x  se trece in tabloul d in pozitia corespunzatoare caracterului x.

Pentru caracterele care nu sunt in model respectiv pentru ultimul caracter al modelului,  d_x  se face egal cu lungimea totala a modelului.

In continuare, se presupune ca in procesul de comparare al sirului cu modelul a aparut o nepotrivire intre caracterele corespunzatoare.

In aceasta situatie modelul poate fi imediat deplasat spre dreapta cu   d[p_m-1] pozitii, valoare care este de regula mai mare ca 1.

Se precizeaza faptul ca  p_m-1  este caracterul din sirul baleat s, corespunzator ultimului caracter al modelului la momentul considerat, indiferent de locul in care s-a constatat nepotrivirea (figura 4.3.4.b.).

nepotrivire

s 

potrivire

p

0 1 2 3 4 m -1

Fig. 4.3.4.b. Comparare sir - model pentru determinarea lui p_m-1

Daca caracterul  p _m-1  nu apare in model, deplasarea este mai mare si anume cu intreaga lungime a modelului.

Exemplul din secventa [4.3.4.a.] evidentiaza acest proces.

6

5 MARGINE

6 MARGINE

MARGINE [4.3.4.a]

MARGINE

6543217

MAREA MARMARA SE MARGINESTE

Deoarece compararea individuala a caracterelor se realizeaza de la dreapta spre stanga, este mai convenabila urmatoarea formulare a predicatelor P si Q [4.3.4.b].

P(i,j)= A_k: j  k <  m:s_i-j+k = p_{k [4.3.4.b]}

Q(i) = A_k:0  k < i: ~P(k,0)

Interpretarea grafica a a noii formulari a predicatelor in cauza apare in figura 4.3.4.c.

Dupa cum se observa, exista o potrivire incepand de la  i  spre stanga
cu ultimele  m - j  caractere ale modelului adica incepand de la pozitia j (spre dreapta) a modelului, pana la sfarsitul acestuia.

Cand  j = 0 , avem o potrivire de la  i - m  cu  m - 0 caractere, deci cu modelul integral (de la pozitia 0 a modelului).

Fig. 4.3.4.c. Interpretarea predicatelor P si Q in cautarea BM

Aceste predicate sunt utilizate in formularea urmatoare a algoritmului BM [4.3.4.c]:

i:= m; j:= m;

WHILE (j>0) AND (i<n) DO

BEGIN [4.3.4.c]

j:= m; k:= i;

WHILE (j>0) AND (s[k-1]=p[j-1]) DO

BEGIN

k:= k-1;

j:= j-1

END;

i:= i+d[ORD(s[i-1])]

END;

Indicii implicati satisfac urmatoarele relatii: 0 < j < m si 0 < i, k < n.

Astfel terminarea algoritmului cu j = 0 impreuna cu  P(k-j,j), implica  P(k,0) adica o potrivire incepand de la pozitia k spre dreapta, de m caractere, unde  k = i - m.

Terminarea algoritmului cu  j > 0  implica  i = n . In acest caz  Q(i-m) devine Q(n-m) indicand absenta potrivirii.

Programul urmator [4.3.4.d] implementeaza strategia Boyer-Moore intr-un context similar cautarii KMP.

CONST mmax=;

nmax=; [4.3.4.c]

VAR m,n: integer;

p: ARRAY[0..mmax‑1] OF char;

s: ARRAY[0..nmax‑1] OF char;

d: ARRAY[0..255] OF integer;

FUNCTION CautareBM(VAR poz: integer): boolean;

VAR i,j,k: integer;

BEGIN

*citire sir

*citire model

FOR i:=0 TO 255 DO d[CHR(i)]:= m;

FOR j:=0 TO m‑2 DO d[p[j]]:= m‑j‑1;

i:= m; j:= m;

WHILE (j>0) AND (i<=n) DO

BEGIN

j:= m;

k:= i;

WHILE (j>0) AND (s[k‑1]=p[j‑1]) DO

BEGIN

k:= k‑1;

j:= j‑1

END;

IF j>0 THEN i:= i+d[s[i‑1]]

END;

poz:= i‑m;

CautareBM:= j=0

END;

Analiza cautarii Boyer-Moore

Autorii cautarii BM, au demonstrat proprietatea remarcabila ca in toate cazurile, cu exceptia unora special construite, numarul de comparatii este substantial mai redus decat n.

In cazul cel mai favorabil cand ultimul caracter al modelului nimereste intotdeauna in sir peste un caracter diferit de cele ale modelului, numarul de comparatii este n/m .

Autorii indica anumite directii de imbunatatire a performantelor algoritmului.

Una din ele este aceea de a combina strategia BM care realizeaza o deplasare substantiala in prezenta unei nepotriviri cu strategia KMP care permite o deplasare mai substantiala dupa detectia unei potriviri (partiale).

Aceasta metoda necesita doua tablouri precalculate: d₁ (tabloul specific cautarii BM) si d₂ (tabloul corespunzator cautarii KMP).

Toate acestea conduc la complicarea algoritmului si la cresterea regiei sale prin precompilarea tablourilor.

De fapt in multe cazuri trebuie analizata oportunitatea implementarii unor extensii sofisticate care desi rezolva anumite situatii punctuale, pot avea drept consecinta deteriorarea performantelor de ansamblu prin cresterea excesiva a regiei algoritmului implicat.