h1. Automate finite si KMP
 
(Creat de '_azotlichid_':user/azotlichid la data de _2005-01-12_ categoria _Automate_, autor(i) _Vladu Adrian_)
 
*Continut scurt:*
 In acest articol vom aborda cele mai comune probleme legate de pattern matching si vom oferi suportul teoretic necesar intelegerii algoritmului Knuth-Morris-Pratt, pornind de la potrivirea standard cu automate finite si rafinand-o treptat pana la un algoritm de complexitate O(n + m). Toate acestea intr-o maniera usor de inteles ;)
==Include(page="template/raw")==
 
In acest articol vom aborda cele mai comune probleme legate de pattern matching si vom oferi suportul teoretic necesar intelegerii algoritmului Knuth-Morris-Pratt, pornind de la potrivirea standard cu automate finite si rafinand-o treptat pana la un algoritm de complexitate O(n + m). Toate acestea intr-o maniera usor de inteles ;)
 
 
*Continut lung:*
Automate finite
 
Ce sunt automatele finite ?
 
Un automat finit este definit ca un cvintuplu <Q, q0, A, S, d> unde Q este o multime finita de stari Q = {q0, q1, ... qn}, q0 apartine Q (q0 = stare initiala), A inclus in Q (A = multimea starilor de acceptare), S este un alfabet, iar functia d : Q x S -> Q.
 
Aceasta este definitia matematica si foarte abstractizata a automatelor. Pentru a le intelege mai usor, sa luam un exemplu concret
 
Q = {q0, q1, q2, q3}
A = {q3}
S = {a, b}
d =
 
 
 
 
| | a | b |
 
| 0 | 1 | 2 |
 
| 1 | 3 | 1 |
 
| 2 | 3 | 0 |
 
| 3 | 3 | 3 |
 
 
Ce inseamna asta? Sa spunem ca automatul primeste un string s = 'bbaba'
Initial ne aflam in q0. Pentru fiecare element al stringului s_i facem tranzitia d(qk, s_i).
 
Pornim din k = 0. Vom avea :
 
k = 0; d(0, b) = 2;
k = 2; d(2, b) = 0;
k = 0; d(0, a) = 1;
k = 1; d(1, b) = 1;
k = 2; d(1, a) = 3;
 
Daca ultima stare obtinuta qk apartine A, atunci spunem ca automatul accepta stringul. Altfel spus, daca avem stringul s, lungime(s) = n, automatul accepta stringul daca si numai daca d ( ... d( d(0, s(1)), s(2) ) ..., s(n) ) apartine A.
 
Stringurile 'aa', 'aaaaaaa', 'aabababab', 'aaaba', 'ba', 'aba' sunt acceptate de automat, dar 'ba', 'abbbbbb', 'bba' nu.
 
La ce folosesc ?
 
1. Inteligenta artificiala (prima si cea mai involuata stare a inteligentei artificiale)
2. Aplicatii teoretice si probleme de matematica :)
3. Pattern matching
 
Se dau stringurile M si N. Se cere sa gasim toate aparitiile lui N in M.
Vom numi Mi prefixul lui M de lungime i. Presupunand ca avem construit automatul care accepta stringul N, vom cauta toate prefixele lui M acceptate de automat, deci toate numerele 1 <= i <= lungime(M) cu proprietatea ca automatul accepta stringul Mi.
 
 
 
Algoritm_potrivire_cu_automat_finit
 
1: n = lungime(N)
2: q = 0;
3: pt i <- 1, n
4: q = d(q, M[i])
5: daca q apartine A
6: scrie "potrivire la pozitia " i - n + 1
 
complexitate : O(n)
 
Sa vedem cum se construieste automatul de potrivire pentru un string N. Fie m = lungime(M). Construim un automat cu m + 1 stari {q0, q1, ... qm}, A = {qm} . Faptul ca ne aflam in starea x inseamna ca au fost acceptate primele x caractere din sirul de intrare.
Din fiecare stare qx apartine Q si pt fiecare c apartine S construim d(x, c) = y cu proprietatea ca My este cel mai lung prefix al lui M care este sufix al lui Mxc (prefixul de lungime x al lui M, concatenat cu caracterul c).
 
 
 
Algoritm_constructie_automat_finit
 
1: m <- lungime(M)
2: pt q <- 0, m
3: pt c apartine S
4: gaseste Mi = cel mai lung prefix al lui M cu Mi sufix al lui Mqc
5: d(q, c) = i
 
complexitate : linia 4 are complexitatea O(m^2) (implementata in maniera bruta) si se executa de (m + 1) * |S| ori => complexitate totala O(m^3 * |S|)
 
Practic, algoritmul calculeaza pentru toate 0 =< i =< m, c apartine S cat de mult putem lua de la sfarsitul lui Mic astfel incat acesta sa fie un "inceput" de N.
 
Acesta se poate rafina, eliminand operatii redundante, dupa cum vom vedea in cele ce urmeaza.
 
 
 
Algoritmul KMP
 
Gaseste toate aparitiile un string N in M in timp O(n + m), unde n = lungime(N), m = lungime(M). O parte esentiala a sa este functia prefix p : {1..n} -> {0..n-1} unde p[i] = cel mai lung prefix al lui M care este sufix al lui Mi. Evident, Mp[i] (prefixul de lungime p[i] al lui M) prefix al lui Mi, deci p[i] < i.
 
Algoritm_calcul_functie_prefix
 
1: n <- lungime(N)
2: k <- 0
3: p[1] <- 0
4: pt i <- 2, n
5: cat timp (k > 0) si (N[k + 1] ** N[i])
6: k <- p[k]
7: daca N[k + 1] = N[i]
8: k <- k + 1
9: p[i] <- k
 
Analiza complexitatii :
- la fiecare pas (i = 2, n) k se incrementeaza cel mult o data, deci pe parcursul algoritmului k se va incrementa de cel mult n - 1 ori (linia 8)
- in linia 5, k se decrementeaza cel mult pana devine 0, deci se va decrementa de cel
mult n - 1 ori pe parcursul algoritmului
 
=> Complexitate : O(n)
 
Algoritmul este similar cu constructia automatului de acceptare. Din fiecare stare i in care s-a acceptat Ni, vedem cat de mult putem lua de la sfarsitul lui Ni astfel incat sufixul respectiv sa fie prefix pentru N. De remarcat ca in cazul in care starea candidata k nu este buna, nu mergem in k - 1, ci in p[k]. Aceasta este de fapt "magia" care ofera complexitate liniara.
 
Algoritmul de potrivire este similar celui al calculului functiei prefix, numai ca aici la fiecare pas i cautam cel mai lung prefix al lui N care este sufix al lui Mi.
 
 
 
Algoritm_potrivire_KMP
 
1: m <- lungime(M), n <- lungime(N)
2: q <- 0
3: pt i <- 1, m
4: cat timp (q > 0) si (N[q + 1] ** M[i])
5: q <- pi[q]
6: daca N[q + 1] = M[i]
7: q <- q + 1
8: daca q = n
9: scrie "potrivire la pozitia " i - n + 1
 
 
 
Analog Algoritm_Calcul_Functie_Prefix, complexitatea algoritmului efectiv de potrivire este O(m). Astfel rezulta complexitatea liniara a algoritmului KMP O(n + m)
 
Teme pentru acasa:
 
- folosind functia prefix, rafinati constructia automatului finit de acceptare pt un string, aducand-o la complexitatea O(m^2 * |S|)
- problema "[1]Microvirus" (hint : construiti automatul de potrivire pentru stringul dat)
- Timus 1158
 
 
 
References
 
Visible links
1. http://www.liis.ro/%7ecampion/problems/2/64/microvirus.htm
==Include(page="template/raw")==
 
Automate finite
 
Ce sunt automatele finite ?
 
Un automat finit este definit ca un cvintuplu <Q, q0, A, S, d> unde Q este o multime finita de stari Q = {q0, q1, ... qn}, q0 apartine Q (q0 = stare initiala), A inclus in Q (A = multimea starilor de acceptare), S este un alfabet, iar functia d : Q x S -> Q.
 
Aceasta este definitia matematica si foarte abstractizata a automatelor. Pentru a le intelege mai usor, sa luam un exemplu concret
 
Q = {q0, q1, q2, q3}
A = {q3}
S = {a, b}
d =
 
 
 
 
| | a | b |
 
| 0 | 1 | 2 |
 
| 1 | 3 | 1 |
 
| 2 | 3 | 0 |
 
| 3 | 3 | 3 |
 
 
Ce inseamna asta? Sa spunem ca automatul primeste un string s = 'bbaba'
Initial ne aflam in q0. Pentru fiecare element al stringului s_i facem tranzitia d(qk, s_i).
 
Pornim din k = 0. Vom avea :
 
k = 0; d(0, b) = 2;
k = 2; d(2, b) = 0;
k = 0; d(0, a) = 1;
k = 1; d(1, b) = 1;
k = 2; d(1, a) = 3;
 
Daca ultima stare obtinuta qk apartine A, atunci spunem ca automatul accepta stringul. Altfel spus, daca avem stringul s, lungime(s) = n, automatul accepta stringul daca si numai daca d ( ... d( d(0, s(1)), s(2) ) ..., s(n) ) apartine A.
 
Stringurile 'aa', 'aaaaaaa', 'aabababab', 'aaaba', 'ba', 'aba' sunt acceptate de automat, dar 'ba', 'abbbbbb', 'bba' nu.
 
La ce folosesc ?
 
1. Inteligenta artificiala (prima si cea mai involuata stare a inteligentei artificiale)
2. Aplicatii teoretice si probleme de matematica :)
3. Pattern matching
 
Se dau stringurile M si N. Se cere sa gasim toate aparitiile lui N in M.
Vom numi Mi prefixul lui M de lungime i. Presupunand ca avem construit automatul care accepta stringul N, vom cauta toate prefixele lui M acceptate de automat, deci toate numerele 1 <= i <= lungime(M) cu proprietatea ca automatul accepta stringul Mi.
 
 
 
Algoritm_potrivire_cu_automat_finit
 
1: n = lungime(N)
2: q = 0;
3: pt i <- 1, n
4: q = d(q, M[i])
5: daca q apartine A
6: scrie "potrivire la pozitia " i - n + 1
 
complexitate : O(n)
 
Sa vedem cum se construieste automatul de potrivire pentru un string N. Fie m = lungime(M). Construim un automat cu m + 1 stari {q0, q1, ... qm}, A = {qm} . Faptul ca ne aflam in starea x inseamna ca au fost acceptate primele x caractere din sirul de intrare.
Din fiecare stare qx apartine Q si pt fiecare c apartine S construim d(x, c) = y cu proprietatea ca My este cel mai lung prefix al lui M care este sufix al lui Mxc (prefixul de lungime x al lui M, concatenat cu caracterul c).
 
 
 
Algoritm_constructie_automat_finit
 
1: m <- lungime(M)
2: pt q <- 0, m
3: pt c apartine S
4: gaseste Mi = cel mai lung prefix al lui M cu Mi sufix al lui Mqc
5: d(q, c) = i
 
complexitate : linia 4 are complexitatea O(m^2) (implementata in maniera bruta) si se executa de (m + 1) * |S| ori => complexitate totala O(m^3 * |S|)
 
Practic, algoritmul calculeaza pentru toate 0 =< i =< m, c apartine S cat de mult putem lua de la sfarsitul lui Mic astfel incat acesta sa fie un "inceput" de N.
 
Acesta se poate rafina, eliminand operatii redundante, dupa cum vom vedea in cele ce urmeaza.
 
 
 
Algoritmul KMP
 
Gaseste toate aparitiile un string N in M in timp O(n + m), unde n = lungime(N), m = lungime(M). O parte esentiala a sa este functia prefix p : {1..n} -> {0..n-1} unde p[i] = cel mai lung prefix al lui M care este sufix al lui Mi. Evident, Mp[i] (prefixul de lungime p[i] al lui M) prefix al lui Mi, deci p[i] < i.
 
Algoritm_calcul_functie_prefix
 
1: n <- lungime(N)
2: k <- 0
3: p[1] <- 0
4: pt i <- 2, n
5: cat timp (k > 0) si (N[k + 1] ** N[i])
6: k <- p[k]
7: daca N[k + 1] = N[i]
8: k <- k + 1
9: p[i] <- k
 
Analiza complexitatii :
- la fiecare pas (i = 2, n) k se incrementeaza cel mult o data, deci pe parcursul algoritmului k se va incrementa de cel mult n - 1 ori (linia 8)
- in linia 5, k se decrementeaza cel mult pana devine 0, deci se va decrementa de cel
mult n - 1 ori pe parcursul algoritmului
 
=> Complexitate : O(n)
 
Algoritmul este similar cu constructia automatului de acceptare. Din fiecare stare i in care s-a acceptat Ni, vedem cat de mult putem lua de la sfarsitul lui Ni astfel incat sufixul respectiv sa fie prefix pentru N. De remarcat ca in cazul in care starea candidata k nu este buna, nu mergem in k - 1, ci in p[k]. Aceasta este de fapt "magia" care ofera complexitate liniara.
 
Algoritmul de potrivire este similar celui al calculului functiei prefix, numai ca aici la fiecare pas i cautam cel mai lung prefix al lui N care este sufix al lui Mi.
 
 
 
Algoritm_potrivire_KMP
 
1: m <- lungime(M), n <- lungime(N)
2: q <- 0
3: pt i <- 1, m
4: cat timp (q > 0) si (N[q + 1] ** M[i])
5: q <- pi[q]
6: daca N[q + 1] = M[i]
7: q <- q + 1
8: daca q = n
9: scrie "potrivire la pozitia " i - n + 1
 
 
 
Analog Algoritm_Calcul_Functie_Prefix, complexitatea algoritmului efectiv de potrivire este O(m). Astfel rezulta complexitatea liniara a algoritmului KMP O(n + m)
 
Teme pentru acasa:
 
- folosind functia prefix, rafinati constructia automatului finit de acceptare pt un string, aducand-o la complexitatea O(m^2 * |S|)
- problema "[1]Microvirus" (hint : construiti automatul de potrivire pentru stringul dat)
- Timus 1158
 
 
 
References
 
Visible links
1. http://www.liis.ro/%7ecampion/problems/2/64/microvirus.htm
 

h1. Automate finite si KMP
 
(Categoria _Algoritmi_, Autor _Adrian Vladu_)
 
In acest articol vom aborda cele mai comune probleme legate de pattern matching si vom oferi suportul teoretic necesar intelegerii algoritmului Knuth-Morris-Pratt, pornind de la potrivirea standard cu automate finite si rafinand-o treptat pana la un algoritm de complexitate {$O(n + m)$}. Toate acestea intr-o maniera usor de inteles ;)
 
h2. Automate finite
 
h3. Ce sunt automatele finite ?
 
Un automat finit este definit ca un cvintuplu {@<@}{$Q, q{~0~}, A, &#0931;, &#0948;$}{@>@} unde $Q$ este o multime finita de stari {$Q = {q{~0~}, q{~1~}, ... q{~n~}}$}, $q{~0~}$ apartine $Q$ ({$q{~0~}$} = stare initiala), $A$ inclus in $Q$ ({$A$} = multimea starilor de acceptare), $&#0931;$ este un alfabet, iar functia {$&#0948; : Q x &#0931; -> Q$} este functia de tranzitie a automatului.
 
Aceasta este definitia matematica si foarte abstractizata a automatelor. Pentru a le intelege mai usor, sa luam un exemplu concret
 
!Automate-finite-si-KMP?dfa.jpg!
 
* $Q = {q{~0~}, q{~1~}, q{~2~}, q{~3~}}$
* $A = {q{~3~}}$
* $&#0931; = {a, b}$
* &#0948; =
 
table. | &#0948; | a | b |
| 0&nbsp; | 1 | 2 |
| 1 | 3 | 1 |
| 2 | 3 | 0&nbsp; |
| 3 | 3 | 3 |
 
 
Ce inseamna asta? Sa spunem ca automatul primeste un string $s$ = *bbaba*
Initial ne aflam in {$q{~0~}$}. Pentru fiecare element al stringului $s{~i~}$ facem tranzitia {$&#0948;(q{~k~}, s{~i~})$}.
 
Pornim din {$k = 0$}. Vom avea :
 
* $k = 0; &#0948;(0, b) = 2;$
* $k = 2; &#0948;(2, b) = 0;$
* $k = 0; &#0948;(0, a) = 1;$
* $k = 1; &#0948;(1, b) = 1;$
* $k = 1; &#0948;(1, a) = 3;$
 
Daca ultima stare obtinuta $q{~k~}$ apartine {$A$}, atunci spunem ca automatul accepta stringul. Altfel spus, daca avem stringul {$s$}, {$lungime(s) = n$}, automatul accepta stringul daca si numai daca $&#0948;( ... &#0948;( &#0948;(0, s{~1~}), s{~2~} ) ..., s{~n~} )$ apartine {$A$}.
 
Stringurile '{$aa$}', '{$aaaaaaa$}', '{$aabababab$}', '{$aaaba$}', '{$ba$}', '{$aba$}' sunt acceptate de automat, dar '{$abbbbbb$}', '{$bba$}' nu.
 
h3. La ce folosesc ?
 
# Inteligenta artificiala (prima si cea mai involuata stare a inteligentei artificiale)
# Aplicatii teoretice si probleme de matematica :)
# Pattern matching
 
Se dau stringurile $M$ si {$N$}. Se cere sa gasim toate aparitiile lui $N$ in {$M$}.
Vom numi {$M{~i~}$} prefixul lui $M$ de lungime {$i$}. Presupunand ca avem construit automatul care accepta stringul {$N$}, vom cauta toate prefixele lui $M$ acceptate de automat, deci toate numerele $1 &le; i &le; lungime(M)$ cu proprietatea ca automatul accepta stringul {$M{~i~}$}.
 
h3. Algoritm_potrivire_cu_automat_finit
 
== code(c) |
n = lungime(N)
m = lungime(M)
q = 0;
pt i <- 1, m
    q = d(q, M[i])
    daca q apartine A
        scrie "potrivire la pozitia " i - n + 1
==
 
* Complexitate : $O(n)$
 
Sa vedem cum se construieste automatul de potrivire pentru un string {$N$}. Fie {$m = lungime(M)$}. Construim un automat cu $m + 1$ stari {{$q{~0~}, q{~1~}, ... q{~m~}$}}, $A = {q{~m~}}$ . Faptul ca ne aflam in starea $x$ inseamna ca au fost acceptate primele $x$ caractere din sirul de intrare.
Din fiecare stare $q{~x~}$ apartine $Q$ si pt fiecare $c$ apartine $S$ construim $&#0948;(x, c) = y$ cu proprietatea ca $M{~y~}$ este cel mai lung prefix al lui $M$ care este sufix al lui $M{~x~}c$ (prefixul de lungime $x$ al lui {$M$}, concatenat cu caracterul {$c$}).
 
 
 
h3. Algoritm_constructie_automat_finit
 
== code(c) |
m <- lungime(M)
pt q <- 0, m
    pt c apartine S
        gaseste M[i] = cel mai lung prefix al lui M cu M[i] sufix al lui M[q]c
            d(q, c) = i
==
 
* Complexitate : linia $4$ are complexitatea $O(m^2^)$ (implementata in maniera bruta) si se executa de $(m + 1) * |&#0931;|$ ori => complexitate totala $O(m^3^ * |&#0931;|)$
 
Practic, algoritmul calculeaza pentru toate {$0 &le; i &le; m$}, $c$ apartine $S$ cat de mult putem lua de la sfarsitul lui $M{~i~}c$ astfel incat acesta sa fie un "inceput" de {$N$}.
 
Acesta se poate rafina, eliminand operatii redundante, dupa cum vom vedea in cele ce urmeaza.
 
h2. Algoritmul KMP
 
Gaseste toate aparitiile unui string $N$ in $M$ in timp {$O(n + m)$}, unde {$n = lungime(N)$}, {$m = lungime(M)$}. O parte esentiala a sa este functia prefix $&pi; : {1..n} -> {0..n-1}$ unde $&pi;{~i~}$ = cel mai lung prefix al lui $M$ care este sufix al lui {$M{~i~}$}. Evident, $M{~&pi;{~i~}~}$ (prefixul de lungime $&pi;{~i~}$ al lui {$M$}) este prefix al lui {$M{~i~}$}, deci {$&pi;{~i~} < i$}.
 
h3. Algoritm_calcul_functie_prefix
 
== code(c) |
n <- lungime(N)
k <- 0
pi[1] <- 0
pt i <- 2, n
    cat timp (k > 0) si (N[k + 1] != N[i])
        k <- pi[k]
    daca N[k + 1] = N[i]
        k <- k + 1
    pi[i] <- k
==
 
h4.  Analiza complexitatii :
 
* la fiecare pas ({$i = 2, n$}) $k$ se incrementeaza cel mult o data, deci pe parcursul algoritmului $k$ se va incrementa de cel mult $n - 1$ ori (linia {$8$})
* in linia {$5$}, $k$ se decrementeaza cel mult pana devine {$0$}, deci se va decrementa de cel
mult $n - 1$ ori pe parcursul algoritmului
* {=>} Complexitate : $O(n)$
 
Algoritmul este similar cu constructia automatului de acceptare. Din fiecare stare $i$ in care s-a acceptat {$N{~i~}$}, vedem cat de mult putem lua de la sfarsitul lui {$N{~i~}$} astfel incat sufixul respectiv sa fie prefix pentru {$N$}. De remarcat ca in cazul in care starea candidata $k$ nu este buna, nu mergem in {$k - 1$}, ci in {$&pi;{~k~}$}. Aceasta este de fapt "magia" care ofera complexitate liniara.
 
Algoritmul de potrivire este similar celui al calculului functiei prefix, numai ca aici la fiecare pas $i$ cautam cel mai lung prefix al lui $N$ care este sufix al lui {$M{~i~}$}.
 
 
 
h3. Algoritm_potrivire_KMP
 
== code(c) |
m <- lungime(M), n <- lungime(N)
q <- 0
pt i <- 1, m
    cat timp (q > 0) si (N[q + 1] != M[i])
        q <- pi[q]
    daca N[q + 1] = M[i]
        q <- q + 1
    daca q = n
        scrie "potrivire la pozitia " i - n + 1
==
 
Analog Algoritm_Calcul_Functie_Prefix, complexitatea algoritmului efectiv de potrivire este {$O(m)$}. Astfel rezulta complexitatea liniara a algoritmului KMP $O(n + m)$
 
h2. Teme pentru acasa:
 
* folosind functia prefix, rafinati constructia automatului finit de acceptare pentru un string, aducand-o la complexitatea $O(m^2^ * |&#0931;|)$
* problema "Microvirus":http://www.liis.ro/%7ecampion/problems/2/64/microvirus.htm (hint : construiti automatul de potrivire pentru stringul dat)
* Timus 1158: "Censored!":http://acm.timus.ru/problem.aspx?space=1&num=1158
 

3698