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
 Folosirea altor instrumente de evaluare (investigatia, proiectul, protofoliul)
 PROIECT DIDACTIC - Cunoasterea numarului cinci
 Proiect iluminat electric si instalatii
 Organizarea si conducerea procesului tehnologic proiectat

Lucrari de diploma

vezi toate lucrarile de diploma
 PROIECT DE DIPLOMA CHIRURGIE ORO-MAXILO-FACIALA - SUPURATIILE LOJELOR PROFUNDE DE ETIOLOGIE ODONTOGENA
 ACTIUNEA DIPLOMATICA A ROMANIEI LA CONFERINTA DE PACE DE LA PARIS (1946-1947)
 LUCRARE DE DIPLOMA MANAGEMENT - MANAGEMENTUL CALITATII APLICAT IN DOMENIUL FABRICARII BERII. STUDIU DE CAZ - FABRICA DE BERE SEBES
 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 - ANALIZA EFICIENTEI ECONOMICE – CAI DE CRESTERE LA S.C. CONSTRUCTIA S.A TG-JIU
 Lucrare de licenta educatie fizica si sport - studiu asupra imbunataȚirii motricitaȚii in lectia de educatie fizica la clasele a v-a de la &
 Lucrare de licenta - cercetare si analiza financiara asupra deseurilor de ambalaje la sc.ambalaje sa
 LUCRARE DE LICENTA MANAGEMENT CRESTEREA VANZARILOR PRIN METODA IMBUNATATIRII SERVICIILOR CATRE CLIENTI

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
 ATESTAT LA INFORMATICA - Baza de date relationala aplicata intr-o biblioteca scolara
 LUCRARE DE ATESTAT ELECTRONIST - TEHNICA DE CALCUL - Placa de baza
 GENERATOR DE TESTE GRILA - Proiect atestat Visual FOX PRO
 Proiect atestat - comercializarea produselor turistice balneare in statiunea sangeorz - bai

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