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.