1

Wyszukiwanie wzorca

Pattern Matching

Pattern recognition

Wyszukiwanie wzorca

Algorytmy do rozwiązywania problemu PM:

"Naiwny” (

Naive algorithm

)

Karpa-Rabina (KR)

Knutha-Morrisa-Pratta (KMP)

Karpa-Millera-Rosenberga (KMR)

Boyera-Moore'a (BM)

ASD

LJ

S

Problem wyszukiwania wzorca polega na znajdowaniu wszystkich wystąpień
wzorca P (

Pattern

) o długości m=| P |w ustalonym tekście T (

Text

) o długości

n=| T |.

2

Wyszukiwanie wzorca

Podstawowe pojęcia i oznaczenia.

Σ - alfabet skończony zbiór symboli

Tekst (słowo) - ciąg symboli alfabetu Σ

Długość tekstu - liczba jego symboli

T[1 .. n]- tekst, n-elementowa tablica T (Text)

X[i .. j] = X[i], X[i+1], ; ,X[j],

gdzie i ≤ j

P[l .. m] – wzorzec, m-elementowa tablica P (Pattern)

Reprezentacje tekstów: listowa, tablicowa

ASD

LJ

S

Wyszukiwanie wzorca

Wzorzec P występuje w tekście T na pozycji i (wzorzec pasuje do tekstu
począwszy od i-tej pozycji) gdy:

T[i .. i+ m-1] = P[l .. m]

T[i + j -1] = P[j]

dla 1≤ j ≤ m

b

b

a

b

a

c

a

b

b

a

b

a

Tekst T

Wzorzec P

i=3

Problem: znalezienie wszystkich wystąpień wzorca P=aba w tekście T=bbabacabb.
Rozwiązanie: wzorzec P występuje w tekście T dokładnie raz na 3-ciej pozycji.

ASD

LJ

S

3

Wyszukiwanie wzorca

Algorytm N „Naiwny” (algorytm typu

Brute-force

).

Dla każdej z n-m+1 możliwych wartości i algorytm znajduje wszystkie wystąpienia
wzorca poprzez sprawdzanie waruneku:

T[i .. i+m-1] = P[1 .. m]

P

p

1

p

2



p

k



p

m

i

1

n-m+1

t

1

t

2

t

i



t

n-m

t

n-m+1



t

n

T



Złożoność obliczeniowa algorytmu O((n-m+1)m).

ASD

LJ

S

Wyszukiwanie wzorca

Algorytm N „Naiwny”.

ALG_N (T,P,n,m)
{

// n = |T|– długość tekstu;
// m – |P|– długość wzorca
// i – pozycja wystąpienia wzorca
FOR i=1, 2, … ,n-m+1 {

IF (P[l..m]== T[i..i+m-1]) return (i);

}

}

a

c

a

a

b

c

a

a

b

i=1

a)

a

c

a

a

b

c

a

a

b

i=2

b)

a

c

a

a

b

c

a

a

b

i=3

c)

a

c

a

a

b

c

a

a

a

i=4

d)

Działanie algorytmu dla wzorca P=aab i tekstu acaabc

4

Wyszukiwanie wzorca

ALG_N (T,P,n,m)
{

FOR i=1,2,…,n-m+1 {

j=0;
WHILE (P[j+1]==T[i+j]) j=j+1;

IF(j==m) return(i);

} //przesunięcie;

}

a

a

b

a

c

a

a

a

b

b

c

a

a

b

a

a

b

a

a

b

a

a

b

a

a

b

Złożoność pesymistyczna: O(n

2

).

- Fałszywe starty podczas wyszukiwania.

ASD

LJ

S

Wyszukiwanie wzorca

Algorytm K-R (Karpa R., Rabina M.).

1.

Wzorzec P[1 .. m] o długości m znaków interpretowany jest jako liczba m

cyfrowa w systemie o zadanej podstawie r. Definiowana jest funkcja

haszująca h

P

=h(P[1 .. m]).

2.

Dla tekstu wejściowego T[i .. i+m-1] definiowana jest funkcja haszująca

h

T

=h(T[i .. i+m-1]).

3.

Sprawdzenie zgodności wzorca z aktualnie badanym fragmentem tekstu

dokonywane jest na podstawie warunku h

P

=h

T

.

ASD

LJ

S

5

Algorytm K-R

Dla tekstu

T[i..i+m-1]

określana jest wartość:

T

i

= T[i] r

m-1

+ T[i+1] r

m-2

+ ;+T[i+m-1]

Dla tekstu

T[i+1..i+m]

otrzymujemy:

T

i+1

= T[i+1] r

m-1

+ T[i+2] r

m-2

+ ; +T[i+m-1]

*

r +T[i+m]

T

i *

r = T[i] r

m-1

*

r + T[i+1] r

m-2

*

r + ;+T[i+m-1]

*

r + T[i+m] - T[i+m] = T[i] r

m-1

*

r + T

i+1

- T[i+m]

T

i+1

= (T

i

- T[i] r

m-1

) r +T[i+m]

Wobec tego:

Funkcja haszująca:

gdzie: q jest „dużą” liczbą pierwszą.

ASD

LJ

S

h(T

i

) = T

i

mod q

Wyszukiwanie wzorca

Wykorzystywana jest własność operacji modulo.

Operację modulo można stosować względem wyniku końcowego, albo po każdej

operacji cząstkowej i przenosząc otrzymaną wartość do następnego wyrażenia

cząstkowego np.:

(6 10

1

+ 5) mod 9 = 65 mod 9 = 2

6 10

1

mod 9 = 6

(6 + 5) mod 9 = 2

dla r=10:

ASD

LJ

S

6

Wyszukiwanie wzorca

ALG_R-K (T,P,n,m,r,q)
{

h

P

= h(P[1..m]);

// inicjalizacja funkcji dla wzorca P

h

T

= h(T[1..m]);

// inicjalizacja funkcji dla tekstu T

rm1=r

m-1

;

FOR

i=1,2,… ,n-m+1{

IF (h

P

= h

T

){

IF(P[1..m]== T[i..i+m-1])

return(i);

}
h

T

=((h

T

-T[i]

*

rm1)*r+T[i+m])mod q;

}

}

Algorytm Karpa-Rabina .

Złożoność przeciętna: O(n+m).

ASD

LJ

S

Wyszukiwanie wzorca

Złożoność obliczeniowa algorytmu K-R.

Pesymistyczna złożoność algorytmu K-R wynosi O((n - m + 1)m): algorytm

sprawdza każde poprawne przesunięcie w sposób bezpośredni.

Przeciętna złożoność algorytmu wynosi O(n + m).

Liczba q jest liczbą pierwszą o „dużej wartości”. Prawdopodobieństwo, że

wystąpi kolizja (wartości h będą takie same dla dwóch różnych argumentów)

wynosi 1/q.

Podstawa systemu winna być potęgą liczby 2. Możliwe jest wówczas

zaimplementowanie operacji mnożenia przez podstawę jako przesunięcia

bitowego.

ASD

LJ

S