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