cautare peste siruri

28
Cautare peste siruri problema cautarea naiva algoritmul Knuth-Morris-Pratt algoritmul Boyer-Moore algoritmul Rabin-Karp cazul mai multor pattern-uri expresii regulate

Upload: kendra

Post on 19-Jan-2016

110 views

Category:

Documents


3 download

DESCRIPTION

Cautare peste siruri. problema cautarea naiva algoritmul Knuth-Morris-Pratt algoritmul Boyer-Moore algoritmul Rabin-Karp cazul mai multor pattern-uri expresii regulate. Tipul de date abstract String. obiecte: siruri de elemente apartinind unui tip abstract Character operatii - PowerPoint PPT Presentation

TRANSCRIPT

Page 1: Cautare peste siruri

Cautare peste siruri

problema cautarea naiva algoritmul Knuth-Morris-Pratt algoritmul Boyer-Moore algoritmul Rabin-Karp cazul mai multor pattern-uri expresii regulate

Page 2: Cautare peste siruri

Tipul de date abstract String

obiecte: siruri de elemente apartinind unui tip abstract Character

operatii

• inserarea unui subsir

• eliminarea unui subsir

• concatenarea a doua siruri

• regasirea unui sir ca subsir al altui sir

– sirul in care se cauta se numeste subiect; il notam s[0..n-1]

– sirul a carui aparitie este cautata in subiect se numeste “pattern”; il notam p[0..m-1]

Page 3: Cautare peste siruri

Cautare naiva: proprietati

nu necesita preprocesare; spatiu suplimentar: O(1); totdeauna deplaseaza “pattern”-ul cu o unitate la dreapta;

comparatiile pot fi facute in orice ordine; complexitatea cautarii: O(mn) numarul mediu de comparatii intre caractere: 2n .

s

p≠

Page 4: Cautare peste siruri

Cautarea naiva: algoritmfunction pmNaiv(s, n, p, m)

begin

i -1while (i < n-m) do

i i+1j 0while (s[i+j] = p[j]) do

if (j = m-1)

then return i

else j j+1return -1

end

Page 5: Cautare peste siruri

Algoritmul KMP: proprietati

realizeaza comparatiile de la stanga la dreapta; preprocesare in timpul O(m) cu spatiu suplimentar O(m); complexitatea timp a cautarii: O(n+m) (independent de

marimea alfabetului);

Page 6: Cautare peste siruri

Algoritmul KMP: ideea

a b a b * …

a b a b c

≠?

Page 7: Cautare peste siruri

Algoritmul KMP: ideea

subiect

pattern

i

j

. . .

. . .

subiect

pattern

i

j k0

. . . . . .

. . . . . . . . .

subiect

pattern

j k0

. . . . . .

. . . . . . . . .

i

Page 8: Cautare peste siruri

Terminologie

prefixp[0..k-1]

sufixp[j-1..j-k]

“bordura” (border)prefixul de lungime k = sufixul de lungime k

functia esecf[j] = k ddaca ce mai lata bordura a lui p[0..j-1] are latimea k

Page 9: Cautare peste siruri

Algoritmul KMP: functia esec

procedure determinaFctEsec(p,m,f)begin

f[0] -1for j 1 to m-1 do

k f[j-1]while (k -1 and p[j-1] p[k]) do

k f[k]f[j] k+1

endAnaliza: timpul in cazul cel mai nefavorabil O(m)

Page 10: Cautare peste siruri

Algoritmul KMP: functia esec: exemplu

p = abaabaaabc

50 1 2 3 4 6 7 8a b a a b a a a b c 9

-1

j 0 1 2 3 4 5 6 7 8 9

p[j] a b a a b a a a b c

f[j] -1 0 0 1 1 2 3 1 1 2

Page 11: Cautare peste siruri

Algoritmul KMP

function KMP(s, n, p, m, f)

begin

i 0j 0while (i < n) do

while (j -1 and s[i] p[j])doj f[j]

if (j = m-1)

then return i-m+1

else i i+1 j j+1

return -1

end

Analiza: timpul in cazul cel mai nefavorabil O(2n) – numarul total de executii ale buclei interioare while este <= numarul de incrementari ale lui j (incrementarea lui j are loc inafara buclei)

Page 12: Cautare peste siruri

Algoritmul Boyer-Moore: proprietati

comparatiile sunt realizate de la dreapta la stanga; preprocesare in timpul O(km) si spatiu suplimentar O(k),

unde k = #Character; complexitatea timp a cautarii: O(mn); 3n comparatii de caractere in cazul cel mai nefavorabil pentru

un “pattern” neperiodic; cea mai buna performanta: O(n / m) .

Page 13: Cautare peste siruri

Algoritmul Boyer-Moore: ideea

0 1 2 3 4 5 6 7 8 9 10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

V I S U L U N E I N O P T I D E I A R N A

I A R0 1 2

I A R0 1 2

I A R0 1 2

I A R0 1 2

I A R0 1 2

I A R0 1 2

I A R0 1 2

I A R0 1 2

≠ ≠ ≠ ≠ ≠ ≠ ≠ ===

012345678910

Page 14: Cautare peste siruri

Algoritmul Boyer-Moore: functia salt

cazul cind caracterul apare o singura data in pattern

AMAR

MAR

salt[A] = 1 cazul cind caracterul apare de mai multe ori in pattern

SAMAR

AMAR

salt[A] = 1

Page 15: Cautare peste siruri

Algoritmul Boyer-Moore: salt

i+salt[‘A’]i

u‘A’

‘A’ ‘B’ ‘A’ nu e in u

j salt[‘A’] ≥ m-j

i+m-ji

u‘A’

‘A’ ‘B’ ‘A’ e in u

j salt[‘A’] < m-j

Page 16: Cautare peste siruri

Algoritmul Boyer-Moore

function BM(s, n, p, m, salt)begin

i m-1; j m-1repeat

if (s[i] = p[j])then i i-1

j j-1else

if (m-j) > salt[s[i]]then i i+m-jelse i i+salt[s[i]]j m-1

until (j<0 or i>n-1)if (j<0)then return i+1else return -1

end

Page 17: Cautare peste siruri

Algoritmul Rabin-Karp: proprietati

utilizeaza o functie “hash”; preprocesare in timpul O(m) si spatiu suplimentar O(1); cautare in timpul O(mn); timpul mediu: O(n+m) .

Page 18: Cautare peste siruri

Algoritmul Rabin-Karp: ideea

021 ]1[...]1[]0[ dmpdpdpy mm

021 ]1[...]1[][ dmisdisdisx mmi

011 ][)][( dmisddisxx m

ii

0 m-1

p

i i+m-1

s

i+1 i+m

s

Page 19: Cautare peste siruri

Algoritmul Rabin-Karpfunction RK(s, n, p, m)begin

dlam1 1for i 1 to m-1 do dlam1 (d*dlam1)%qhp 0for i 0 to m-1 do hp (d*hp+index(p[i]))%qhs 0for i 0 to m-1 do hs (d*hs+index(s[i]))%qi 0while (i < n-m) do

if (hp = hs and equal(p, s, m, i))then return ihs (hs+d*q-index(s[i])*dlam1)%qhs (d*hs+index(s[i+m]))%qi i+1

return -1end

Page 20: Cautare peste siruri

Algoritmul Rabin-Karp: implementare C

#define REHASH(a, b, h) ((((h)-(a)*d) << 1) (b))int RK(char *p, int m, char *s, int n) { long d, hs, hp, i, j; /* Preprocesare */ for (d = i = 1; i < m; ++i) d = (d << 1); for (hp = hs = i = 0; i < m; ++i) { hp = ((hp << 1) + p[i]); hs = ((hs << 1) + s[i]); } /* Cautare */ i = 0; while (i <= n-m) { if (hp == hs && memcmp(p, s + i, m) == 0) return i; hs = REHASH(s[i], s[i + m], hs); ++i; } return -1;}

Page 21: Cautare peste siruri

Mai multe pattern-uri

0

1 2 3 4 5

6 7 8

9 10

A

B C D E

C D E

BC

• patternul desemneaza o multime de siruri de cautat• exemplu: {ABCDE, CDE, BC}

Page 22: Cautare peste siruri

Mai multe pattern-uri (continuare)

0

1 2 3 4 5

6 7 8

9 10

A

B C D E

C D E

BC

Page 23: Cautare peste siruri

Expresii regulate

patternul desemneaza o multime infinita de siruri de cautat = limbajul generat de o expresie regulata

definitia expresiilor regulate peste A

<expr_reg> ::= a | ε | empty

| (expr_regexpr_reg) | (expr_reg + expr_reg) | expr_reg*

limbajul definit de expresiile regulateL(a) = {a}L(ε) = {ε}L(empty) = ØL(e1e2) = L(e1)L(e2) = {uv | u L(e1), v L(e2)}

L(e1+e2) = L(e1) L(e2)

L(e*) = iL(ei) = iL(e)i

Page 24: Cautare peste siruri

Automatul asociat unei expresii regulate

a

A1

A2

a A

e1

e2

ε

empty

Page 25: Cautare peste siruri

Automatul asociat unei expresii regulate (continuare)

A1

A2

A1

(e1e2)

(e1 + e2)

e1*

A1 A2

Page 26: Cautare peste siruri

Automatul asociat unei expresii regulate: exemplu

e = a(b*a+cd)

s = abbcacdaaab

1 2

3 4 5

76

a

b

cd

a

Page 27: Cautare peste siruri

Algoritm de cautare – structuri de date

D = coada cu restrictii la iesire, unde inserarile se pot face si la inceput si la sfarsit iar stegerile/citirile numai la inceput.

q = starea curenta a automatului, j pozitia curenta in textul s, i pozitia in textul s de inceput a

"pattern"-ului curent Simbolul # va juca rolul de delimitator (el poate fi inlocuit cu

starea invalida -1). Initial avem D = (#), q = 1 (prima stare dupa starea initiala 0),

i = j = 1.

Page 28: Cautare peste siruri

Algoritm de cautare: pasul curent

Daca din q pleaca doua arce neetichetate , atunci insereaza la inceput in D

destinatiile celor doua arce; din q pleaca un singur arc etichetat cu s[j] atunci insereaza la sfarsitul

lui D destinatia arcului; q este delimitatorul # atunci:

daca D = Ø, atunci incrementeaza i, j devine noul i, insereaza # in D si atribuie 1 lui q (aceasta corespunde situatiei cand au fost epuizate toate posibilitatile de a gasi in text o aparitie a unui sir specificat de "pattern" care incepe la pozitia i);

daca D ≠ Ø, atunci incrementeaza j si insereaza # la sfarsitul lui D; q este starea finala atunci s-a gasit o aparitie a unui sir specificat de

"pattern" care incepe la pozitia i. Extrage starea de la inceputul lui D si o memoreaza in q, dupa care

reia pasul curent.