Creeaza.com - informatii profesionale despre


Simplitatea lucrurilor complicate - Referate profesionale unice



Acasa » referate » informatica
Cautarea de siruri Knuth-Morris-Pratt

Cautarea de siruri Knuth-Morris-Pratt



Cautarea de siruri Knuth-Morris-Pratt

·       In anul 1970 Knuth, Morris si Pratt au inventat un algoritm de cautare in siruri de caractere care necesita un numar de comparatii de ordinul n chiar in cel mai defavorabil caz.

·       Noul algoritm se bazeaza pe observatia ca avansul modelului in cadrul sirului cu o singura pozitie la intalnirea unei nepotriviri, asa cum se realizeaza in metoda anterioara, pe langa o eficienta scazuta, conduce la pierderea unor informatii utile.


·       Astfel dupa o potrivire partiala a inceputului modelului cu sirul,

·       Intrucat se cunoaste partial sirul (pana in punctul baleat),

·       Daca avem cunostinte apriorice asupra modelului obtinute prin precompilare,

·       Le putem folosi pentru a avansa mai rapid in sir.

·       Acest lucru este pus in evidenta de exemplul urmator in care:

·       Se cauta modelul MARGINE in textul sursa;

·       Caracterele care se compara sunt cele subliniate;

·       Dupa fiecare nepotrivire, modelul este deplasat de-a lungul intregului drum parcurs intrucat deplasari mai scurte nu ar putea conduce la o potrivire totala [4.3.3.a].

------------------------------------------------------------

MAREA MARMARA SE MARGINESTE

MARGINE

   MARGINE

    MARGINE                         

     MARGINE

      MARGINE                                  [4.3.3.a]

         MARGINE

                  . . .

                 MARGINE

------------------------------------------------------------

·       Utilizand predicatele P si Q, algoritmul KMP poate fi formulat astfel [4.3.2.b]:

------------------------------------------------------------

  i:= 0; j:= 0;

  WHILE (j<m) AND (i<n) DO                    [4.3.3.b]

    BEGIN

      WHILE (j>=0) AND (s[i]<>p[j]) DO j:= d; 

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

    END;

------------------------------------------------------------

·       Formularea algoritmului este aproape completa, cu exceptia factorului d care precizeaza valoarea deplasarii.

·       Se subliniaza faptul ca in continuare Q(i-j) si P(i-j,j) sunt invariatii globali la care se adauga relatiile 0<i<n si 0<j<m.

·       Este foarte important de subliniat faptul ca de aici inainte nu i va fi indicele care precizeaza pozitia primului caracter al modelului in sir ci valoarea i-j.

·      


Indicele i precizeaza pozitia la care a ajuns procesul de cautare in sirul s (fig.4.3.3.a].

Fig. 4.3.3.a. Reprezentarea predicatelor P si Q in contextul cautarii KMP

·       Daca algoritmul se termina deoarece j = m, termenul P(i-j,j) al invariantului devine P(i-m,m), ceea ce conform relatiei care-l defineste pe P  indica o potrivire incepand de la pozitia i-m .

·       Daca la terminare i = n si j < m, invariantul Q(i) implica absenta vreunei potriviri.

·       In vederea determinarii valorii lui d trebuie lamurit rolul atribuirii j:= d.

·       Considerand prin definitie ca d < j atunci atribuirea j:= d reprezinta o deplasare a modelului spre dreapta cu j - d pozitii.

·       Este evident ca este de dorit ca deplasarea sa fie cat mai lunga si in consecinta d cat mai mic posibil.

·       Pentru a determina valoarea lui d se prezinta doua exemple.

------------------------------------------------------------

            Exemplul 4.3.3.a. Se considera situatia din figura 4.3.3.b.

.

                                                   

                         

 

       

Fig. 4.3.3.b. Deplasarea modelului in cadrul sirului s. Cazul 1.

·       Se observa ca deplasarea se poate face peste 3 pozitii intrucat nu mai pot apare alte potriviri. In aceste conditii  d = 0 , iar atribuirea  j = d produce deplasarea cu  j-d = 3  pozitii.

X-----------------------------------------------------------

·       Exemplul 4.3.3.b. Se considera situatia din figura 4.3.3.c.


                    

                          A    B     C     A    B     C      

                            A     B     C     A    B    E

                             

                                                                         

                 

                          A    B     C     A    B     C      

 

                                                   0     1     2     3      4     5          

    

                                                   d=2      j=2

Fig. 4.3.3.c. Deplasarea modelului in cadrul sirului s. Cazul 2.

·       In aceasta situatie deplasarea nu se poate face peste toata lungimea modelului intrucat mai exista o posibilitate de potrivire incepand de la i-2.

·       Acest lucru se intampla intrucat in cadrul modelului exista 2 subsecvente identice 'AB' de lungime 2.

·       Se noteaza cu d lungimea acestei subsecvente.

·       Dupa cum se observa din figura 4.3.3.c, deplasarea modelului la dreapta se poate face numai peste j-d (5 - 2 = 3) pozitii deoarece primele d pozitii ale modelului coincid cu cele d pozitii ale textului care preced indicele i (care indica neconcordanta).

------------------------------------------------------------

·       In concluzie:

a) Initial exista o potrivire intre sirul s si modelul p incepand de la pozitia i-j pe lungime j adica este valabil invariantul  P(i-j,j) & Q(i-j).

b) Dupa efectuarea deplasarii avem din nou o potrivire la i-d de lungime d adica este valabil invariantul  P(i-d,d) & Q(i-d).

·       Aceasta situatie rezulta din observatia ca in model exista doua subsecvente identice de lungime d una la inceputul modelului alta de la pozitia j-d la j-1.

·       Formal acest lucru este precizat de relatia [4.3.3.c].

------------------------------------------------------------

     p0 pd-1 = pj-d pj                                                               [4.3.3.c]

------------------------------------------------------------

·       Pentru ca lucrurile sa se desfasoare corect este necesar ca lungimea lui d sa fie maxima, adica sa avem cea mai lunga subsecventa care indeplineste conditiile precizate.

·       Rezultatul esential este acela ca valoarea lui d este determinata exclusiv din structura modelului si nu depinde de textul propriu-zis.



·       Din cele expuse rezulta ca pentru a-l determina pe d:

·       Pentru fiecare valoare a lui j

·       Se cauta in model cel mai mare d, adica cea mai lunga secventa de caractere a modelului care precede imediat pozitia j si care se potriveste ca un numar egal de caractere de la inceputul modelului.

·       Se noteaza valoarea d pentru un anumit j cu dj.

·       Intrucat valorile dj depind numai si numai de model, inaintea cautarii propriu-zise poate fi construit un tablou d cu aceste valori printr-un proces de precompilare a modelului.

·       Desigur acest efort merita sa fie depus daca  m << n. In continuare se prezinta trei situatii particulare de determinare a valorii deplasamentului d.

------------------------------------------------------------

·       Exemplul 4.3.3.c. Se considera situatia din figura 4.3.3.d.

                                 i - j                                i

                    

       s                        A     A    A    A    A     A    A    A        

  

       p

     

      

                                   0    1     2     3     4     5              d5 = 4   T  j = d5 = 4

       p                              

                              

j=4

 
                                              0     1     2     3     4     5  

                               j = 4

Fig. 4.3.3.d. Determinarea deplasamentului d . Cazul 1.

------------------------------------------------------------

·       Exemplul 4.3.3.d. Se considera situatia din figura 4.3.3.e.

                           i - j                                i


 s

                

 p                            

                            0     1     2     3     4      5           d5 = 0   T  j = d5 = 0

 p                                                   

                                                j = 0         0     1     2     3     4     5  

      

Fig. 4.3.3.e. Determinarea deplasamentului d. Cazul 2.

------------------------------------------------------------

·       Exemplul 4.3.3.e. Se considera situatia din figura 4.3.3.f.

 

                           i - j                                i


  s                

  p                                                

                            0     1     2      3     4     5           d5 = 0   T  j = d5 = 0

                                                                j = 5

  p                                                       

                                                                 0     1     2     3     4     5         

                                                               j = 0

  p                                                              

                                                                       0     1     2      3      4     5         

            

                                                                    j = -1                       d5 = -1

Fig. 4.3.3.f. Determinarea deplasamentului d. Cazul 3.

·       Ultimul exemplu sugereaza ca se poate merge mai departe cu deplasarile si ca in loc sa se realizeze deplasarea peste 5 pozitii, in aceasta situatie se poate face peste intregul model deci  d= -1  iar deplasarea se face peste 5 – (–1) = 6 pozitii.

·       Acest lucru este posibil deoarece primul caracter al modelului este identic cu ultimul sau caracter.

·       Intrucat s-a constatat necoincidenta pentru ultimul caracter al modelului, rezulta ca nu poate exista o coincidenta nici in cazul primului caracter al acestuia (identic cu ultimul), deci deplasarea se poate realiza peste el.

·       In aceste conditii, calculul lui dj care presupune cautarea celor mai lungi secvente care se potrivesc in baza relatiei [4.3.3.c], poate fi completat dupa cum urmeaza.

·       Daca se constata ca  d= 0 si  p= p, atunci se poate face d= -1 indicand deplasarea integrala a modelului fata de pozitia sa curenta in cadrul sirului s.

------------------------------------------------------------

·       In figura 4.3.3.g. apare un tablou demonstrativ in care pentru mai multe siruri model  p  se precizeaza structura tabloului d asociat adica valorile dj corespunzatoare caracterelor modelului rezultate in urma precompilarii.

·       In stanga tabelului apare modelul p iar in dreapta tabelul d asociat.

 

p

d

0

1

2

3

4

5

6

0

1

2

3

4

5

6

 

A



-1

 

A

A

-1

-1

 

A

A

A

A

A

B

-1

-1

-1

-1

-1

4

 

A

B

C

A

B

C

-1

0

0

-1

0

0

 

A

B

C

A

B

C

D

-1

0

0

-1

0

0

3

 

A

B

C

A

B

D

-1

0

0

-1

0

2



 

A

B

C

D

E

F

-1

0

0

0

0

0

 

A

B

C

D

E

A

-1

0

0

0

0

-1

 

M

A

R

G

I

N

E

-1

0

0

0

0

0

0

 

 

Fig.  4.3.3.g. Exemple de precompilare a unor modele

·       Programul care implementeaza cautarea de siruri Knuth-Morrison-Pratt apare in secventa [4.3.3.d].

------------------------------------------------------------

CONST mmax=;

      nmax=;

VAR m,n: integer;

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

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

   d: ARRAY[0..mmax‑1] OF integer;

FUNCTION CautareKMP(VAR poz: integer): boolean;

  VAR i,j,k: integer;

  BEGIN

    *citire sir in s

    *citire model in p

     j:= 0; k:= ‑1; d[0]:= ‑1; 

     WHILE j<m‑1 DO                                   

       BEGIN

         WHILE (k>=0) AND (p[j]<>p[k]) DO k:= d[k];

           j:= j+1; k:= k+1;

           IF p[j]=p[k] THEN d[j]:= d[k]

               ELSE d[j]:= k

       END;                             [4.3.3.d]

     i:= 0; j:= 0; 

     WHILE (j<m) AND (i<n) DO

       BEGIN

         WHILE (j>=0) AND (s[i]<>p[j]) DO j:= d[j];

            j:= j+1;

            i:= i+1;           

       END;

     poz:= i‑m;

     CautareKMP:= j=m

  END;

------------------------------------------------------------

·       Programul KMP consta din 4 parti:

·       Prima realizeaza citirea sirului in care se face cautarea,

·       A doua realizeaza citirea modelului,

·       A treia precompileaza modelul si calculeaza valorile dj,

·       A patra implementeaza cautarea propriu-zisa.

·       Se precizeaza ca partea a treia fiind practic o cautare de siruri se implementeaza tot ca si o cautare  KMP.

·       Analiza cautarii KMP.

·       Analiza exacta a performantei cautarii de siruri Knuth-Morrison-Pratt este asemeni algoritmului foarte sofisticata.

·       Inventatorii demonstreaza ca numarul de comparatii de caractere este de ordinul  n + m , ceea ce reprezinta o imbunatatire substantiala fata de  m * n .

·       De asemenea se subliniaza faptul ca pointerul  i care baleeaza sirul nu merge niciodata inapoi spre deosebire de cautarea directa, unde dupa o potrivire partiala se reia cautarea cu modelul deplasat cu o pozitie, chiar daca o parte din caracterele sirului au fost deja parcurse.

·       Acest avantaj permite aplicarea acestei metode si in cazul unor prelucrari secventiale.

 








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




Taxonomia unitatilor de procesare a datelor
Aplicatia CONTABWIN
Implementarea tipului de date abstract sir
Accelerarea procesului de adunare/scadere in virgula flotanta
CALCULUL CLIENT/SERVER
Cautarea de siruri directa
Marketingul traditional– rezultat al practicii de marketing
E-mail-ul ca instrument de marketing


Termeni si conditii
Contact
Creeaza si tu