Creeaza.com - informatii profesionale despre


Evidentiem nevoile sociale din educatie - Referate profesionale unice
Acasa » referate » informatica
Cautarea de siruri Boyer-Moore

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  dx 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

x

x

x

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

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

Pentru caracterele care nu sunt in model respectiv pentru ultimul caracter al modelului,  dx  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[pm-1] pozitii, valoare care este de regula mai mare ca 1.

Se precizeaza faptul ca  pm-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 pm-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 si Q [4.3.4.b].

P(i,j)= Ak: j  k <  m:si-j+k = pk [4.3.4.b]

Q(i) = Ak: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: d1 (tabloul specific cautarii BM) si d2 (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.







Politica de confidentialitate







creeaza logo.com Copyright © 2023 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Proiecte

vezi toate proiectele
PROIECT DE LECTIE CLASA A II-A, Educatie plastica, Tehnica marmorata
PROIECT DIDACTIC 5-7 ani activitate matematica - „Cum este si cum nu este aceasta piesa”
Proiect Circuite Digitale
Organizarea si conducerea procesului tehnologic proiectat

Lucrari de diploma

vezi toate lucrarile de diploma
LUCRARE DE DIPLOMA - Rolul asistentului medical in ingrijirea pacientului cu A.V.C.
Spatiul romanesc, intre diplomatie si conflict in Evul Mediu
Lucrare de diploma managementul firmei “diagnosticul si evaluarea firmei”
Lucrare de diploma Facultatea de Textile – Pielarie - Tehnologia confectiilor din piele si inlocuitori - PROIECTAREA CONSTRUCTIV TEHNOLOGICA A UNUI PR

Lucrari licenta

vezi toate lucrarile de licenta
Lucrare de licenta contabilitate si informatica de gestiune - politici si tratamente contabile privind leasingul (ias 17). prevalenta economicului asupra juridicului
Lucrare de licenta educatie fizica si sport - sistemul de selectie in jocul de handbal pentru copii de 10-11 ani in concordanta cu cerintele handbalul
Lucrare de licenta - cercetare si analiza financiara asupra deseurilor de ambalaje la sc.ambalaje sa
LUCRARE DE LICENTA - Asigurarea calitatii la firma Trans

Lucrari doctorat

vezi toate lucrarile de doctorat
Diagnosticul ecografic in unele afectiuni gastroduodenale si hepatobiliare la animalele de companie - TEZA DE DOCTORAT
Doctorat - Modele dinamice de simulare ale accidentelor rutiere produse intre autovehicul si pieton
LUCRARE DE DOCTORAT ZOOTEHNIE - AMELIORARE - Estimarea valorii economice a caracterelor din obiectivul ameliorarii intr-o linie materna de porcine

Proiecte de atestat

vezi toate proiectele de atestat
Lucrare atestat informatica - „administrarea gradinii botanice”
Lucrare atestat Tehnician operator tehnica de calcul - Sursa de tensiune cu tranzistoare npn
ATESTAT PROFESIONAL LA INFORMATICA - programare FoxPro for Windows
Proiect atestat tehnician in turism - carnaval la venezia

Aplicatia CONTABWIN
OBIECTE TIP RAPORT
Alte tipuri de produse software
SISTEME DE OPERARE
Cautarea de siruri Boyer-Moore
Analiza de senzitivitate a unei probleme de programare liniara
Recursivitate
Norton Commander - cum se utilizeaza



Termeni si conditii
Contact
Creeaza si tu