Creeaza.com - informatii profesionale despre


Cunostinta va deschide lumea intelepciunii - Referate profesionale unice



Acasa » referate » informatica
Cautarea de siruri directa

Cautarea de siruri directa



Cautarea de siruri directa

O maniera frecvent intalnita de cautare este asa numita cautare de siruri directa ('string search').

Formularea problemei:



Se da un tablou s de n elemente si un tablou p de m elemente, unde 0<m<n declarate astfel [4.3.2.a]:

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

p: ARRAY[0..m-1] OF char; [4.3.2.a]

Cautarea se siruri are drept scop stabilirea primei aparitii a lui p in s.

De regula, s poate fi privit ca un text, iar p ca un cuvant model ('pattern') a carui prima aparitie se cauta in textul s.

Aceasta este o operatie fundamentala in toate sistemele de prelucrare a textelor si in acest sens este de mare interes gasirea unor algoritmi cat mai eficienti.

Cea mai simpla metoda de cautare este asa numita cautare de siruri directa.

Rezultatul unei astfel de cautari este un indice i care precizeaza aparitia unei coincidente intre model si sir.

Acest lucru este formalizat de predicatul P(i,j) [4.3.2.b].

P(i,j)<= Ak:0  k < j:si+k = pk  [4.3.2.b]

Predicatul P(i,j) precizeaza faptul ca exista o coincidenta intre:

Sirul s (incepand cu indicele i)

Sirul p (incepand cu indicele 0) pe o lungime de j caractere (fig. 4.3.2.a).

i i + j - 1

s

p

0 1 2 j - 1

j caractere

Fig.4.3.2.a. Reprezentarea grafica a predicatului P(i,j)

Este evident ca indexul i care rezulta din cautarea directa de siruri trebuie sa satisfaca predicatul P(i,m).

Aceasta conditie nu este insa suficienta.

Deoarece cautarea trebuie sa furnizeze prima aparitie a modelului, P(k,m) trebuie sa fie fals pentru toti k < i .

Se noteaza aceasta conditie cu Q(i)[4.3.2.c].

Q(i) = Ak: 0  k < i:  ~P(k,m)  [4.3.2.c]



Punerea problemei sugereaza formularea cautarii directe de siruri ca si o iteratie de comparatii redactata in termenii predicatelor Q respectiv P.

Astfel implementarea lui Q(i) conduce la secventa [4.3.2.d]:

i:= -1;

REPEAT

i:= 1+1; [4.3.2.d]

gasit:= P(i,m)

UNTIL gasit OR (i=n-m);

Calculul lui P rezulta in continuare ca si o iteratie de comparatii de caractere individuale.

Rafinarea secventei anterioare conduce de fapt la implementarea cautarii directe de siruri ca o repetitie intr-o alta repetitie [4.3.2.e].

FUNCTION CautareDirecta(VAR poz: integer): boolean;

VAR i,j: integer;

BEGIN

i:= ‑1;

REPEAT [4.3.2.e]

i:= i+1; j:= 0;

WHILE (j<m)AND(s[i+j]=p[j]) DO j:= j+1

UNTIL (j=m)OR(i=n‑m);

poz:= i;

CautareDirecta:= j=m

END;

Termenul j = m din conditia de terminare, corespunde lui gasit deoarece el implica P(i,m).

Termenul i=n-m implica Q(n-m), deci non existenta vreunei coincidente in cadrul sirului.

Analiza cautarii de siruri directe.

Algoritmul lucreaza destul de eficient daca se presupune ca nepotrivirea in procesul de cautare apare cel mult dupa cateva comparatii in cadrul buclei interioare.

Astfel pentru un set de 128 de caractere se poate presupune ca nepotrivirea apare dupa inspectarea a 1 sau 2 caractere.

Cu toate acestea in cazul cel mai nefavorabil, degradarea performantei este ingrijoratoare.

Astfel daca spre exemplu sirul s este format din n-1 caractere 'A' urmate de un singur 'B',

Iar modelul consta din m-1 caractere 'A' urmate de un 'B',

In acest caz este necesar un numar de comparatii de ordinul n  m pentru a gasi coincidenta la sfarsitul sirului.

Din fericire exista metode care imbunatatesc radical comportarea algoritmului in aceasta situatie.

Tehnicile de cautare care sunt prezentate in continuare materializeaza acest deziderat.





loading...




Politica de confidentialitate

.com Copyright © 2020 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Proiecte

vezi toate proiectele
 PROIECT DE LECTIE CLASA: a X a EDUCATIE MUZICALA - OPERA IN GERMANIA SI RUSIA
 PROIECT DIDACTIC 3-5 ani Limba si comunicare - Strugurele, de Maria Gaitan
 Proiect instalatii electrice - Sa se proiecteze instalatia electrica si de forta a unei microintreprinderi la alegerea studentului
 PROIECT - Ingineria reglarii automate - sistemul de reglare automata a unei actionari cu motor electric

Lucrari de diploma

vezi toate lucrarile de diploma
 LUCRARE DE DIPLOMA - Rolul asistentului medical in ingrijirea pacientului cu A.V.C.
 Relatiile diplomatice dintre Romania si Austro- Ungaria din a doua jumatate a secolului al XIX-lea
 Lucrare de diploma managementul firmei “diagnosticul si evaluarea firmei”
 Lucrare de diploma tehnologia confectiilor din piele si inlocuitor - proiectarea constructiv tehnologica a unui produs de incaltaminte tip cizma scurt

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 - studiu asupra imbunataȚirii motricitaȚii in lectia de educatie fizica la clasele a v-a de la &
 Lucrare de licenta ecologie si protectia mediului - aspecte ecologice privind fauna de orthoptere si mantide din parcul national muntii macinului
 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
 PROIECT ATESTAT INFORMATICA - GESTIONAREA STOCULUI UNEI FARMACII
 LUCRARE DE ATESTAT ELECTRONIST - TEHNICA DE CALCUL - Placa de baza
 Evidenta a clientilor dar si a serviciilor in Visual Fox pro 9 - Lucrare de atestat
 Lucrare atestat Tehnician in turism - CALITATEA SERVICIILOR TURISTICE




SISTEMUL INFORMATIC , INSTRUMENT AL MANAGEMENTULUI ORGANIZATIILOR ECONOMICO-SOCIALE
SISTEM INFORMATIONAL SI SISTEM INFORMATIC
CALCULUL CLIENT/SERVER
Caracteristicile celor patru tipuri de sisteme informationale
Cautarea de siruri directa
Microcontrolerul AT89C52
Sumatoarele paralele pe principiul selectarii prin transport a sumei
Elementele de baza ale unui template Joomla




Termeni si conditii
Contact
Creeaza si tu