[7] String Matching1
-
Upload
eirdnocotim -
Category
Documents
-
view
48 -
download
4
description
Transcript of [7] String Matching1
-
Proiectarea algoritmilor: Cautare peste siruri
Dorel Lucanu
Faculty of Computer ScienceAlexandru Ioan Cuza University, Iasi, Romania
PA 2013/2014
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 1 / 52
-
Outline
1 Introducere
2 Algoritmul Rabin-Karp
3 Algoritmul Boyer-Moore
4 Algoritmul Knuth-Morris-Pratt
5 Algoritmul Z
6 Algoritmul Boyer-Moore revizuit
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 2 / 52
-
Introducere
Plan
1 Introducere
2 Algoritmul Rabin-Karp
3 Algoritmul Boyer-Moore
4 Algoritmul Knuth-Morris-Pratt
5 Algoritmul Z
6 Algoritmul Boyer-Moore revizuit
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 3 / 52
-
Introducere
Problema
Input Doua siruri s = s0 sn1, numit subiect sau text, sip = p0 pm1, numit pattern.Output Prima aparitie a lui a patternului p n textul s, daca exista.
Varianta: gasirea tuturor aparitiilor.
Algoritmul de cautare secventiala naiva are complexitatea O(n m).
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 4 / 52
-
Introducere
Putin istoric
Algoritmii care rezolva problema de cautarii peste siruri au o istorie interesanta.In 1970, S.A. Cook a demonstrat un rezultat teoretic despre un anumit tipabstract de masina, unde se presupunea existenta unui algoritm de cautare pestesiruri ce necesita un timp proportional cu n + m n cazul cel mai nefavorabil. D.E.Knuth si V.R. Pratt au utilizat constructia laborioasa din teorema lui Cook si auelaborat un algoritm care, mai apoi, a fost rafinat ntr-un algoritm practic sisimplu. J.H. Morris a descoperit acelasi algoritm n timpul implementarii unuieditor de texte. Este unul dintre numeroasele exemple cand un rezultat purteoretic poate conduce la rezultate cu aplicabilitate imediata. Algoritmul dat deKnuth, Morris si Pratt a fost publicat de abia n 1976. Intre timp, R.S. Boyer siJ.S. Moore (si indepedent W. Gosper) au descoperit un algoritm care este multmai rapid n multe situatii. In 1980, R.M. Karp si M.O. Rabin au proiectat unalgoritm cu o descriere foarte simpla si care poate fi extins la texte sipattern-uri bidimensionale, deci foarte util la procesarea imaginilor grafice.
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 5 / 52
-
Algoritmul Rabin-Karp
Plan
1 Introducere
2 Algoritmul Rabin-Karp
3 Algoritmul Boyer-Moore
4 Algoritmul Knuth-Morris-Pratt
5 Algoritmul Z
6 Algoritmul Boyer-Moore revizuit
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 6 / 52
-
Algoritmul Rabin-Karp
Descriere
Acest algoritm utilizeaza tehnica tabelelor de dispersie (hash). Un simbol este osecventa de m caractere. Sa ne imaginam ca toate simbolurile posibile suntmemorate ntr-o tabela de dispersie foarte mare, astfel ncat nu exista coliziune.A testa daca pattern-ul p coincide cu un subsir de lungime m din text esteechivalent cu a testa daca functia de dispersie h da aceeasi valoare pentru ambelesimboluri. Exista avantajul ca pentru pattern functia de dispersie este calculatao singura data. Pentru ca algoritmul sa fie eficient, functia de dispersie trebuiedefinita n asa fel ncat, atunci cand se face o deplasare la dreapta n text, calcululvalorii functiei pentru urmatorul simbol sa fie cat mai simplu. Timpul necesarefectuarii acestui calcul trebuie sa fie cu mult mai mic decat cel necesarcompararii a doua siruri de lungime m.
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 7 / 52
-
Algoritmul Rabin-Karp
Functia de dispersie (hash)
Un mod de a defini functia de dispersie este urmatorul: Se considera fiecare sir dem caractere ca fiind reprezentarea unui numar ntreg n baza d , unde d estenumarul maxim de caractere. Numarul zecimal corespunzator siruluis[i ..i + m 1] este:
x = s[i ]dm1 + s[i + 1]dm2 + + s[i + m 1]
Functia de dispersie h va fi definita prin h(s[i ..i+m1]) = x mod q, unde q esteun numar prim foarte mare. O deplasare la dreapta n text corespunde nlocuiriilui x cu:
(x s[i ]dm1)d + s[i + m]In formulele de mai sus s-a presupus caracterele 0, . . . , d 1. Pentru a interpretacaracterele textului ca fiind cifre, consideram o functie index care asociazafiecarui caracter numarul sau de ordine n alfabet.
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 8 / 52
TeaHighlight
-
Algoritmul Rabin-Karp
Tabela hash
Pentru a evita lucrul cu numere mari, operatiile se executa modulo unnumar natural q;
Ne putem imagina ca q este dimensiunea tabelei hash carememoreaza simbolurile (= secventele de m caractere) din s.
Pentru o dispersie buna, q trebuie sa fie un numar prim mare.
Deoarece pot exista coliziuni, se utiliza o functie eq(p, s, j, m)care compara caracter cu caracter; aceasta functie este apelata doarcand exista egalitate a valorilor hash.
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 9 / 52
-
Algoritmul Rabin-Karp
Algoritmul Rabin-Karp
rk(s, n, p, m) {
// preprocesare
for (j = 1; j < m; j++) dM = (d * dM) % q;
for (j = 0; j < m; j++) {
hp = (hp*d + p[j]) % q; // hash pentru pattern
hs = (hs*d + s[j]) % q; // hash pentru text
}
// cautare
if (hp == hs && eq(p, s, 0, m)) return 0;
for (i = m; i < n; i++) {
hs = (hs - s[i-m]) % q;
hs = (hs*d + s[i]) % q;
if (hs == hp && eq(p, s, i-m, m)) return i - m + 1;
}
return -1;
}
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 10 / 52
TeaHighlight
TeaHighlight
TeaHighlight
TeaHighlight
-
Algoritmul Rabin-Karp
Analiza
Desi teoretic, n cazul cel mai nefavorabil, algoritmul RK are o complexitatetimp proportionala cu n m, n practica s-a dovedit a executa aproximativn + m pasi.
Timpul mediu se poate calcula luand q (dimensiunea tabelei) generataleatoriu (algoritm Las Vegas).
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 11 / 52
-
Algoritmul Rabin-Karp
Algoritmul Rabin-Karp: o posibila implementare C#define REHASH(a, b, h) ((((h)-(a)*dM)
-
Algoritmul Rabin-Karp
Analiza impelementarii C
S-a presupus ca d = 2. Daca d = 2k , atunci se poate utiliza relatiadm1 = (2k)m1 = (2m1)k .Daca long este reprezentat pe 64 biti, atunci dM este 0 pentrum = 65. Deci trebuie sa avem m 65k .Nu mai este utilizat numarul prim q deoarece se utilizeaza aritmeticamodulara peste long.
O implementare Java cu q determinat aleatoriu (Robert Sedgewick andKevin Wayne) poate fi gasita la adresahttp://algs4.cs.princeton.edu/53substring/RabinKarp.java.html.
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 13 / 52
-
Algoritmul Boyer-Moore
Plan
1 Introducere
2 Algoritmul Rabin-Karp
3 Algoritmul Boyer-Moore
4 Algoritmul Knuth-Morris-Pratt
5 Algoritmul Z
6 Algoritmul Boyer-Moore revizuit
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 14 / 52
-
Algoritmul Boyer-Moore
Exemplu
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
V I S U L U N E I N O P T I D E
6=I A R
19 20 21 22 23 24
I A R N A
1
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 15 / 52
TeaHighlight
TeaHighlight
TeaHighlight
-
Algoritmul Boyer-Moore
Exemplu
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
V I S U L U N E I N O P T I D E
6=I A R
19 20 21 22 23 24
I A R N A
2
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 15 / 52
-
Algoritmul Boyer-Moore
Exemplu
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
V I S U L U N E I N O P T I D E
6=I A R
19 20 21 22 23 24
I A R N A
3
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 15 / 52
-
Algoritmul Boyer-Moore
Exemplu
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
V I S U L U N E I N O P T I D E
6=I A R
19 20 21 22 23 24
I A R N A
4
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 15 / 52
-
Algoritmul Boyer-Moore
Exemplu
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
V I S U L U N E I N O P T I D E
6=I A R
19 20 21 22 23 24
I A R N A
5
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 15 / 52
-
Algoritmul Boyer-Moore
Exemplu
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
V I S U L U N E I N O P T I D E
6=I A R
19 20 21 22 23 24
I A R N A
6
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 15 / 52
-
Algoritmul Boyer-Moore
Exemplu
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
V I S U L U N E I N O P T I D E
I
19 20 21 22 23 24
I A R N A
6=A R
7
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 15 / 52
-
Algoritmul Boyer-Moore
Exemplu
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
V I S U L U N E I N O P T I D E
19 20 21 22 23 24
I A R N A=
I A R
8
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 15 / 52
TeaHighlight
TeaHighlight
-
Algoritmul Boyer-Moore
Exemplu
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
V I S U L U N E I N O P T I D E
19 20 21 22 23 24
I A R N A=
I A R
9
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 15 / 52
TeaHighlight
TeaHighlight
-
Algoritmul Boyer-Moore
Exemplu
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
V I S U L U N E I N O P T I D E
19 20 21 22 23 24
I A R N A=
I A R
10
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 15 / 52
TeaHighlight
TeaHighlight
-
Algoritmul Boyer-Moore
Exemplu
Prima data se compara R (ultimul caracter din pattern) cu S (al treilea caracterdin text). Deoarece S nu apare n pattern, se deplaseaza pattern-ul cu treipozitii (lungimea sa) la dreapta. Apoi se compara R cu caracterul spatiu. Nicicaracterul spatiu nu apare n pattern asa ca acesta se deplaseaza din nou ladreapta cu trei pozitii. Procesul continua pana cand R este comparat cu I (al21-lea caracter din text). Deoarece I apare n pattern pe prima pozitie sedeplaseaza pattern-ul la dreapta cu doua pozitii. Apoi se compara R cu R, deciexista potrivire. Se continua comparatia cu penultimul caracter din pattern (defapt al doilea) si precedentul din text (al 22-lea). Se obtine din nou potrivire si secompara urmatoarele doua caractere de la stanga (primul din pattern si al21-lea din text). Deoarece exista potrivire si pattern-ul a fost parcurs complet,rezulta ca s-a determinat prima aparitie a pattern-ului n text.
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 16 / 52
-
Algoritmul Boyer-Moore
Regula caracterului rau 1/3
Engleza: bad character shift rule
Evita repetarea comparatiilor fara succes n cazul caracterelor care nu aparn pattern sau ntr-un sufix (maximal) al acestuia.
salt[C ] =
m pozitia ultimei aparitii , daca C apare n patterna lui C n pattern
m , altfel
(alternativ, salt(C ) = max({0} {i < m | p[i ] = C}))
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 17 / 52
-
Algoritmul Boyer-Moore
Regula caracterului rau 2/3
i+salt[A] i
u A
A B A nu e in u
j caz 1: salt[A] m-j
i+m-j i
u A
A B A e in u
j caz 2: salt[A] < m-j
Primul caz: i = i + salt[s[i]];Al doilea caz: i = i + m - j;
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 18 / 52
-
Algoritmul Boyer-Moore
Regula caracterului rau 3/3
Daca p[j ] 6= s[i ] = C ,1 daca aparitia cea mai din dreapta a lui C n p este k < j , p[k] si s[i ]
sunt aliniate (i = i + salt[s[i]])
2 daca aparitia cea mai din dreapta a lui C n p este k > j , p estetranslatat la dreapta cu o pozitie (i = i + m - j)
3 daca C nu apare n p, patternul p este aliniat cu s[i + 1..i + m] (i = i+ m). Devine caz particular al primului daca salt[s[i ]] = m.
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 19 / 52
-
Algoritmul Boyer-Moore
Algoritmul Boyer-Moore (varianta 1)
BM(s, n, p, m, salt) {
i = m-1; j = m-1;
repeat
if (s[i] = p[j]) {
i = i-1;
j = j-1;
}
else if ((m-j) > salt[s[i]]) i = i+m-j;
else i = i+salt[s[i]];
j = m-1;
until (jn-1);
if (j
-
Algoritmul Boyer-Moore
Analiza
Pentru cazul cel mai nefavorabil are complexitatea O(m n).
In schimb are o comprtare buna n medie.
Vom vedea o alta versiune mai tarziu care este liniara.
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 21 / 52
-
Algoritmul Knuth-Morris-Pratt
Plan
1 Introducere
2 Algoritmul Rabin-Karp
3 Algoritmul Boyer-Moore
4 Algoritmul Knuth-Morris-Pratt
5 Algoritmul Z
6 Algoritmul Boyer-Moore revizuit
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 22 / 52
-
Algoritmul Knuth-Morris-Pratt
Descriere
Ideea algoritmului este urmatoarea: Atunci cand s-a ntalnit o nepotrivire, i.e.caracterul curent pj din pattern este diferit de caracterul curent si din text,caracterele si1, . . . , sij+1 din text sunt cunoscute deoarece ele exista npattern. Pozitia de start pentru urmatoarea comparatie dintre pattern si textpoate fi determinata exploatand aceasta informatie. Ca urmare, ntoarcerile ntext sunt eliminate. Astfel ca algoritmul va consta din doua etape:
1 Se proceseaza mai ntai pattern-ul n O(m) si se creeaza o structura dedate.
2 Folosind structura de date creata la prima etapa, se proceseaza textul fara amai executa ntoarceri.
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 23 / 52
-
Algoritmul Knuth-Morris-Pratt
KMP: ideea
. . . a b a b * . . .
6=a b a b c
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 24 / 52
-
Algoritmul Knuth-Morris-Pratt
KMP: ideea
. . . a b a b * . . .
??
a b a b c
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 24 / 52
-
Algoritmul Knuth-Morris-Pratt
KMP: ideea (cont)
subiect
pattern
i
j
. . .
. . .
subiect
pattern
i
j k 0
. . . . . .
. . . . . . . . .
subiect
pattern
j k 0
. . . . . .
. . . . . . . . .
i
u u
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 25 / 52
-
Algoritmul Knuth-Morris-Pratt
KMP: ideea (cont)
subiect
pattern
i
j
. . .
. . .
subiect
pattern
i
j k 0
. . . . . .
. . . . . . . . .
subiect
pattern
j k 0
. . . . . .
. . . . . . . . .
i
u u
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 25 / 52
-
Algoritmul Knuth-Morris-Pratt
KMP: ideea (cont)
subiect
pattern
i
j
. . .
. . .
subiect
pattern
i
j k 0
. . . . . .
. . . . . . . . .
subiect
pattern
j k 0
. . . . . .
. . . . . . . . .
i
u u
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 25 / 52
-
Algoritmul Knuth-Morris-Pratt
Studierea domeniului problemei
u v v u este prefix si sufix al lui vu @ v u v v si u 6= vlpps(v) = cel mai lung prefix si sufix propriu al lui vFormal:
lpps(v) v v(u)u v v = u v lpps(v)
Notatie: lpps i (v) = lpps(. . . lpps(v) . . .) de i-orilpps0(v) = v
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 26 / 52
-
Algoritmul Knuth-Morris-Pratt
Studierea domeniului problemei (cont.)
Proprietati ale lui lpps(v):
Propozitie
lpps i+1(v) @ lpps i (v) @ @ lpps0(v) = v
Teorema
(u, v)u v v (i 0)u = lpps i (v)
Demonstratie. Prin inductie dupa lungimea lui |v | (pe tabla). sfdem
Corolar
(u, v)v 6= u @ v (i > 0)u = lpps i (v).
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 27 / 52
-
Algoritmul Knuth-Morris-Pratt
Functia esec - descriere
f [j ] = k daca si numai daca |lpps(p[0..j 1])| = kDaca j = 0 atunci f [0] = 1 (putem presupune ca p0 p1desemneaza sirul vid);
Presupunem j > 0 si ca f [0], . . . , f [j 1] sunt calculate. Consideramcazul lpps(p[0..j 1]) 6= (f [j ] 6= 0).Rezulta ca lpps(p[0..j 1]) este de forma up[j 1].Deoarece u v p[0..j 2], exista i 0, u = lpps i (p[0..j 2]).Deci u este cel mai mare subsir cu u = lpps i (p[0..j 2]) sip[|u|] = p[j 1].De aici obtinem ca f [j ] = k + 1, unde k este cel mai mare cuproprietatile: exista i 0, f [i ] = k si p[k] = p[j 1].
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 28 / 52
-
Algoritmul Knuth-Morris-Pratt
Functia esec - algoritm
determinaF (p, m, f) {
f[0] = -1;
for (j = 1; j< m; j = j+1) {
k = f[j-1];
while ((k != -1) && (p[j-1] != p[k]))
k = f[k];
f[j] = k+1;
}
}
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 29 / 52
-
Algoritmul Knuth-Morris-Pratt
Exemplu
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
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 30 / 52
-
Algoritmul Knuth-Morris-Pratt
Analiza
Invariantul instructiunii for: la sfarsitul executiei fiecarei bucle for, f [j ]este lungimea cel mai lung prefix al lui p care se potriveste n p la pozitiade sfarsit j 1, adica f [j ] = |lpps(p[0..j 1]|.
Timpul n cazul cel mai nefavorabil este O(m). Daca aplatizam for si whilentr-o singura bucla while, la fiecare pas se mareste cu cel putin o unitate jsau j k . Rezulta ca vor fi maxim 2m iteratii.
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 31 / 52
-
Algoritmul Knuth-Morris-Pratt
De la algoritmul pentru f [] la algoritmul KMP
subiect
pattern
i
j k 0
. . . . . .
. . . . . . . . .
subiect
pattern
j k 0
. . . . . .
. . . . . . . . .
i
u u
u
Se considera s[i ] n loc de p[j ] si j n loc de k .
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 32 / 52
-
Algoritmul Knuth-Morris-Pratt
Algoritmul KMP
KMP(s, n, p, m, f) {
i = 0;
j = 0;
while (i < n) {
while (j != -1) && (p[j] != s[i])
j = f[j];
if (j = m-1)
return i-m+1; /* gasit p in s */
else {
i = i+1;
j = j+1;
}
}
return -1; /* p nu apare in s */
}
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 33 / 52
-
Algoritmul Knuth-Morris-Pratt
Analiza
Invariantul primei instructiuni while: la sfarsitul executiei fiecarei buclewhile, p[0..j 1] este cel mai lung prefix al lui p care se potriveste n s lapozitia de sfarsit i 1.Rezulta ca dupa terminarea instructiunii while interioare, p[0..j ] este celmai lung prefix al lui p care se potriveste n s la pozitia de sfarsit i .
Timpul n cazul cel mai nefavorabil este O(n + m). Daca aplatizam celedoua bucle while ntr-o singura bucla, la fiecare pas se mareste cu cel putino unitate i sau i j . Rezulta ca vor fi maxim m + n iteratii.
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 34 / 52
-
Algoritmul Z
Plan
1 Introducere
2 Algoritmul Rabin-Karp
3 Algoritmul Boyer-Moore
4 Algoritmul Knuth-Morris-Pratt
5 Algoritmul Z
6 Algoritmul Boyer-Moore revizuit
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 35 / 52
-
Algoritmul Z
Domeniul problemei: definitia pentru Z [j ]
Fie p[0..m 1] un sir.Z [j ] = lungimea celui mai lung subsir care pleaca din p[j ] si este prefix allui p.
Exercitiu. Sa se dea o definitie formala pentru Z [j ].
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 36 / 52
-
Algoritmul Z
Algoritmul Z - invariant
j L R
u u
Algorimul Z, care calculeaza valorile Z [j ], j = 1, . . . ,m 1, mentineurmatorul invariant:[L,R] este un interval cu R maxim astfel ncat1 L j R sip[L..R] este prefix al lui p.
Daca nu exista un astfel de interval atunci L = R = 1.
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 37 / 52
-
Algoritmul Z
Algoritmul Z - iteratia curenta 1/3
Presupunem toate valorile pana la Z [j 1] calculate.Pentru calculul lui Z [j ] distingem urmatoarele cazuri:
j > R (i.e. j 1 = R). Nu exista un prefix al lui p care se termina laj sau dupa j .Se reseteaza L si R pentru p[0..] si p[j ..]:
L = R = j; // reseteaza L si R
while (R < M && p[R-L] == p[R])
R = R + 1;
// p[j..R-1] cel mai lung prefix
Z[j] = R - L; // = |p[j..R-1]|
R = R -1;
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 38 / 52
-
Algoritmul Z
Algoritmul Z - iteratia curenta 2/3
j R. [L,R] se extinde. Fie k = j L. AvemZ [j ] min{Z [k],R j + 1} (explicatii pe tabla)Distingem subcazurile:
Z [k] < R j + 1. Nu exista prefix mai lung care pleaca din j :Z[j] = Z[k];
Z [k] R j + 1. Exista un prefix mai lung ce pleaca din j . Sereseteaza L la j si se calculeaza noul R pornind de la R + 1:
L = j;
while (R < m && p[R-L] == p[R])
R = R + 1;
// p[L..R-1] cel mai lung prefix
Z[j] = R - L; // = |p[L..R-1]|
R = R - 1;
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 39 / 52
-
Algoritmul Z
Algoritmul Z - iteratia curenta 3/3asamblam cazurile:
if (j > R) {
L = R = j;
while (R < M && p[R-L] == p[R])
R = R + 1;
Z[j] = R - L;
R = R -1;
} else {
k = j - L;
if (Z[k] < R-j+1)
Z[j] = Z[k];
else {
L = j;
while (R < m && p[R-L] == p[R])
R = R + 1;
Z[j] = R - L;
R = R - 1;
}
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 40 / 52
-
Algoritmul Boyer-Moore revizuit
Plan
1 Introducere
2 Algoritmul Rabin-Karp
3 Algoritmul Boyer-Moore
4 Algoritmul Knuth-Morris-Pratt
5 Algoritmul Z
6 Algoritmul Boyer-Moore revizuit
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 41 / 52
-
Algoritmul Boyer-Moore revizuit
Motivatie
Regula caracterului rau nu este eficienta daca alfabetul este mic.
In astfel de cazuri se poate castiga n eficienta daca se considera sufixelepotrivite deja.
Asta este realizata de regula sufixului bun.
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 42 / 52
-
Algoritmul Boyer-Moore revizuit
Regula sufixului bun: ilustrare caz 1
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
a c c a c b b c a b b a c b a b a b b a b b c b a b
a a b a b b c b a b 0 1 2 3 4 5 6 7 8 9
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
a c c a c b b c a b b a c b a b a b b a b b c b a b
a a b a b b c b a b 0 1 2 3 4 5 6 7 8 9
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 43 / 52
-
Algoritmul Boyer-Moore revizuit
Regula sufixului bun: cazul 1 formal
Cazul 1:daca p[j 1] nu se potriveste si p include o copie a lui p[j ..m 1]precedata de un caracter 6= p[j 1], se face salt la cea mai apropiata copiedin stanga cu aceasta proprietate.
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 44 / 52
-
Algoritmul Boyer-Moore revizuit
Regula sufixului bun: ilustrare caz 2
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
a b c a c b b c a b b a c b a b a b b a b b c b a b
a b b a b c b c a b 0 1 2 3 4 5 6 7 8 9
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
a b c a c b b c a b b a c b a b a b b a b b c b a b
a b b a b c b c a b 0 1 2 3 4 5 6 7 8 9
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 45 / 52
-
Algoritmul Boyer-Moore revizuit
Regula sufixului bun: cazul 2 formal
Cazul 2: daca nu se aplica regula din cazul 1, se face saltul cel mai mic astfelncat un sufix al lui s[0..i ] se potriveste cu un prefix al lui p
daca cel mai lung prefix al lui s[0..i ] care se potriveste peste un prefix allui p este sirul vid, atunci se face un salt cu m pozitii
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 46 / 52
-
Algoritmul Boyer-Moore revizuit
goodSuff (j) - definitie (cazul 1)
goodSuff (j) = pozitia de sfarsit a aparitiei lui p[j ..m 1] cea maiapropiataa de j si care nu este precedata de p[j 1].Daca nu exista o astfel de copie, goodSuff (j) = 0.
Avem 0 goodSuff (j) < m 1; daca goodSuff (j) > 0 atunci el reprezinta o copie a unui sufix buncare permite un salt de m goodSuff (j) pozitii deoarece p[m..m 1] este sirul vid, goodSuff (m) = cea mai din dreaptapozitie k cu p[k] 6= p[m 1] (1 daca toate caracterele sunt egale).
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 47 / 52
-
Algoritmul Boyer-Moore revizuit
goodSuff (j) - calcul
lcs(j , p) = lungimea celui mai lung sufix comun lui p[0..j ] si p.
Lema
Valorile lcs(j , p) pot fi calculate n timpul O(m).
Exercitiu Sa se demonstreze lema. (se utilizeaza algoritmul Z adaptat).
Teorema
Daca goodSuff (j) > 0, atunci goodSuff (j) este cel mai mare k < m 1cu lcs(k, p) = m j (= |p[j ..m 1]|).
Rezulta ca valorile goodSuff (j) pot fi calculate n timpul O(m).
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 48 / 52
-
Algoritmul Boyer-Moore revizuit
Preprocesarea n cazul 2
lp(j) = lungimea celui mai lung prefix al lui p care este sufix al luip[j ..m 1].
Lema
lp(j) = max{k | 0 k |p[j ..m 1]| lcs(k , p) = k}.
Exercitiu Sa se demonstreze lema.
Rezulta ca valorile lp(j) pot fi calculate n timpul O(m).
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 49 / 52
-
Algoritmul Boyer-Moore revizuit
Regula sufixului bun
Presupunem ca p[j 1] nu se potriveste (dupa ce s-au potrivit p[j ..m 1].1 daca goodSuff (j) > 0, face un salt egal cu m goodSuff (j) (cazul 1)2 daca goodSuff (j) = 0, face un salt egal cu m lp(j) (cazul 2)
Daca p[m 1] nu se potriveste, atunci j = m si saltul este corect.
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 50 / 52
-
Algoritmul Boyer-Moore revizuit
Algoritmul Boyer-Moore (versiunea 2)
BM(s, n, p, m, goodSuff, lp) {
k = m-1;
while (k < n) {
i = k; j = m-1;
while (j > 0 && p[j] == s[i]) {
i = i-1;
j = j-1;
}
if (j < 0) return i+1;
// nepotrivire pe pozitia p[j]
mareste k cu maximul dintre salturile date de
regula caracterului rau si regula sufixului bun
}
}
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 51 / 52
-
Algoritmul Boyer-Moore revizuit
Analiza
Teorema
Algoritmul BM executa totdeauna cel mult m + n comparatii de caractere si
aproximativn
msalturi cand alfabetul nu este mic si pattern-ul nu este
prea lung.
Observatie: Daca alfabetul are numai doua caractere (cazul sirurilorbinare), atunci performantele algoritmului BM nu sunt cu mult mai bunedecat cele ale cautarii naive. In acest caz se recomanda mpartirea sirurilorn grupe cu un numar fixat de biti. Fiecare grupa reprezinta un caracter.Daca dimensiunea unei grupe este k atunci vor exista 2k caractere, i.e.dintr-un alfabet mic obtinem unul cu multe caractere. Totusi, k va trebuiales suficient de mic pentru ca dimensiunea tabelei de salturi sa nu fie preamare. sfobs
D. Lucanu (FII - UAIC) Cautare peste siruri PA 2013/2014 52 / 52
IntroducereAlgoritmul Rabin-KarpAlgoritmul Boyer-MooreAlgoritmul Knuth-Morris-PrattAlgoritmul ZAlgoritmul Boyer-Moore revizuit