[7] string matching1

Proiectarea algoritmilor: Cautare peste siruri

Dorel Lucanu

Faculty of Computer ScienceAlexandru Ioan Cuza University, Iasi, Romania

[email protected]

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


Introducere

Plan

1 Introducere




5 Algoritmul Z



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).


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.


Algoritmul Rabin-Karp

Plan

1 Introducere




5 Algoritmul Z




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.



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.


TeaHighlight


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.




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;

}


TeaHighlight

TeaHighlight

TeaHighlight

TeaHighlight


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).



Algoritmul Rabin-Karp: o posibila implementare C#define REHASH(a, b, h) ((((h)-(a)*dM)


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.


Algoritmul Boyer-Moore

Plan

1 Introducere




5 Algoritmul Z




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


TeaHighlight

TeaHighlight

TeaHighlight


Exemplu

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18


6=I A R

19 20 21 22 23 24

I A R N A

2



Exemplu

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18


6=I A R

19 20 21 22 23 24

I A R N A

3



Exemplu

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18


6=I A R

19 20 21 22 23 24

I A R N A

4



Exemplu

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18


6=I A R

19 20 21 22 23 24

I A R N A

5



Exemplu

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18


6=I A R

19 20 21 22 23 24

I A R N A

6



Exemplu

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18


I

19 20 21 22 23 24

I A R N A

6=A R

7



Exemplu

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

I A R N A=

I A R

8


TeaHighlight

TeaHighlight


Exemplu

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

I A R N A=

I A R

9


TeaHighlight

TeaHighlight


Exemplu

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

I A R N A=

I A R

10


TeaHighlight

TeaHighlight


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.



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}))




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;




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.



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


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.


Algoritmul Knuth-Morris-Pratt

Plan

1 Introducere




5 Algoritmul Z




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.



KMP: ideea

. . . a b a b * . . .

6=a b a b c



KMP: ideea

. . . a b a b * . . .

??

a b a b c



KMP: ideea (cont)

subiect

pattern

i

j

. . .

. . .

subiect

pattern

i

j k 0

. . . . . .

. . . . . . . . .

subiect

pattern

j k 0

. . . . . .

. . . . . . . . .

i

u u



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



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).



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].



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;

}

}



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



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.



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 .



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 */

}



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.


Algoritmul Z

Plan

1 Introducere




5 Algoritmul Z



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 ].


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.


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;


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;


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;

}


Algoritmul Boyer-Moore revizuit

Plan

1 Introducere




5 Algoritmul Z




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.



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



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.



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



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



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).



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).



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).



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.



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

}

}



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


IntroducereAlgoritmul Rabin-KarpAlgoritmul Boyer-MooreAlgoritmul Knuth-Morris-PrattAlgoritmul ZAlgoritmul Boyer-Moore revizuit

[7] string matching1

Documents