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

          0                                                                                                                         

         

  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.








Politica de confidentialitate

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


Proiecte

vezi toate proiectele
 PROIECT DE LECTIE Clasa: I Matematica - Adunarea si scaderea numerelor naturale de la 0 la 30, fara trecere peste ordin
 Proiect didactic Grupa: mijlocie - Consolidarea mersului in echilibru pe o linie trasata pe sol (30 cm)
 Redresor electronic automat pentru incarcarea bateriilor auto - proiect atestat
 Proiectarea instalatiilor de alimentare ale motoarelor cu aprindere prin scanteie cu carburator

Lucrari de diploma

vezi toate lucrarile de diploma
 Lucrare de diploma - eritrodermia psoriazica
 ACTIUNEA DIPLOMATICA A ROMANIEI LA CONFERINTA DE PACE DE LA PARIS (1946-1947)
 Proiect diploma Finante Banci - REALIZAREA INSPECTIEI FISCALE LA O SOCIETATE COMERCIALA
 Lucrare de diploma managementul firmei “diagnosticul si evaluarea firmei”

Lucrari licenta

vezi toate lucrarile de licenta
 CONTABILITATEA FINANCIARA TESTE GRILA LICENTA
 LUCRARE DE LICENTA - FACULTATEA DE EDUCATIE FIZICA SI SPORT
 Lucrare de licenta stiintele naturii siecologie - 'surse de poluare a clisurii dunarii”
 LUCRARE DE LICENTA - Gestiunea stocurilor de materii prime si materiale

Lucrari doctorat

vezi toate lucrarile de doctorat
 Doctorat - Modele dinamice de simulare ale accidentelor rutiere produse intre autovehicul si pieton
 Diagnosticul ecografic in unele afectiuni gastroduodenale si hepatobiliare la animalele de companie - TEZA DE DOCTORAT
 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- Tehnician operator tehnica de calcul - Unitati de Stocare
 LUCRARE DE ATESTAT ELECTRONIST - TEHNICA DE CALCUL - Placa de baza
 ATESTAT PROFESIONAL LA INFORMATICA - programare FoxPro for Windows
 Proiect atestat tehnician in turism - carnaval la venezia




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