[8] String Matching2
-
Upload
eirdnocotim -
Category
Documents
-
view
12 -
download
2
description
Transcript of [8] String Matching2
-
Proiectarea algoritmilor: Cautare peste siruri
Dorel Lucanu
Faculty of Computer ScienceAlexandru Ioan Cuza University, Iasi, Romania
PA 2014/2015
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 1 / 36
-
Outline
1 Algoritmul Aho-Corasick
2 Expresii regulate
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 2 / 36
-
Algoritmul Aho-Corasick
Plan
1 Algoritmul Aho-Corasick
2 Expresii regulate
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 3 / 36
-
Algoritmul Aho-Corasick
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.
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 4 / 36
-
Algoritmul Aho-Corasick
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}
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 5 / 36
-
Algoritmul Aho-Corasick
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, . . .
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 6 / 36
-
Algoritmul Aho-Corasick
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 .
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 7 / 36
-
Algoritmul Aho-Corasick
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
-
Algoritmul Aho-Corasick
Constructia arborelui digital
constrTrie(P) {newstate = 0;
for (each c )g[0,c] = undef;
for (each Pi P)addPattern(Pi);
}
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 9 / 36
-
Algoritmul Aho-Corasick
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.
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 10 / 36
-
Algoritmul Aho-Corasick
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}
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 11 / 36
-
Algoritmul Aho-Corasick
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}
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 12 / 36
-
Algoritmul Aho-Corasick
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}
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 13 / 36
-
Algoritmul Aho-Corasick
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}
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 14 / 36
-
Algoritmul Aho-Corasick
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}
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 15 / 36
-
Algoritmul Aho-Corasick
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.
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 16 / 36
-
Algoritmul Aho-Corasick
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;
}
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 17 / 36
-
Algoritmul Aho-Corasick
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]];}
}
}
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 18 / 36
-
Expresii regulate
Plan
1 Algoritmul Aho-Corasick
2 Expresii regulate
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 19 / 36
-
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.
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 20 / 36
-
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)
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 21 / 36
-
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
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 22 / 36
-
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
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 23 / 36
-
Expresii regulate
Automatul asociat unei expresii regulate
e = e1e2:
startstart M1 M2
e = e1 + e2:
start
M1
M2
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 24 / 36
-
Expresii regulate
Automatul asociat unei expresii regulate
e = e1 :
start M1
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 25 / 36
-
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
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 26 / 36
-
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)
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 27 / 36
-
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.
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 28 / 36
-
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))
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 29 / 36
-
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
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 30 / 36
-
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}
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 31 / 36
-
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)) = .
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 32 / 36
-
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
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 33 / 36
-
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
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 34 / 36
-
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)
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 35 / 36
-
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).
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2014/2015 36 / 36
Algoritmul Aho-CorasickExpresii regulate