A
LGORYTMY
I
S
TRUKTURY
D
ANYCH
dr Edyta Łukasik
A
LGORYTMY
I
S
TRUKTURY
D
ANYCH
dr Edyta Łukasik
P
ROBLEM
Dany jest wzorzec oraz tekst.
Należy wyszukać wszystkie wystąpienia wzorca w
podanym tekście.
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16 17
A L I
B
A B A
A R
A B A B A
A L I
2
Wzorzec: ABA
Wystąpienia:
5, 10, 12
Tekst
A
LGORYTM
NAIWNY
procedure Naiwny ( napis, wzor : String);
var
dw, dt, i, j : integer;
begin
dw := length (wzor);
dt := length (napis);
for i:=1 to dt-dw+1 do
begin
j:=0;
while (wzor[j+1]=napis[i+j]) and (j<dw) do j:=j+1;
if (j=dw) then writeln(’Wzorzec jest od pozycji’,i);
end;
end;
3
A
LGORYTM
NAIWNY
-
WNIOSKI
Złożoność tego algorytmu:
wykonuje się dt*(dt-dw+1) porównań;
dw – dł. wzorca, dt – dł. tekstu;
zwykle dw<<dt więc koszt jest dt*dw.
Tak wysoka jego złożoność eliminuje go w
praktyce z przeszukiwania zbiorów binarnych.
Jedyną jego zaletą jest prostota, ale długi czas
działania bierze górę.
4
A
LGORYTM
KMP
Idea tego algorytmu polega na zbadaniu wzorca,
w celu obliczenia ilości pozycji, o które należy
przesunąć wskaźnik, gdy stwierdzona zostanie
niezgodność wzorca i tekstu. Nie zawsze należy
badać wzorzec od początku. Może się zdarzyć, że
prefiks jest ten sam i tę informację trzeba umieć
wykorzystać.
Równolegle algorytm ten odkryli D. E. Knuth i
V. R. Pratt oraz J. H. Morris.
5
A
LGORYTM
KMP –
TABLICA
PRZESUNIĘĆ
(1)
6
void tworzShiftKMP ( int dw, string wzor, int s[ ])
{ //w stringu elementy są od indeksu 0
int i, k;
s[0]=0; s[1]=0;
k=0;
for(i=2;i<=dw;i++)
{
while (k>0 && wzor[k]!=wzor[i-1]) k = s[k];
if (wzor[k] == wzor[i-1]) k++;
s[i] = k;
}
}
Wynikowa
tablica
A
LGORYTM
KMP –
IMPLEMENTACJA
(2)
7
void KMP (int dw, int dn, string wzor, string napis)
{
int i, q;
int P[dn+1];
q=0; i=1;
tworzShiftKMP(dw, wzor, P);
while (i<=dn-dw+1)
{
while (q<dw && wzor[q]==napis[q+i-1]) q++;
if (q>=dw) cout<<"Wzorzec jest od pozycji "<<i<<endl;
if (q-P[q]>1) i+=q-P[q]; else i++;
q=P[q];
}
}
Długość wzorca
Długość napisu
A
LGORYTM
KMP –
PRZYKŁAD
1
1.
Wzorzec: A B C D A B C
Tablica przesunięć dla wzorca:
[
0
,
0
,
0
,
0
,
0
,
1
,
2
,
3]
.
2.
Wzorzec: A B A B A B
Tablica przesunięć dla wzorca:
[
0
,
0
,
0
,
1
,
2
,
3
,
4]
.
3.
Wzorzec: A B C E A B C D A B C E
Tablica: przesunięć dla wzorca:
[
0
,
0
,
0
,
0
,
0
,
1
,
2
,
3
,
0
,
1
,
2
,
3
,
4]
.
8
A
LGORYTM
KMP –
PRZYKŁAD
2
9
Wzorzec: ALARALA Tablica P = [0,0,0,1,0,1,2,3]
Tekst: MALARFALARALACA
i=1
M
ALARFALARALACA
q=0
A
LARALA
i:=i+1=2
i=2 M
ALAR
FALARALACA
q=P[0]=0
ALAR
ALA
q=1,...,4
i:=i+q-P[q]=2+4-0=6
A
LGORYTM
KMP –
PRZYKŁAD
2
C
.
D
.
10
i=6 MALAR
F
ALARALACA
q=P[4]=0
A
LARALA
i:=i+1=7
i=7 MALARF
ALARALA
CA
q=P[0]=0
ALARALA
q=1,...,7
i:=i+q-P[q]=7+7-1=13
i=13: 13 > (15-7+1) więc już nie sprawdzamy!
A
LGORYTM
KMP –
WNIOSKI
Algorytm ten działa w czasie proporcjonalnym do
dn+dw. Jest on rzędu O(dn+dw).
Największy zysk jest widoczny przy użyciu go dla
tekstów o wysokim stopniu samopowtarzalności.
Użycie jego jest wskazane w przeglądaniu
liniowym tekstu bez buforowania, gdyż nie cofamy
się po przeglądanym tekście.
Algorytm ten można znacznie zoptymalizować,
jeżeli często zdarza się szukanie tego samego
wzorca. Wtedy należy „wbudować” tablicę
przesunięć znanego wzorca.
11
A
LGORYTM
B
OYERA
-M
OORE
’
A
W algorytmie tym porównywany jest ostatni znak
wzorca.
Jeżeli rozpatrywany znak nie występuje we
wzorcu, wówczas można przesunąć się o całą
długość wzorce do przodu.
Jeżeli występuje, wówczas przesuwamy się tak ze
wzorcem, aby te same znaki nałożyły się na siebie
i porównywanie jest kontynuowane.
Jest to algorytm badania niezgodności.
12
13
void BM(int dw, int dn, string wzor, string napis)
{ int tabs[k+1], i, j, x,f;
tworzShiftBM(dw,wzor,tabs);
i=0;
while (i<=dn-dw+1)
{
j=dw;
while (napis[i+j]==wzor[j] && j>0) j--;
if (j<=0)
{cout<<"Wzorzec od pozycji "<<i<<endl; i++;}
else
{ x = tabs[index(napis[i+j])];
if (dw+1-j>x) i += dw+1-j;
else i += x;
}
}
}
A
LGORYTM
B
OYERA
-M
OORE
’
A
A
LGORYTM
BM –
TABLICA
PRZESUNIĘĆ
14
Informuje ona o ile liter należy się przesunąć, licząc od końca
wzorca, aby trafić na właściwy znak.
void tworzShiftBM (int dw, string w, int ts[])
{
int i;
for(i=0;i<=k;i++) ts[i]=dw+1;
for(i=0;i<=dw;i++) ts[index(w[i])]=dw-i;
}
Funkcja indeks zwraca dla spacji 0 w pozostałych
przypadkach numer litery w alfabecie.
A
LGORYTM
BM -
PRZYKŁAD
1
2
3
4
5
6
7
8
9
10
11 12
A
L
A
K
C
A
B
R
A
M
P
L
A
B
R
A
Znak A B C D E F G H I
J
K L Ł M N O P R
Index 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
Tabs
0
2
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
1
A
B
R
A
15
M=4
,
x=4
i:=i+1
A
B
R
A
A
LGORYTM
BM -
WNIOSKI
Algorytm ten jest najbardziej praktyczny, gdy
alfabet jest dostatecznie duży i wzorzec względnie
długi.
Koszt działania tego algorytmu wynosi O(dn),
gdzie dn jest długością przeglądanego tekstu.
Porównywanie symboli od strony prawej do lewej
jest bardzo efektywnym sposobem. W najlepszym
przypadku algorytm przegląda jedynie dn/dt część
całego tekstu.
16
A
LGORYTM
K
ARPA
-R
ABINA
Wzorzec do wyszukania jest traktowany jako
klucz o długości M znaków, któremu przypisana
jest pewna wartość funkcji H(w). Obliczana jest
ona dla wzorca tylko raz.
Tekst jest analizowany po M kolejnych znaków.
Obliczana jest dla nich wartość funkcji H(t).
Te dwie wartości H(w) i H(t) są ze sobą
porównywane. Jeżeli są one równe, wtedy
sprawdzamy znak po znaku fragment tekstu i
wzorzec.
17
A
LGORYTM
KR –
OBLICZANIE
KLUCZA
Każdy znak będziemy interpretować jako pewną
cyfrę dziesiętną. W przypadku ogólnym jako
cyfrę w systemie o podstawie d.
Wtedy H(w) możemy obliczyć z reguły Hornera
w czasie O(M).
Obliczenie H(t
s+1
) jest bardzo proste, jeżeli mamy
już obliczone H(t
s
): usuwamy z t
s
cyfrę
najbardziej znaczącą, przemnażamy wszystko
przez podstawę, aby przesunąć cyfry o jedną
pozycję w lewo i dodajemy cyfrę najmniej
znaczącą.
18
A
LGORYTM
K
ARPA
-R
ABINA
(1)
19
Najpierw należy obliczyć hasz dla wzorca i hasz
dla pierwszych tylu znaków tekstu, ile wynosi
długość wzorca:
b= 10;
p= 33554393; //p – duża liczba pierwsza
hashW=0;
hashR=0;
for(i=1;i<=dlwzorca;i++)
{
hashW=(hashW*b+index(wzor[i])) % p;
hashR=(hashR*b+index(napis[i])) % p;
}
A
LGORYTM
K
ARPA
-R
ABINA
(2)
20
bM1=1;
for(i=1;i<=dlwzorca-1;i++)
bM1 = (b*bM1) % p; //b do potęgi m-1
for(i=1;i<=dltekstu-dlwzorca+1;i++)
{
if (hashW==hashR)
{
j=0;
while (wzor[j+1]==napis[i+j] && j<dlwzorca) j++;
if (j==dlwzorca) cout<<"wzorzec od pozycji "<<i<<endl;
}
hashR=(hashR+b*p-index(napis[i])*bM1) % p;
hashR=(hashR*b+index(napis[i+m])) % p;
}
A
LGORYTM
KR –
WNIOSKI
Jako podstawę systemu (nasze b) należy wybrać
wielokrotność
liczby
2.
Można
wtedy
zaimplementować operację mnożenia przez b jako
przesunięcie bitowe (np. dla b=64 o <<6 ).
Dla dużego p (liczba pierwsza) zmniejszamy
prawdopodobieństwo
wystąpienia
kolizji
spowodowanej niejednoznacznością funkcji H.
Koszt algorytmu O(M+N).
21
A
LGORYTM
KR –
PRZYKŁAD
22
Alfabet składa się z liter: A, B, C, D. Za podstawę systemu
przyjmiemy
więc liczbę 4. Wartości liter wynoszą
odpowiednio: A-0, B-1, C-2, D-3. Za moduł przyjmiemy liczbę
pierwszą 23.
Szukany wzorzec to: BDA.
Tekst ma postać: CDBDACCAA.
Obliczamy hash wzorca:
H(W) = (1
4
2
+3
4
1
+0
4
0
) mod 23 = 28 mod 23 = 5
Obliczmy hash pierwszych trzech znaków tekstu:
H(T) = (2
4
2
+3
4
1
+1
4
0
) mod 23 = 45 mod 23 = 22
A
LGORYTM
KR –
PRZYKŁAD
23
Jeżeli H(W)
H(T) (5
22), wtedy wzorzec na tej pozycji
na pewno nie wystąpił.
Sprawdzamy kolejną sekwencję znaków o długości 3
przesuwając się względem poprzedniej sekwencji o jeden znak:
C
DB
DB
D
H(T) = ( H(T) - (4
2
mod 23)
2) mod 23 = (22-16
2) mod 23 =
= -10 mod 23 = 13 – usunięcie najwyższej cyfry (
C
)
H(T) = H(T)
4 mod 23 = 13
4 mod 23 = 52 mod 23 = 6
– przesunięcie o rząd wielkości
H(T) = ( H(T) + 3 ) mod 23 = (6+3) mod 23 = 9
– dodanie ostatniej cyfry (
D
)
A
LGORYTM
KR –
PRZYKŁAD
24
H(T) = 9
5 = H(W)
Więc to nie może być wzorzec, szukamy dalej!!!
Sprawdzamy kolejną sekwencję znaków o długości 3
przesuwając się względem poprzedniej sekwencji o jeden znak:
D
BD
BD
A
H(T) = ( H(T) - (4
2
mod 23)
3) mod 23 = (9-16
3) mod 23 =
= -39 mod 23 = 7 – usunięcie najwyższej cyfry (
D
)
H(T) = H(T)
4 mod 23 = 7
4 mod 23 = 5
– przesunięcie o rząd wielkości
H(T) = ( H(T) + 0 ) mod 23 = (5+0) mod 23 = 5
– dodanie ostatniej cyfry (
A
)
A
LGORYTM
KR –
PRZYKŁAD
25
H(T) = 5 = H(W)
Mamy więc sekwencję podejrzaną o identyczną z
wzorcem. Teraz algorytmem naiwnym znak po znaku należy
przejrzeć tę sekwencję i wzorzec co do zgodności znaków.
Wzorzec: BDA
Sekwencja (fragment tekstu od pozycji 3): BDA.
Pierwsze wystąpienie wzorca zostało więc znalezione
w tekście. Występuje on w szukanym tekście i zaczyna się od
pozycji 3.