[8] string matching2

Proiectarea algoritmilor: Cautare peste siruri

Dorel Lucanu

Faculty of Computer ScienceAlexandru Ioan Cuza University, Iasi, Romania

[email protected]

PA 2014/2015

D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 1 / 36

Outline

1 Algoritmul Aho-Corasick

2 Expresii regulate


Algoritmul Aho-Corasick

Plan


2 Expresii regulate



Problema cautarii pentru mai multe pattern-uri

Input Un sir s = s0 sn1, numit subiect sau text, si o multime depattern-uri P = {P0, . . .Pk1}.Output Aparitiile pattern-elor Pj n textul s, daca exista. Notam

m =k1

j=0 |Pj |.Utilizarea unui algoritm de cautare liniar determina paritiile n timpulO(n + k m).Algoritmul Aho-Corasick (1975) poate realiza cautarea n timpulO(n + m + z), unde z este numarul de aparitii.



Arbore digital

P == {amar ,mar ,martie, rama,manta}

0 6 5 7 8 9

1

14 15 16 17

3 2 a

m a 4 r

m a n t a

10 11 12 13 t i e

r

r

a m a

{amar}

{manta}

{mar} {martie}

{rama}



Structura de date pentru arborele digital

0 6 5 7 8 9

1

14 15 16 17

3 2 a

m a 4 r

m a n t a

10 11 12 13 t i e

r

r

a m a

{amar}

{manta}

{mar} {martie}

{rama}

Consideram doua functii (tablouri): g[state, letter] si out[state]:g[0,a] = 1, g[0, m] =5, g[0, r] = 14,g[1, m] = 2, g[5, a] = 6, g[14, a] = 15,. . .out[4] = amar, out[10] = mar, . . .



Adaugarea lui martie

state = 0;g[state, m] = 5 state = 5g[state, a] = 6 state = 6g[state, r] nedefinitpresupunem ca valoarea variabilei globale newstate era 9newstate = 10, g[newstate, r] = 10newstate = 11, g[newstate, t] = 11newstate = 12, g[newstate, i] = 12newstate = 13, g[newstate, e] = 13out[13] = martie

Presupunem ca alfabetul este .



Adaugarea unui pattern ntr-un arbore digital (trie)addPattern(P) {

m = P.length();

state = 0;

j=1;

while (g[state, P[j]] != undef) {

state = g[state, P[j]]; // g este variabila globala

j = j+1;

}

for (i = j; i


Constructia arborelui digital

constrTrie(P) {newstate = 0;

for (each c )g[0,c] = undef;

for (each Pi P)addPattern(Pi);

}



Functia esec KMP (reamintire)

p = abaabaaabc

5 0 1 2 3 4 6 7 8 a 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 4 1 2

Reamintim ca se mai numeste automat KMP.



Functia esec AC

0 6 5 7 8 9

1

14 15 16 17

3 2 a

m a 4 r

m a n t a

10 11 12 13 t i e

r

r

a m a

~{a,m,r}

{amar}

{manta}

{mar} {martie}

{rama}



Functia esec AC

0 6 5 7 8 9

1

14 15 16 17

3 2 a

m a 4 r

m a n t a

10 11 12 13 t i e

r

r

a m a

~{a,m,r}

{amar}

{manta}

{mar} {martie}

{rama}

Urmand aceeasi conventie ca la KMP, se mai numeste si automat AC.



Constructia functiei esec

initializare:

q = empty();

for (each c ) {state = g[0,c];

if ((state != 0) and (state != undef))

q.pushBack(state);

f[state] = 0;

}



Constructia functiei esec

iteratia principala

while (! q.isEmpty()) {

crntstate = q.topFront(); q.popFront();

for (each c ) {chldstate = g[crntstate, c];

if ((chldstate != undef) and (chldstate != 0)) {

q.pushBack(chldstate);

state = f[crntstate];

while (g[state,c] = undef) state = f[state];

f[chldstate] = g[state, c];

out[chldstate] = out[chldstate] out[f[chldstate]];}

}

}


Expresii regulate

Plan


2 Expresii regulate


Expresii regulate

Definitie

In aceasta sectiune consideram cazul cand pattern-ul constituie doar ospecificatie a ceea ce se cauta n sensul ca el desemneaza o multime desiruri pentru care se cauta. Numim o astfel de specificatie patterngeneralizat.Un alt mod de a specifica pattern-uri generalizate l constituie expresiileregulate.

Definitie

Multimea expresiilor regulate peste alfabetul este definita recursiv astfel:, empty sunt expresii regulate

orice caracter din este o expresie regulata;

daca e1, e2 sunt expresii regulate, atunci e1e2 si e1 + e2 sunt expresii regulate;

daca e este expresie regulata, atunci (e) si e sunt expresii regulate.

Arborele sintactic abstract: pe tabla.


Expresii regulate

Legatura cu pachetul din C++

expresia regulata

[abc] a + b + c

\d sau [[:digit:]] 0 + 1 + + 9[[:digit:]]* (0 + 1 + + 9)[[:digit:]]+ (0 + 1 + + 9)(0 + 1 + + 9)


Expresii regulate

Limbajul definit de o expresie regulata

Definitie

Multimea de siruri (limbajul) L(e) definit de o expresie regulata e este definitrecursiv astfel:

L() = {}) ( este sirul vid (de lungime zero)), L(empty) = daca e este un caracter atunci L(e) = {e};daca e = e1e2 atunci L(e) = L(e1)L(e2) = {w1w2 | w1 L(e1),w2 L(e2)};daca e = e1 + e2 atunci L(e) = L(e1) L(e2);daca e = e1 atunci L(e) = kL(ek1 ), undeL(e01 ) = {}, L(ek+11 ) = L(ek1 )L(e1);daca e = (e1) atunci L(e) = L(e1).

Exemplu: Fie alfabetul A = {a, b, c}. Avem L(a(b + a)c) = {abc, aac}si L((ab)) = {, ab, abab, ababab, . . .} = {(ab)k | k 0}. sfex


Expresii regulate

Automatul asociat unei expresii regulate

cazul de baza

e este o litera (un simbol) a startstart

a

e este startstart

e este emptystartstart

pentru cazul inductiv presupunem:

startstart M1

startstart M2


Expresii regulate


e = e1e2:

startstart M1 M2

e = e1 + e2:

start

M1

M2


Expresii regulate


e = e1 :

start M1


Expresii regulate

Exemplu

0start 1

2

3

4

5 6

7 8 9 10

a

a b

b a

Detaliile procesului de constrtie pe tabla


Expresii regulate

Automate nedeterministe

Automatele asociate expresiilor regulate sunt cazuri particulare deautomate finite: M = (Q,, , q0,Qf ), unde Q este multimea destari, alfabetul, : Q A Q tranzitiile, q0 Q starea initiala,Qf Q starea finalalimbajul acceptat L(M) este multimea de cuvinre ce descriu parcursuride la starea initiala la o stare finala

daca M(e) este automatul asociat lui e, atunci L(M(e)) = L(e)

tranzitiile neetichetate se numesc si -tranzitii (sau spontane)

automatul construit direct din definitie este nedeterminist sineminimal

costisitor de aplicat n practica

se poate construi un automat echivalent determinist?

raspunsul este afirmativ (automatele finite nedeterministe au aceeasipute de acceptare ca si cele deterministe), dar cu anumite costuri (ase vedea slide-urilr urmatoare)


Expresii regulate

Constructia unui automat determinist echivalent

Fie N un automat nedeterminist cu multimea de stari Q. Construim unautomat determinsit D astfel:

multimea de stari este P(Q) (numar exponential de stari!!!)exista tranzitie etichetata cu a de la Q1 la Q2 daca si numai daca Q2este multimea tuturor starilor q2 cu proprietatea ca exista q1 Q1 sitranzitie etichetata cu a de la q1 la q2 n N

starea initiala a lui D este {q0}, unde q0 este starea initiala a lui No submultime Qf este stare finala daca si numai daca include o starefinala qf a lui N

Exemplu pe tabla.Constructia de mai sus se poate mbunatati utilizand un algoritm bazat pederivativele Brzozowski.


Expresii regulate

Derivativele Brzozowski

Derivativele unei expresii regulate (Brzozowski, 1964):

a(empty) = empty ?(empty) = empty

a() = empty ?() =

a(b) =

{ , b = a

empty , b 6= a ?(b) = empty

a(e1e2) = a(e1)e2 + ?(e1)a(e2) ?(e1e2) = ?(e1)?(e2)

a(e1 + e2) = a(e1) + a(e2) ?(e1 + e2) = ?(e1) + ?(e2)

a(e) = a(e)e ?(e) =

Extensia la cuvinte: (e) = e, wa(e) = a(w (e))


Expresii regulate

Simplificari

concatenarea si + sunt asociative, + este si comutativa

e + e = e

e + empty = empty + e = e

e empty = empty e = empty

e = e = e


Expresii regulate

Proprietatea fundamentala

Theorem (Brzozowski)

Multimea derivatelor unei expresii {w (e) | w A} este finita.

Exemplu:{w ((ab + a ) b a) | w A} ={(b + )((a b + a) b a), (a b + a) b a, a, , empty}


Expresii regulate

Constructia automatului (Brzozowski)

multimea de stari este multimea derivatelor

exista tranzitie etichetata cu a de la q1 la q2 daca si numai daca q1corespunde unei derivate w (e) si q2 corespunde derivatei wa(e)pentru un w A;starea initiala este e = (e)

o stare q este finala (de acceptare) daca si numai daca corespundeunei derivate w (e) si ?(w (e)) = .


Expresii regulate

Exemplu

e = (a b + a) b a

(a b + a) b astart

(b + )(a b + a) b a (a b + a) b a + a

a

a

b

a

b

a

b

a


Expresii regulate

Constructia unui automat determinist

(Berry, Setti: From Regular Expressions To Deterministic Automata, 1986)O continuare a lui a n e este orice expresie wa(e) 6= empty .

se marcheaza simbolurile din e ca fiind distincte; fie e expresiaobtinuta (de exemplu e = (ab + b)ba este transformata ne = (a1b2 + b3)b4a5)se construieste automatul M pentru e urmand ideea din algoritmullui Brzozowski:

M are o stare pentru fiecare continuare a unui simbol marcat n e

exista tranzitie de la q1 la q2 daca si numai daca q1 corespunde uneicontinuari C , C , C poate genera un cuvant care ncepe cu a(wa(e) 6= empty) si q2 corespunde continuarii lui astarea initiala este e

q este o stare finala (de acceptare) daca si numai daca ea corespundeunei continuari C si ?(C ) =

se elimina marcile din M

se determinizeaza M construind M ale carui stari sunt submultimi destari ale lui M


Expresii regulate

Constructii mai performante

utilizand functiile first si follow (Berry, Setti, 1986)

paralelizare (Myer, A Four Russians Algorithm for Regular ExpressionPattern Matching)

o alta constructie pentru automatul nedeterminist esteGlushkov-McNaughton-Yamada (1960-1961), care poate fi siparalelizata (Navarro & Raffinot, 2004)


Expresii regulate

Complexitatea cautarii cu expresii regulate

Presupunem ca lungimea expresiei regulate este m (numarul de caracterefara operatori) si m = | {,+, }|.Theorem (Thomson, 1968)

Problema cautarii cu expresii regulate poate fi rezolvata n timpul O(mn)cu automate nedeterministe si spatiu O(m).

Theorem (Kleene, 1956)

Problema cautarii cu expresii regulate poate fi rezolvata n timpulO(n + 2m) cu automate deterministe si spatiu O(2m).

Theorem (Myers, 1992)

Problema cautarii cu expresii regulate poate fi rezolvata n timpulO(mn/ log n) cu automate deterministe si spatiu O(mn/ log n).


Algoritmul Aho-CorasickExpresii regulate

[8] string matching2

Documents