Laboratorium :Algorytmy i struktury danych
Temat:	Wyszukiwanie łańcucha znaków w tekście.
Wykonał:	Daszkiewicz Mariusz	Data: 99-11-142	Ocena:

1.1:Algorytm Brute - Force.

Algorytm ten wykonuje m*n porównań, gdzie m to długość wzorca , a n to długość badanego tekstu. Polega to na tym, że porównujemy pierwszą literę wzorca z kolejnymi literami badanego tekstu. W przypadku zgodności przesuwamy się na następną literę wzorca i następną literę badanego tekstu i kontynuujemy tak długo jak występuje zgodność. W przypadku braku zgodność na którejś pozycji cofamy się o n-1 znaków sprawdzonych. Jest to algorytm bardzo powolny i przeszukuje najdłuzej ze wszystkich algorytmów.

1.2:Program wykonujący przeszukiwanie Brute - Force w języku wysokiego poziomu ma postać ma postać:

program Dahoo1;uses crt;

var tab:string; l,q,zn:integer;

kl:string; begin clrscr; write('Podaj jakiś ciąg znaków :'); readln(tab); write('Podaj klucz który chcesz znaleźć w tym ciągu:');

readln(kl);

l:=0;q:=1;

repeat

l:=l+1;

if tab[l]=kl[q] then begin

q:=q+1;

l:=l+1;

zn:=1;

while (zn<>0)and(n<=length(kl))do

begin

if tab[l]<>kl[q] then

zn:=0

else

begin

q:=q+1;

l:=l+1;

end;

end;

if zn=1 then writeln('Podany klucz jest na pozycji:',l - length(kl)) else begin l:=l-q+1;

n:=1

end;

end;

until (zn=1) or (l>length(tab));

if zn=0 then writeln('Podanego klucza nie znaleziono');

readln;

end.

1.3:Schemat blokowy do powyższego algorytmu ma postać:

2.1:Algorytm K-M-P.

Algorytm K-M-P jest dość przypomina algorytm brute - force . Jest jednak różnica: tutaj w przypadku niezgodności na którejś pozycji w kluczu nie cofamy się o n-1 znaków tylko analizujemy klucz aby sprawdzić o ile znaków można ewentualnie przesunąć się w tablicy.

2.2:Program wykonujący przeszukiwanie wg algorytmu K-M-P w języku wysokiego poziomu ma następującą postać:

program Dahoo2;

var

tab,kl:string;

L,KG,QW,RAK,ZN:integer;

procedure ToWzor;

var temp:string;

begin

temp:=kl;

for RAK:=1 to KG do

for QW:=1 to KG-RAK do

if temp[RAK+QW-1]<>kl[RAK] then break;

if (RAK+QW-1=KG) and (temp[RAK+QW-1]=kl[RAK]) then KG:=KG+RAK

else KG:=KG+L;

end;

procedure porownanie;

begin

for KG:=1 to length(kl) do

begin

if tab[L+KG]<>kl[KG] then porownanieWzorca;

if KG=length(kl) then ZN:=1;

end;

end;

begin

write('Podaj jakiś ciąg znaków: ');

readln(tab);

write('Podaj klucz, który chcesz znaleźć w tym ciągu :');

readln(kl);

for L:=1 to length(tab) do

if (tab[L]=kl[1])and(ZN=0) then porownanie;

if ZN=1 then writeln('Znaleziono klucz pozycja:',i)

else writeln('Klucza nie znaleziono');

readln;

end.

2.3:Schemat blokowy powyższego algorytmu ma postać:

3.1:Algorytm Boyera i Moore'a.

Algorytm ten działa na zupełnie innej zasadzie niż algorytmy poprzednie. Tutaj nie są porównywane pierwsze litery klucza i tablicy ale ostatnia litera klucza z elementami tablicy. I jeśli dana litera z tablicy nie występuje w kluczu to od razu można przeskakuje się dalej o całą długość klucza.

3.2:Program realizujący powyższy algorytm napisany w języku wysokiego poziomu ma następującą postać:

Program Dahoo3; uses crt; var Tab,Kl,Lit:string;

Jump,KL,QW,ZN:integer;

procedure znajdz;

begin

for KL:=1 to length(Kl) do

if Kl[i]=Lit then

begin

Jump:=Jump+length(Kl)-KL;

for QW:=1 to length(Kl) do

begin

if Kl[QW]<>Tab[Jump-length(Kl)+QW] then

begin

ZN:=0;

exit

end

else ZN:=1;

end;

if ZN=1 then break;

end;

end;

begin

clrscr;

write('Podaj jakiś ciąg znaków : ');

readln(Tab);

write('Podaj klucz, który chcesz znaleźć w tym ciągu:');

readln(Kl);

Jump:=length(Kl);

while (Jump<=length(Tab))and(ZN=0) do

begin

Lit:=Tab[Jump];

znajdz;

if ZN=0 then Jump:=Jump+length(Kl)

else

writeln('Znaleziono klucz pozycja:',Jump-length(Kl)+1);

end;

if ZN=0 then writeln('Klucza nie znaleziono');

readln;

end.

3.3:Schemat blokowy do powyższego algorytmu ma postać:

4.1:Algorytm Rabina i Karpa.

Algorytm Rabina i Karpa oparty jest na transformacji kluczowej. Jego zasada działania opiera się dla danego klucza na obliczeniu wartości danej funkcji i następnie w tablicy przesuwając się oblicza się funkcję dla tej samej długości słowa co klucz. W przypadku znalezienia sekwencji o tej samej wartości funkcji co klucz sprawdza się czy odpowiada ona kluczowi i jeśli nie to kontynuuje się przeszukiwanie.

4.2: Program realizujący ten algorytm w języku wysokiego poziomu ma postać:

program Dahoo4;uses crt;var Tab,Kl:string; L,Lange,Marker:integer;function moduloKlucz(Kl:string):integer; var z,x,w:integer; begin x:=0; for z:=1 to Lange do x:=((x+ord(Kl[z])) mod 17);

moduloKlucz:=x;

end;

function modulotabl(Tab:string;L:integer):integer;

var z,x:integer;

begin

x:=0;

for z:=1 to Lange do

x:=(x+ord(Tab[L+z-1])) mod 17;

modulotabl:=x;

end;

procedure sprawdzenie;

var z:integer;

begin

for z:=1 to Lange do

if Kl[z]<>Tab[z+L-1] then

begin

Marker:=0;

break;

end

else

Marker:=1;

end;

begin

clrscr;

write('Podaj elementy tablicy:');

readln(Tab);

write('Podaj klucz:');

readln(Kl);

Lange:=length(Kl);

writeln('modulo klucz:', moduloKlucz(Kl));

for L:=1 to length(Tab) do

begin

if moduloKlucz(Kl)=modulotabl(Tab,L) then

begin

sprawdzenie;

if Marker=1 then break;

end;

end;

if Marker=0 then writeln('Klucza nie znaleziono');

if Marker=1 then writeln('Znaleziono klucz pozycja:',L);

readln;

end.

4.3: Schemat blokowy tego algorytmu ma postać:

5: Wnioski:

Powyższe ćwiczenie miało na celu zaprezentowanie czterech metod przeszukiwania teksu, są to: Brute - Force, K-M-P, Boyera i Moore'a oraz Algorytm Rabina i Karpa. Zastosowane są w nich różne techniki przeszukiwań. Brute - force jest stosunkowo najprostszym algorytmem przeszukuje on po kolei całą tablicę znak po znaku a jeśli wystąpi zbieżność z kluczem to przeskakuje on w kluczu na następną pozycję i sprawdza zgodność następnego znaku itd. W przypadku niezgodności na którejś pozycji musi się on cofnąć w tablicy o długość klucza-1 co znacznie spowalnia przeszukiwanie. K-M-P jest szybszym algorytmem niż brute - force. Wykorzystana tu jest przeszukaną już część klucza do stwierdzenia czy może przesunąć klucz o jakąś ilość liter w przód i nie cofać się w tablicy o długość prawie całego klucza. Algorytm Boyera i Moore'a chyba najszybszym algorytmem bo w przeciwieństwie do poprzednich nie sprawdza wszystkich znaków w tablicy, tylko za każdym razem skacze w tablicy o długość klucza i sprawdza czy dany element występuje w kluczu i jeśli nie to skacze znów w tablicy o długość klucza itd. Jeśli natomiast dany element występuje w tablicy to tak przesuwa klucz aby znaleziony znak pokrył się ze znakiem w kluczu i sprawdza czy klucz zgadza się z sekwencją w tablicy i jeśli nie to znów skacze o długość klucza. Algorytm Rabina - Karpa w przeciwieństwie do pozostałych nie sprawdza się tu zgodności z kolejnych znaków a jedynie oblicza się funkcję dla klucza i dla danej sekwencji znaków z tablicy. Algorytm ten ze względu na obliczanie funkcji za każdym razem jest algorytmem wolnym. Przeglądając tablicę po kolei oblicza się funkcję i sprawdza zgodność z kluczem. Jeśli wystąpi zgodność to sprawdza się czy klucz jest zgodny z sekwencją znaków i jeśli nie jest zgodny to przeszukiwanie jest kontynuowane.

---