Dr Aleksander Klosow

PWSZ Legnica, 2003

www.strony.wp.pl/wp/klosov/

Algorytmy i Struktury Danych

Wykład 9

ALGORYTMY PRZESZUKIWANIA

PLAN

Przeszukiwanie posortowanych ciągów liczbowych:

1. Metoda naiwna

2. Metoda binarna

Poszukiwanie wzorca w tekście:

3. Metoda brute-force

4. Metoda KMP

5. Metoda Boera-Moore'a

Przeszukiwanie ciągu liczb - METODA NAIWNA

- dla dowolnego ciągu liczb

i L N

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
2	5	7	12	15	17	21	23	25	26	36	42	43	44	45	45

int Znajdz(int t[N], int L) { int i; for(i=0;i<N;i++) if(t[i]==L) return i; return -1; }

Złożoność obliczeniowa: O(n)

Przeszukiwanie ciągu liczb - METODA BINARNA

- tylko dla ciągów posortowanych

L N

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
2	5	7	12	15	17	21	23	25	26	36	42	43	44	45	45

i=N/2 L>t[i]

int ZnajdzBin(int t[N], int L) { int i; int A = 0, B = N-1; while(A<=B) { i = (A+B)/2; if(t[i]==L) return i; else if(t[i]>L) B = i-1; else A = i+1; } return -1; }

Złożoność obliczeniowa: O(log2(N)) N = 100 Naiwny: 100 operacji Binarny: 7 operacji N = 10000 Naiwny: 10000 operacji Binarny: 13 operacji

SZUKANIE WZORCU W TEKŚCIE

METODA BRUTE-FORCE

i

a

n

a

n

a

s

y

z

n

a

s

z

e

j

k

l

a

s

y

j

n

a

s

z

e

j

n

a

s

z

e

j

n

a

s

z

e

j

n

a

s

z

e

j

...

...

...

...

...

n

a

s

z

e

j

n

a

s

z

e

j

Metoda próbuje dopasować wzorzec do fragmentu tekstu tej samej długości. Zaczynając od pierwszej pozycji w każdym kroku przemieszczamy się o jedną pozycje w prawo w tekście do momentu, aż cały fragment teksu będzie zgodny ze wzorcem, bądź osiągniemy koniec tekstu.

METODA BRUTE-FORCE

Implementacja

int BruteForce(char *t, char *w) { int i=0,j=0; int N=strlen(t), M=strlen(w); while(j<M && i<N) { if(t[i]!=w[j]) { i = i - j - 1; j = -1; } i++; j++; } if(j==M) return i-M; else return -1; }

Złożoność obliczeniowa: O(N·M)

METODA Knutha-Morrisa-Pratta (K-M-P)

Złożoność obliczeniowa O(M+N)

i

a

b

a

c

a

b

a

b

a

b

a

c

a

a

b

c

b

a

a

b

c

a

j+shift

a

b

a

b

a

c

a

b

a

b

a

c

1

a

b

a

b

a

c

0

a

b

a

b

a

c

0

a

b

a

b

a

c

3

shift

1	2	3	4	5	6
a	b	a	b	a	c
0	0	1	2	3	0

Metoda wykorzystuje zbadaną część wzorca do wyznaczenia optymalnego przesunięcia wzorca względem badanego fragmentu tekstu. Do tego celu na wstępie generowana jest tablica optymalnych przesunięć shift. Metoda kończy działanie jak w poprzednim algorytmie.METODA K-M-P

Implementacja

int M = strlen(w);

int shift[M];

int KMP(char *t, char *w) { int i,j,N=strlen(t); for(i=0,j=0; i<N&&j<M; i++,j++) while((j>=0) && (t[i]!=w[j])) j=shift[j]; if(j==m) return i-M.; else return -1; }

void InitShift(char *w) { int i,j; shift[0]=-1; for(i=0,j=-1; i<M-1;i++,j++,shift[i]=j) while((j>=0)&&(w[i]!=w[j])) j=shift[j]; }

[Wróblewski P., Algorytmy, struktury danych i techniki programowania...]

METODA Boyera-Moore'a (BM)

Złożoność obliczeniowa O(N/M)

i

a

v

e

,

C

a

e

s

a

r

,

m

o

r

i

t

u

r

i

t

e

s

o

l

u

t

a

n

t

s

o

l

u

t

s

o

l

u

t

s

o

l

u

t

s

o

l

u

t

s

o

l

u

t

s

o

l

u

t

s

o

l

u

t

1. W metodzie wzorzec jest badany od końca

2. W wypadku niezgodności wzorzec jest przesuwany tak, aby badana litera tekstu pasowała do pierwszej z prawej takiej samej litery we wzorcu, w przeciwnym przypadku wzorzec jest przesuwany o całą długość w prawo.

3. Metoda wykorzystuję tablicę optymalnych przesunięć wzorca podobnie do metody K-M-P

METODA Boyera-Moore'a (BM)

Implementacja

int BM(char *t, char *w) { int i,j,N=strlen(t),x; for(i=M-1,j=M-1; j>0; i--,j--) while( t[i]!=w[j] ) { x=shift[indeks(t[i])]; if(M-j>x) i+=M-j; else i+=x; if(i>=N) return -1; j=M-1; } return i; }

const K = 53; // litery(26+26) i spacja (1) int shift[K]; int indeks(char c) { switch(c) { case 32: return 0; // spacja default: if(islower(c)) return c-'a'+1; else return c-'A'+27; } } void InitShift(char *w) { int i; for(i=0; i<K; i++) shift[i]=M; for(i=0; i<M; i++) shift[indeks(w[i])]=M-i-1; }

WNIOSKI

Metoda	Klasa	Kiedy stosować	+/-
Brute-Force	O(NM)	Krótki tekst oraz wzorzec	Prosty w programowaniu / Powolny
K-M-P	O(N+M)	Powtarzający się wzorzec, krótki tekst, mały alfabet	Szybki / Ograniczony obszar zastosowań
BM	O(N/M)	Długi tekst, długi wzorzec, duży alfabet	Szybki / Kłopotliwa implementacja

---