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

 

A



 

A

A

 

A

A

A

A

A

B

 

A

B

C

A

B

C

 

A

B

C

A

B

C

D

 

A

B

C

A

B

D



 

A

B

C

D

E

F

 

A

B

C

D

E

A

 

M

A

R

G

I

N

E

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 © 2021 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Proiecte

vezi toate proiectele
 SCHITA DE PROIECT DIDACTIC GEOGRAFIE CLASA: a IX-a - Unitatile majore ale reliefului terestru
 PROIECT DIDACTIC 5-7 ani Educatia limbajului - Cate cuvinte am spus?
 Proiect atestat Tehnician Electronist - AMPLIFICATOARE ELECTRONICE
 Proiect - masurarea si controlul marimilor geometrice

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)
 LUCRARE DE DIPLOMA MANAGEMENT - MANAGEMENTUL CALITATII APLICAT IN DOMENIUL FABRICARII BERII. STUDIU DE CAZ - FABRICA DE BERE SEBES
 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 - ANALIZA EFICIENTEI ECONOMICE – CAI DE CRESTERE LA S.C. CONSTRUCTIA S.A TG-JIU
 Lucrare de licenta sport - Jocul de volei
 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
 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 MATEMATICA-INFORMATICA - CALUTUL INTELIGENT
 Proiect atestat Tehnician Electronist - AMPLIFICATOARE ELECTRONICE
 ATESTAT PROFESIONAL LA INFORMATICA - programare FoxPro for Windows
 ATESTAT PROFESIONAL TURISM SI ALIMENTATIE PUBLICA, TEHNICIAN IN TURISM




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