Wyszukiwanie wzorca
Pattern Matching
Pattern recognition
Wyszukiwanie wzorca
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 |.
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
1
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 d" 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 1d" j d" m
Tekst T b b a b a c a b b
i=3
a b a
Wzorzec P
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
2
Wyszukiwanie wzorca
Algorytm N  Naiwny (algorytm typu Brute-force).
T t1 t2 ti tn-m tn-m+1 tn
i
1 n-m+1
P p1 p2 pk pm
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]
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) b)
a c a a b c a c a a b c
i=1
i=2
a a b a a b
c) d)
a c a a b c
a c a a b c
i=4
i=3
a a a
a a b
Działanie algorytmu dla wzorca P=aab i tekstu acaabc
3
Wyszukiwanie wzorca
ALG_N (T,P,n,m) a c a a a b b c
{
FOR i=1,2,& ,n-m+1 {
a a b
j=0;
WHILE (P[j+1]==T[i+j]) j=j+1;
a a b
IF(j==m) return(i);
} //przesunięcie;
a a b
}
a a b
a a b
Złożoność pesymistyczna: O(n2).
a a b
- 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 hP=h(P[1 .. m]).
2. Dla tekstu wejściowego T[i .. i+m-1] definiowana jest funkcja haszująca
hT=h(T[i .. i+m-1]).
3. Sprawdzenie zgodności wzorca z aktualnie badanym fragmentem tekstu
dokonywane jest na podstawie warunku hP=hT.
ASD LJ S
4
Algorytm K-R
Dla tekstu T[i..i+m-1] określana jest wartość:
Ti = T[i] rm-1 + T[i+1] rm-2 + +T[i+m-1]
Dla tekstu T[i+1..i+m] otrzymujemy:
Ti+1 = T[i+1] rm-1 + T[i+2] rm-2 + +T[i+m-1]*r +T[i+m]
Ti * r = T[i] rm-1 *r + T[i+1] rm-2*r + +T[i+m-1]*r + T[i+m] - T[i+m] = T[i] rm-1 *r + Ti+1 - T[i+m]
Wobec tego:
Ti+1 = (Ti - T[i] rm-1) r +T[i+m]
Funkcja haszująca:
h(Ti) = Ti mod q
gdzie: q jest  dużą liczbą pierwszą.
ASD LJ S
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.:
dla r=10:
(6 101 + 5) mod 9 = 65 mod 9 = 2
6 101 mod 9 = 6 (6 + 5) mod 9 = 2
ASD LJ S
5
Wyszukiwanie wzorca
Algorytm Karpa-Rabina .
ALG_R-K (T,P,n,m,r,q)
{
hP= h(P[1..m]); // inicjalizacja funkcji dla wzorca P
hT= h(T[1..m]); // inicjalizacja funkcji dla tekstu T
rm1=rm-1;
FOR i=1,2,& ,n-m+1{
IF (hP = hT){
IF(P[1..m]== T[i..i+m-1])
return(i);
}
hT=((hT-T[i]* rm1)*r+T[i+m])mod q;
}
}
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
6