sisteme de programe pentru timp real
DESCRIPTION
Sisteme de programe pentru timp real. Universitatea “Politehnica” din Bucuresti 2005-2006 Adina Magda Florea http://turing.cs.pub.ro/sptr_06. Structura curs. Prelucrarea sirurilor de caractere Criptografie si criptosisteme Retele neurale Algoritmi genetici Retele Bayesiene - PowerPoint PPT PresentationTRANSCRIPT
Sisteme de programeSisteme de programepentru timp realpentru timp real
Universitatea “Politehnica” din Bucuresti
2005-2006
Adina Magda Florea
http://turing.cs.pub.ro/sptr_06
Structura curs
• Prelucrarea sirurilor de caractere
• Criptografie si criptosisteme
• Retele neurale
• Algoritmi genetici
• Retele Bayesiene
• Programare web
Informatii curs
Pagina Web a cursului
http://turing.cs.pub.ro/sptr_06
Notare
• Laborator 30%
• Tema de casa de semestru 20%
• Examen 50%
• Minimum 7 prezente la laborator
Curs Nr. 1&2
• Complexitatea calculului
• Probleme NP-complete
• Prelucrarea sirurilor de caractere
Complexitatea calculului
Analiza algoritmilor
• o “dimensiune” N
• timpul mediu (average case)
• timpul cel mai nefavorabil (worst case)
• limita a performantei
• deducerea timpului mediu
• identificarea operatiilor abstracte
Clasificarea algoritmilor
Timp de executie proportional cu:
• Constant• log N• N• N log N• N2
• N3
• 2N
Timpul de executie a unui
program
• C1 * f(N) + C2
• Ce inseamna “a fi
proportional cu” ?
Complexitatea calculului
• studiul cazului cel mai nefavorabil (worst case) ignorind factorii constanti
• notatia O mare• DEFINTIE: O functie g(N) se spune a fi
O(f(N)) daca exista constantele pozitive C0 si N0 astfel incat g(N) < C0 *f(N) pentru orice N > N0.
• limita superioara a performantelor unui algoritm
Complexitatea calculului
• O(f(N)) este o limita superioara si, in realitate, poate fi mult mai scazuta;
• intrarea ce determina cazul cel mai nefavorabil poate sa nu apara niciodata in practica;
• constanta C0 nu se cunoaste si s-ar putea sa nu fie mica;
• constanta N0 nu se cunoaste si s-ar putea sa nu fie mica.
Complexitatea calculului
• notatia • limita inferioara a performantelor unui
algoritm (f1(N) (“big omega”)
• DEFINTIE: O functie g(N) se spune a fi (f1(N)) daca exista o constanta pozitiva C0 astfel incit g(N) C0 * f1(N) pentru un numar infinit de mare de valori ale lui N.
Complexitatea calculului pentru algoritmi recursivi
• Descompunerea recursiva a problemei in subprobleme
• Timpul de executie pentru acesti algoritmi este determinat de dimensiunea si numarul subproblemelor, precum si de costul descompunerii
• CN = complexitatea pentru o intrare de dimensiune N
• CN NLa fiecare apel recursiv se elimina cate un element de
intrare: CN = CN-1+1 int sum(int n)
{ if (n==) return 1; return n+sum(n-1); }
• CN N2/2Un algoritm care necesita parcurgerea intrarii si elimina
un element la fiecare apel recursiv: CN = CN-1 + N, pentru N 2, cu C1 = 1
bubble(int a[], int N) /* bubble sort recursiv */
• CN logN
Algoritmul injumatateste intrarea la fiecare apel recursiv: CN = CN/2 + 1, pentru N 2, cu C1 = 0 (pt deducere N=2n)
int binsearch(int a[], int key, int l, int r)
• CN 2N
Algoritmul imparte intrarea in doua parti la fiecare pas si apoi prelucreaza recursiv fiecare parte (“Divide and conquer”): CN = 2*CN/2 + 1, pentru N 2, cu C1 = 0
rigla(int l, int r, int h
/* Desenarea marcajelor pe o rigla */
• CN NlogNAlgoritm recursiv care isi imparte intrarea in doua parti
la fiecare pas, prelucreaza recursiv fiecare parte si face o trecere liniara peste intrare, fie inainte, fie dupa divizarea intrarii (“Divide and conquer”) :
CN = 2 * CN/2 + N, pt N 2, cu C1 = 0.
quicksort(int a[], int l, int r)
• Insertion sort N
• Bubble sort
• Quicksort
• Heapsort
• Mergesort
• Sequential search
• Binary search
• Binary tree search
• Shortest path V, E
• Depth-first search
• Breadth-first search
• Min. spanning tree
• N2/4, N2/8
• N2/4, N2/4
• N logN, N2
• N logN, N logN
• N logN, N logN (sp N)
• N, N/2
• logN, logN
• N, logN
• E sau V2
• V+E sau V2
• V+E sau V2
• (E+V) log V – pr. q.
• E log E - Kruskal
Probleme NP-complete
• “grele” si “usoare”
• Problema usoara: “Exista o cale de la x la y cu cost M ?
• Problema grea: “Exista o cale de la x la y cu cost M ?
• Algoritmi “eficienti” si algoritmi “ineficienti”
Probleme NP-complete
• P: multimea tuturor problemelor ce pot fi solutionate prin algoritmi deterministi, in timp polinomial
• NP: multimea tuturor problemelor ce pot fi rezolvate prin algoritmi nedeterministi, in timp polinomial
• NP =? P
Clasa problemelor NP-complete
• Clasa de echivalenta: daca o problema din NP poate fi rezolvata eficient, atunci toate pot fi rezolvate la fel
• Se poate demonstra echivalenta problemelor NP-complete din punct de vedere al algoritmilor de rezolvare
• Pentru a demonstra ca o problema X din NP este NP-completa este necesar sa se demonstreze ca o problema NP-completa (Y, cunoscuta) poate fi transformata in timp polinomial - redusa polinomial la problema X
• Presupunem ca problema ciclului hamiltonian (CH) este NP-completa (Y) si dorim sa vedem daca cea a comis-voiajorului (CV) este NP-completa (X)
• Trebuie ca Y sa fie redusa polinomial la X
• Instanta a CH => se construieste o instanta a CV:
• oraseCV = noduri din grafCH
• distante perechi oraseCV = 1 daca exiata arcCH
» = 2 daca nu exista arcCH
Se cere CV sa gaseasca un ciclu care include toate orasele si are suma ponderilor V, numarul de noduri din graf – acesta trebuie sa corespunda unui ciclu hamiltonian
Am demonstrat ca CV este NP-completa
• Este o expresie booleana data realizabila ?
• Dandu-se un graf neorientat, exista un ciclu hamiltonian continut in el (ciclu ce include toate nodurile) ?
• Problema comis-voiajorului: Fiind dat un graf cu ponderi intregi pozitive si un intreg K, sa se gaseasca un ciclu care include toate nodurile si a carui suma a ponderilor sa fie K (sau minima).
• Exista un K-clique intr-un graf neorientat G? (K-clique – un subgraf complet - orice pereche de puncte din subgraf este legata de un arc - al lui G cu K noduri)
Exemple de probleme NP-complete
Este un graf neorientat colorabil cu k culori ? (G este k-colorabil daca exista o atribuire de intregi 1, 2, ... k, reprezentand culori, pentru nodurile din G, astfel incat nu exista doua noduri adiacente de aceeasi culoare. Numarul cromatic al lui G este cel mai mic k pentru care G este k-colorabil.)
Exista o acoperire de noduri de dimensiune K intr-un graf neorientat ? ( G = (V, E), o acoperire de noduri este un subset S V astfel incit fiecare arc din G este incident intr-un nod din S, card(S) = K.)
• Problema izomorfismului subgrafurilor: este un graf neorientat G izomorf cu un subgraf al unui alt graf neorientat G’ ?
Problema Knapsack: Fiind data secventa de intregi S = i1, i2, ... in si un intreg K, exista o subsecventa a lui S a carei sume este exact K ?
Pentru o familie de multimi S1, S2, … Sn, exista o acoperire de multimi formata dintr-o sub-familie de multimi disjuncte ?
• Problema planificarii taskurilor: Dandu-se un “deadline” si o multime de taskuri de lungimi variabile, ce trebuie executate pe doua procesoare identice, se pot aranja aceste taskui in asa fel incit “deadline”-ul sa fie respectat ?
Cum se poate evita complexitatea?
• algoritm polinomial dar suboptimal; rezulta o solutie apropiata de cea mai buna
• se foloseste direct algoritmul exponential daca dimensiunea intrarii nu este mare
• algoritm exponential cu euristici
Algoritmi de identificare a sirurilor de caractere
• Introducere
• Algoritmul cautarii directe
• Algoritmul Knuth-Morris-Prat
• Algoritmul Boyer-Moore
• Algoritmul Rabin-Karp
• Algoritmul deplaseaza-aduna
1 Introducere
• Identificarea (recunoasterea) sabloanelor in siruri de caractere
• sir – a, lungime N • sablon – p, lungime M• Fiind dat un sir de lungime N
a = a1a2a3...aN, si un sablon de lungime M
p = p1p2p3...pM, se cere sa se gaseasca multimea de pozitii
{ i 1 i N-M+1 a.i. aiai+1…ai+M-1 = p }
Introducere
• Prima aparitie / toate aparitiile• Cum difera de cautarea unei chei• Scurt istoric• Algoritmul fortei brute. Are un timp al cazului cel mai nefavorabil
proportional cu N*M, dar in multe cazuri practice, timpule mediu este proportional cu N+M.
• In 1970, S.A. Cook a demonstrat teoretic, folosind un model de masina abstracta, ca exista un algoritm de identificare a sabloanelor cu timpul cel mai nefavorabil proportional cu N+M. Pornind de la modelul lui Cook, D.E. Knuth, J.H. Morris si V.R. Pratt au construit un astfel de algoritm.
• R.S. Boyer si J.S. Moore au descoperit, in 1976, un algoritm chiar mai rapid decit (2) in multe aplicatii, deoarece examineaza in multe cazuri numai o parte din caracterele textului.
• In 1980, R.M. Karp si M.O. Rabin au observat ca problema identificarii sabloanelor nu este mult diferita de o problema standard de cautare si au descoperit un algoritm aproape la fel de simplu ca cel al fortei brute, dar care are virtual intotdeauna timpul proportional cu M+N.
2 Algoritmul cautarii directe
int cautsablon1(char *p, char *a) { int i = 0, j = 0; /* i este pointerul in text */ int M = strlen(p); /* j este pointerul in sablon*/ int N = strlen(a);
do { while ((i < N) && (j<M) && (a[i]==p[j])) {i++;j++;} if (j==M) return i-M; i- = j-1; j = 0; } while (i<N);return i;
}
Algoritmul cautarii directe
int cautsablon2(char *p, char *a) { int i, j;
int M = strlen(p); int N = strlen(a); for (i=0, j=0; j<M && i<N; i++, j++) while (a[i] != p[j])
{ i- = j-1; j = 0;}
if (j==M) return i-M; else return i;
}
Se introduce santinela pla sfarsitul lui a
Algoritmul cautarii directe
• Proprietate: Algoritmul cautarii directe necesita, in cazul cel mai nefavorabil, un numar de maxim N*M comparatii de caractere.
• Timpul de rulare este proportional, pentru cazul cel mai defavorabil, cu M*(N-M+1), si cum M << N obtinem valoarea aproximativa N*M.
• Cazul cel mai nefavorabil poate apare, de exemplu, la prelucrarea imaginilor binare.
• In multe aplicatii de prelucrare a textelor, bucla interioara se executa rareori si timpul de rulare este proportional cu N+M.
3. Algoritmul Knuth-Morris-Pratt
Idee• startul fals al identificarii consta din caractere
deja cunoscute• a – sir, i – index in sir, N
• p – sablon, j – index in sablon, M
• Caz particular: primul caracter din sablon nu mai apare in sablon i
sir: 1000001000000 a
sablon: 1000000 p
j
nu i = i – j + 1 da – nu se modifica i si j = 0
Caz general
sir: 1010100111 a
sablon: 10100111 p
j=4
• i trebuie decrementat. Cu cat?
• Se poate cunoaste aceasta valoare – depinde de caracterul din sablon Daca nepotrivirea intre sir si sablon apare pe pozitia j in sablon, si Exista un k [0, j-1] pentru care
p[0] ... p[k-1] = p[j-k] ... p[j-1]
atunci o posibila identificare intre sir si sablon poate apare incepand cu caracterul din sir a[i-k] si caracterul din sablon p[j-k].
j = 4, k=2
p[0] p[1] = p[j-k] p[j-1], adica p[0] p[1] = p[2] p[3]
Caz generalTrebuie cautat k maxim cu aceasta proprietate.• Daca nu exista k cu ac. proprietatea atunci cautarea se
reia de la pozitia i si j=0.• Daca exista un astfel de k atunci
i = i – k, j = 0 .• Se calculeaza valorile unui vector next[M] pt pj p
= cu cat trebuie decrementat i la aparitia unei nepotriviri pe pozitia j
• next[j] = numarul maxim de caratere nr de la inceputul sablonului care identifica cu ultimele nr caractere din sablon pana la pozitia j-1 = kmax cu proprietatea anterioara
Vectorul next10100111 next[4] = 2 j = 4 Reluare cautare i = i – next[j], j = 0
Cum se calculeaza next[j]? Metoda informala, legata de implementare Metoda formala, bazata pe modelul formal al unui automat
finit determinist care recunoaste un sablon intr-un sir, pentru un alfabet dat.
• Se gliseaza o copie a primelor j caractere din sablon peste sablon de la stanga la dreapta, incapand cu primul caracter din copie suprapus cu al doilea caracter din sablon
• Se opreste glisarea daca: (a) toate caracterele suprapuse (pana la j-1) coincid sau (b) primul caracter al copiei ajunge pe pozitia j.
Vectorul next - exemplu j next[j] sablon si copie sablon 1 0 10100111 0 matches
12 0 10100111 0 matches
10 10
3 1 10100111 101 101 1 match
4 2 10100111 1010 1010 2 matches
5 0 10100111 10100 10100 10100 0 matches 10100
6 1 10100111 101001 1 match
7 1 10100111 1010011 1 match 1010011
Vectorul next• Caracterele identice definesc urmatorul loc posibil in care
sablonul se poate identifica cu sirul, dupa ce se gaseste o nepotrivire pe pozitia j (caracterul p[j]).
• Distanta cu care trebuie sa ne intoarcem in sir este exact next[j], adica numarul de caractere care coincid.
• Este convenabil next[0] = -1.
Cum facem sa nu ne intoarcem in sir?• a[i] != p[j] se reia de la i – next[j] si j = 0• Dar primele next[j] caractere incepand de la pozitia i – next[j]
din sir = primele next[j] caractere din sablon i nemodificat si j = next[j]
Exemplu
i = 4 ar trebui i = 2 si j = 0
sir: 1010100111 a
sablon: 10100111 p
j=4
next[4] = 2
acelasi efect daca i nemodificat si j = 2
Algoritmul Knuth-Morris-Prattint cautKMP(char *p, char *a) { int i, j; int M=strlen(p); int N=strlen(a); initnext(p); for (i=0, j=0; j<M && i<N; i++, j++) while ((j>=0) && (a[i] != p[j])) j = next[j]; if (j==M) return i-M; else return i; }
Obs: Pt. j = 0 si a[i] != p[0] este necesar ca i+, j = 0 deci next[0] = -1
Calculul vectorului next
void initnext(char *p)
{ int i,j, M=strlen(p);
next[0] = -1;
for (i=0, j=-1; i<M; i++, j++, next[i]=j)
while ((j>=0) && (p[i] != p[j]))
j=next[j];
}
Obs:
• Dupa incrementarile i++ si j++ avem p[i-j] … p[i-1] = p[0]…p[j-1]
• Identificarea efectueaza maxim M+N comparatii de caractere
Algoritm pentru sablon fix
sfs0 s1 s2 s3 s4 s5 s61 0 1 0 0 1 1 1
1
s7
Caracterele din sirul de intrare total diferite de cele din sablonsunt citite numai in s0, pe tranzitia s0 p s0, p p0.
Automatul citeste un nou caracter de intrare numai pentru tranzitiile “la dreapta”, i.e., daca caracterul din sir se potriveste cu sablonul.
Altfel automatul se intoarce fara a citi un nou caracter (acesta este motivul pentru care nu sunt etichetate si tranzitiile “la stinga”).
Algoritm pentru sablon fix
int cautKMP1(char *a) { int i=-1;
sm: i++; s0: if (a[i]!=‘1’) goto sm; i++; s1: if (a[i]!=‘0’) goto s0; i++; s2: if (a[i]!=‘1’) goto s0; i++; s3: if (a[i]!=‘0’) goto s1; i++; s4: if (a[i]!=‘0’) goto s2; i++; s5: if (a[i]!=‘1’) goto s0; i++; s6: if (a[i]!=‘1’) goto s1; i++; s7: if (a[i]!=‘1’) goto s1; i++; return i-8;}
Caracteristici KMP• Algoritmul KMP presupune precompilarea sablonului, ceea
ce este justificat daca M « N, adica textul este considerabil mai lung decat sablonul;
• Algoritmul KMP nu decrementeaza indexul din sir, proprietate folositoare mai ales pentru cautarile pe suport extern;
• Algoritmul KMP da rezultate bune daca o nepotrivire a aparut dupa o identificare partiala de o anumita lungime. In cazul in care aceste situatii sunt o exceptie, algoritmul nu aduce imbunatatiri semnificative;
• Algoritmul KMP imbunatateste timpul cazului cel mai nefavorabil, dar nu si timpul mediu.
4 Algoritmul Boyer-Moore
UN EXEMPLU DE CAUTARE RAPIDA
UTARE
UTARE
UTARE
UTARE
UTARE
• Potrivit daca intoarcerea in text nu este dificila
Algoritmul Boyer-Moore
• Vectorul skip – se defineste pentru fiecare caracter din alfabet
• arata, pentru fiecare caracter din alfabet, cat de mult se sare (se deplaseaza sablonul la dreapta) in sir daca acest caracter a provocat nepotrivirea
• rutina initskip – initializeaza skip:
• skip[index(p[j])] = M-j-1, j=0,M-1 pentru caracterele din sablon
• skip[index(c)] = M pentru restul de caractere din alfabet
Algoritmul Boyer-Moore
int caut_BM(char *p, char*a) { int i, j, t;
int M=strlen(p), N = strlen(a); initskip(p); for (i=M-1, j=M-1; j>=0; i--, j--) while (a[i]!=p[j])
{ t = skip[index(a[i])]; i+ = (M-j > t) ? M-j : t; if (i >= N) return N; j = M-1;
return i+1;
}
Algoritmul Boyer-Moore
• Combinarea a doua metode pentru a afla exact cu cat trebuie deplasat la dreapta sirul: metoda prezentata si metoda vectorului next din algoritmul Knuth-Morris-Prat, in varianta de la dreapta la stinga, pentru ca apoi sa se aleaga in skip cea mai mare valoare.
• In conditiile acestei modificari, este valabila urmatoarea proprietate.
• Proprietate: Algoritmul Boyer-Moore face cel mult M+N comparatii de caractere si foloseste N/M pasi, daca alfabetul nu este mic si sablonul este scurt.
5. Algoritmul Rabin-Karp
Idee• Considera textul ca fiind o memorie mare si
trateaza fiecare secventa de M caractere a textului ca o cheie intr-o tabela de dispersie (hash).
• Trebuie sa calculam functia de dispersie pentru toate secventele posibile de M caractere consecutive din text si sa verificam daca valorile obtinute sunt egale cu functia de dispersie a sablonului.
• Artificiu pt. a nu tine toata tabela de dispersie in memorie.
Calculul functiei hash
• h(k)=k mod q, unde k este numarul de caractere din sir, iar q (dimensiunea tabelei) este un numar prim mare.
• q poate fi chiar foarte mare deoarece tabela hash nu se tine in memorie
• Functia de dispersie pentru pozitia i din text se calculeaza pe baza valorii acestei functii pentru pozitia i-1
• Se transforma grupuri de M caractere in numere, prin impachetare ca reprezentare intr-o anumita baza
• Aceasta corespund la a scrie caracterele ca numere in baza d, unde d este numarul de caractere posibile din alfabet.
Calculul functie hash
• O secventa de M caractere consecutive a[i]…a[i+M-1] corespunde:
y = a[i]*dM-1 + a[i-1]*dM-2 + … + a[i+M-1]• Presupunem ca stim valoarea lui h(y) = y mod q.• Deplasarea in text cu o pozitie la dreapta corespunde
inlocuirii lui y cu
y1 = (y - a[i]*dM-1)*d + a[i+M]• Consideram d=32 (sau orice multiplu de 2 corespunzator)• Cum facem sa nu memoram valorile functiei hash pentru
toate grupurile de M caractere din sir?
Calculul functiei hash pt. y1 pe baza lui ySe cunoaste ca:
(a + b) mod q = (a mod q + b mod q) mod q
(a * b) mod q = (a * (b mod q)) mod q
Se doreste sa se arate ca:
(a0 * x + a1) mod q = ((a0 mod q) * x + a1) mod q
Demonstratie:
(a0 * x + a1) mod q = ((a0 * x) mod q + a1 mod q) mod q =
= [(x(a0 mod q)) mod q + a1 mod q] mod q = ((a0 mod q) x + a1) mod q
Noul sir impachetat y1 se obtine din y astfel (slide precedent):
y1 = (y - a[i] * dM-1) * d + a[i+M]
Cum se calculeaza y1 mod q pe baza lui y :
y1 mod q = ((y – a[i] * dM-1) * d + a[i+M]) mod q
= ( (y – a[i] * dM-1) mod q * d + a[i+m]) mod q
Algoritmul Rabin-Karpint caut_RK(char *p, char *a){ int i;long int dM=1, h1=0, h2=0;
int M=strlen(p), N=strlen(a);
for (i=1; i<M; i++) dM = (d*dM) % q;
// calculeaza d**(M-1) mod q in dM
for (i=0; i<M; i++)
{h1 = (h1*d + index(p[i]))%q;
// functia hash pt sablon
h2 = (h2*d + index(a[i]))%q;
// functia hash pt text
}
for (i=0; h1!=h2; i++)
{h2 = (h2 + d*q - index(a[i])*dM)%q;
// d*q se adauga pt a mentine expresia >0
h2 = (h2 * d + index(a[i+M]))%q;
if (i > (N-M)) return N;
}
return i;}
Caracteristici RK• Algoritmul Rabin-Karp are destul de probabil o complexitate
timp liniara.
• Algoritmul are timpul proportional cu N+M, dar el gaseste doua siruri cu valori de dispersie egale.
• In aceste conditii, trebuie sa comparam sablonul cu cele M caractere din sir, pentru cazul coliziunilor.
• Deci, din punct de vedere teoretic, acest algoritm ar putea sa fie tot O(NM), in cazul cel mai defavorabil, in care toate sabloanele gasite ar fi coliziuni putin probabil, deoarece q este mare; in practica, algoritmul foloseste N+M pasi.
• Daca sablonul se cauta de mai multe ori, el poate fi considerat o cheie, iar textul poate fi organizat in stucturi eficiente de cautare, cum ar fi arbori binari, tabele de dispersie, etc.
6. Algoritmul deplaseaza-aduna
Idee• Algoritmul reprezinta starea cautarii ca un
numar, si fiecare pas in cautare (identificare) este descris printr-un numar de operatii aritmetice si logice
• Acest lucru este posibil daca numerele folosite sunt suficient de mari pentru a putea reprezenta toate starile posibile in cursul rularii
Algoritmul deplaseaza-aduna
Se poate generaliza usor la urmatoarele cazuri:
1. “Don’t care symbols”, deci identificarea cu orice caracter pe o pozitie
2. Identificarea cu un caracter dintr-o clasa de caractere (un interval)
3. Identificarea cu un caracter din complementul unei clase.
4. Identificarea cu un numar dat K de nepotriviri
5. Identificarea mai multor sabloane in paralel.
Ipotezea - sirul (de lungime N) in care se executa cautare
p - sablonul (de lungime M)
i - index in sablon
j - index in text
• Se foloseste un vector cu M componente, care reprezinta cele M posibile stari in cautare: indexul i indica starea intre pozitiile 1…i ale sablonului si pozitiile (j-i+1)…j ale textului
• M comparatoare de siruri care ruleaza in paralel si citesc concurent aceeasi pozitie din sir
Ipoteze• starei - p[1]…p[i] ? a[j-i+1] … a[j]
• {sji}, i=1,M – multime de stari dupa citirea
caracterului j din sir
• sji = numarul de nepotriviri intre
p[1]…p[i] si a[j-i+1] …a[j]
• Apare identificare daca sjM = 0
Exemplu• Pozitia j-1 de cautare in text – se
calculeaza sj-1i
i i sji-1
sablon a b a b c 1 1
sablon a b a b c 2 0
sablon a b a b c 3 3
sablon a b a b c 4 0
sablon a b a b c 5 5
sir c b b a b a b a b c a b a
j-1
• Sablonul ababc (M=5)
• Sir: cbbabababcaba
sji = numarul de nepotriviri intre p[1]…p[i] si a[j-i+1] …a[j]
Exemplu• Se avanseaza in text la
pozitia j – se calculeaza sji
j
i i sj-1i Ti[a] sj
i
a b a b c 0 0
a b a b c 1 1 0 0
a b a b c 2 0 1 2
a b a b c 3 3 0 0
a b a b c 4 0 1 4
c b b a b a b a b c a b a 5 5 1 1
Exemplu• Se avanseaza in text la
pozitia j – se calculeaza sji
j
i i sj-1i Ti[a] sj
i
a b a b c 0 0
a b a b c 1 1 0 0
a b a b c 2 0 1 2
a b a b c 3 3 0 0
a b a b c 4 0 1 4
c b b a b a b a b c a b a 5 5 1 1
Definitii• Se defineste T[x] pentru x • Ti[x] = 0 daca pi = x, i=1,M
= 1 in caz contrar(prin compararea fiecarui caracter x din alfabet cu p[0]
…p[M])
• Se observa relatia
sji = sj-1
i-1 + Ti[aj] i=1,M• Identificarea apare daca sj
M = 0• Cuvant w• b biti necesari pentru a reprezenta o stare
Definitii
• Vector de stari reprezentat ca un numar in baza 2b
• Pentru identificare exacta b = 1
• sji = 0 daca p[0]..p[i] = a[j-i+1]..a[j]
= 1 in caz contrar
• sjM = 0 atunci starej < 2M-1
1
01 2
M
i
ibjisstare
j
DefinitiiActualizare la citirea unui nou caracter:• deplasez vect. de stari cu b pozitii la stanga = avans
cu 1 pozitie in text• actualizez starile pe baza lui T si fac o operatie
potrivita
• starej = (starej << b) op T[aj]
• Obs: Operatia nu trebuie sa produca transport pt. sji
care sa afecteze sji+1
• Pentru b=1 op = sau logic
Definitii• Reprezint T tot ca un numar in baza 2b
• unde, x, (cond) = 1 daca cond adevarata= 0 in caz contrar
Exemplub=1, = {a, b, c, d} p = ababcT[a] = 11010 T[b] = 10101T[c] = 01111 T[d] = 11111starea initiala este 11111
T x x pib i
i
M
[ ] ( )
10
1
2
Exemplu
Sablon ababc
Sir a b d a b a b a b c
T[x] 11010 10101 11111 11010 10101 …………..
Stare 11110 11101 11111 11110 11101 ….
(11111)
starej-1 << b | T[aj] = starej
Algoritmul deplaseaza-aduna
#define CUVANT 32
#define B 1
#define MAXSIM 128
In variabila lim vom calcula 2B(M-1)
Algoritmul deplaseaza-adunaint caut_shadd(char *p,char *a) {unsigned int state, lim, first, initial; unsigned int T[MAXSIM]; int i, j, matches, M=strlen(p), N=strlen(a); if(M>CUVINT) {printf("\n Error: Utilizati dim. sablon<dim.
cuvint\n"); return -1; } /* preprocesare */ for(i=0; i<MAXSIM; i++) T[i]=~0; lim=0; for(i=0,j=1; i<M; i++,j<<=B) { T[p[i]] &= ~j; lim |= j; } lim = ~(lim>>B);
Algoritmul deplaseaza-aduna - continuare
/* cautare */ matches=0; initial = ~0; first=p[0]; i=0; while (i<N) { while(i<N && a[i]!=first) i++; state=initial; do { state=(state<<B) | T[a[i]]; if (state<lim) matches++; /* identificare pe poz i-M+1 */ i++; } while(state!=initial); } return matches;}
Caracteristici• Este nevoie de b*M*|| biti suplimentari de memorie si daca b*M w,
atunci este nevoie de || cuvinte de memorie suplimentare.
• Construirea tabelei T se face intr‑un timp proportional cu:
• Complexitatea cautarii, pentru cazul cel mai nefavorabil si pentru cazul mediu este
unde
este timpul necesar calculului unui numar constant de operatii cu intregi de M*b biti, folosind un cuvint de lungime w biti.
• In practica (sabloane de 32 sa 64 biti), timpul mediu si cel mai nefavorabil este O(N).
OM b
wM
OM b
wN
M b
w
Extinderea algoritmului la identificarea
claselor de sabloane • x
• * [x1x2…xn] - clasa {x1} sau {x1x2…xn} - complement
Extinderea algoritmului la identificarea
claselor de sabloane Exemplu: = {a, b, c, d}.
Sablonul [Aa]b{b}*{bd} se potriveste peste (sub)sirurile Abaca, abcda, dar nu si peste abbac sau ababb.
Doua dimensiuni: lungimea M a sablonului si dimensiunea descrierii sablonului, notata cu M1.
Extinderea algoritmului la identificarea
claselor de sabloane
Exemplu: = {a, b, c, d}.
Sablonul este a{b}[ab]b{abc}.
M = 5 si M1 = 15.
T[a] = 11000 T[b] = 10011
T[c] = 11101 T[d] = 01101
T x x clasaib i
i
M
[ ] ( )
10
1
2
Algoritmul pt calculul lui Tvalinit 111...111 (w biti)for i = 1 to M do
if p1 = ‘*’ or pi este un complement
then valinit valinit & 111…0i…111
endfor
for i = 1 to || do T[xi] valinitendfor
for i = 1 to M do
foreach x pi do
if pi este un complement
then T[x] T[x] | 000…1i…000
else T[x] T[x] & 111…0i…111
endforeach
endfor
70
Implementarea calculului lui T
void tinit(char *p)
{ unsigned int T[MAXSYM], initval, mask=1;
int i=0, M=0, M1=strlen(p);
/* calculeaza initval<-initval & 111..0i..111 */
initval=~0;
while(i<M1)
{ M++;
if(p[i]=='*')initval&=~mask;
else if(p[i]=='{'){initval&=~mask;
while(p[i]!=EOS &&
p[i]!='}') i++;}
else if(p[i]=='[')
while(p[i]!=EOS && p[i]!=']')i++;
mask<<=B;i++;
}71
Implementarea calculului lui T - continuare
/* calculeza T[xi]<-initval pentru fiecare xi din alfabet*/
for(i=0;i<MAXSYM;i++)T[i]=initval;/* Actualizeaza T[x], cu x din sablon */ i=0; mask=1; while(i<M1)
{ if(p[i]=='{') while(p[++i]!='}') T[p[i]]|=mask;
else if(p[i]=='[')while(p[++i]!=']')
T[p[i]]&=~mask; else T[p[i]]&=~mask;
i++; mask<<=B;}
72
Identificarea cu max k nepotriviriFiecare stare individuala poate fi reprezentata printr-un numar de maxim O(logM) biti.
- daca sjM k, am gasit o identificare cu maximum k
nepotriviri
· - operatorul op este adunarea
- Deoarece ne intereseaza numai k nepotriviri, este suficient sa alegem
b = sup|log2(k+1)| + 1
Problema transportului – un bit de transport (overflow) pt fiecare stare
73
Identificarea cu max k nepotriviri- Obtinerea unei noi stari:
starej+1=(starej << b) + T[xj+1]
- Conditia de identificare cu max k nepotriviri
sjM + overfj < (k+1) * 2b(M-1)
Cazul • Sablonul ababc
• Alfabetul {a, b, c, d}
• T construit anterior
• k = 2, b = 3 (b = sup|log2(k+1)| + 1)
74
Exemplu• Sablonul ababc• Alfabetul {a, b, c, d}• T construit anterior• k = 2, b = 3• starea initiala 00000• overflow initial 44444
sir a b d a bT[x] 11010 10101 11111 11010 10101stare 11010 20201 13121 02220 32301overf 44440 44400 44000 40000 00000
sir a b a b cT[x] 11010 10101 11010 10101 01111stare 30020 10301 10020 10301 00121overf 04000 40000 04000 40000 04000
75
Algoritmul pentru max k nepotriviri
mask 1Mb0…0…………12b0…01b0…0
lim (k+1) << (M-1)*bstare 0 overf maskfor i = 1 to N do
stare (stare << b) + T[ai]
overf (overf << b) | (stare & mask) stare stare & ~mask if (stare+overf) < lim
then identificare la pozitia i-M+1
endfor
76