1 PRETRAŽIVANJE
U ovom radu ćemo razmotriti problem pronalaženja određene
informacije u velikom skupu podataka. Kao što ćemo videti, izvesne metode
organizacije podataka (t.j. strukture podataka) čine proces pronalaženja
efikasnijim. S obzirom da je proces pretraživanja vrlo čest u obradi podataka,
poznavanje metoda i tehnika organizacije podataka pretraživanja je vrio
važno.
Pre nego što predemo na konkretne metode uvedimo neke osnovne
termine.
Tabela
ili
datoteka
je grupa elemenata od kojih se svaki naziva
zapis
ili
čvor.
Ove termine upotrebljavaćemo u najopštijem smislu i ne bi
trebalo da se pomešaju sa sličnim terminima u PASCAL-u ili COBOL-u.
Svakom zapisu je pridružen
ključ
kojim se on može razlikovati od
ostalih zapisa.Odnos između ključa i zapisa može biti različit. U najprostijem
slučaju ključ je unutar zapisa kao jedan njegov deo (polje). Takvi ključevi se
nazivaju
internim.
U ostalim slučajevima, može postojati posebna tabela
ključeva sa pokazivačima (logičkim ili fizičkim) na zapise. Takvi ključevi se
nazivaju
eksternim.
Za svaku datoteku postoji najmanje jedan skup ključeva
(moguće je više) koji su jedinstveni, tj. ne postoje dva zapisa sa istim ključem.
Takvi ključevi se nazivaju
primanim.
Na primer, ako je datoteka realizovana
kao niz, indeks nekog elementa u nizu je ključ tog elementa. Pošto bilo koje
polje ili kombinacija polja nekog zapisa može biti ključ u nekoj određenoj
primeni, ključevi ne moraju uvek biti jedinstveni. Na primer, ako se u datoteci
2
int Poz = -1;
for (int i = 0; i < aArray.length;
{
if ((aArray[i].Key ==
aTargetKey) {
Poz = i;
break;
}
}
return Poz;
}
Realizacija datoteke kao spregnute liste ima prednost u tome što se
veličina memorijskog prostora potrebnog za smeštanje datoteke može menjati
prema potrebi. Definišimo prvo čvor liste na sledeći način:
class CvorListe
{
int Kljuc;
CvorListe Sledeci;
public CvorListe(int aKljuc, CvorListe aSled)
{
Kljuc = aKljuc;
Sledeci = aSled;
}
}
Pretpostavimo da promenljiva Glava pokazuje na prvi zapis datoteke, a
polje Kljuc sadrži vrednost ključa zapisa koji tražimo. Algoritam koji
sekvencijalno pretražuje datoteku i ako je pretraživanje neuspešno vrši
ubacivanje, izgleda ovako:
CvorListe Prethodni = null;
CvorListe Tekuci = Glava;
while (Tekuci != null)
{
if (Tekuci.Kljuc == TargetKey)
return tekuci;
Prethodni = Tekuci;
Tekuci = Tekuci.Sledeci;
}
// nije nađen
CvorListe novi = new CvorListe(kljuc, null); if
(Prethodni == null) // lista je bila prazna
Glava = novi;
else
Prethodni.Sledeci = novi;
return novi;
4
2.1 Efikasnost sekvencijalnog pretraživanja
Ako pretpostavimo da nema ubacivanja i izbacivanja i da vršimo
sekvencijalno pretraživanje datoteke veličine n zapisa, tada broj poređenja
koje moramo da obavimo prilikom pretraživanja zavisi od toga gde se nalazi
zapis sa ključem jednakim argumentu. Ako je zapis na početku, samo jedno
poređenje je potrebno; ako je zapis poslednji, tada je potreban n poređenja. U
proseku, za uspešno pretraživanje je potrebno (n+1)/2 poređenja, a za
neuspešno n poređenja (u oba slučaja O(n)).
Međutim, čest slučaj je da se nekim zapisima češće pristupa nego nekim
drugim. Ako se takvi zapisi stave na početak datoteke, tada prosečan broj
poređenja može značajno smanjiti. Pretpostavimo da
P(i)
označava
verovatnoću da se zapis na
i
-toj poziciji traži i da važi:
P(1) * P(2) * P(3)
+, +
P(n)
= 1.
Tada je prosečan broj poređenja jednak :
P(1) + 2P(2) * 3P(3)
+... +
nP(n).
( Zašto ?)
Znači, za datu veliku datoteku, sortiranjem zapisa datoteke u opadajućem
redosledu verovatnoća traženja postiže se efikasnije pretraživanje.
Na žalost, verovatnoće
P(i)
su vrlo retko poznate unapred. a često se ta
verovatnoća menja u vremenu. Zato bi bilo poželjno imati algoritam koji će
stalno da vrši preuređivanje datoteke tako da zapisi kojima se češće pristupa
budu bliži početku. Postoji više metoda kako se ovo može postići. Jedna od
njih, poznata kao
prebaci na početak,
efikasna samo za spregnute liste, uvek
kada je pretraživanje uspešno nađeni zapis pomeri sa njegove pozicije na
početak liste. Drugi metod
je metod transpozicije
u kome se pretraženi zapis
zameni sa svojim prethodnikom.Tako će zapisi kojima se
češće
pristupa
postepeno doći na početak liste.
5
Međutim, sporost izvršavanja rekurzivne procedure čini je nepogodnom za
primene gde je efikasnost primarna. U takvim slučajevima se koristi
nerekurzivna procedura:
public static int BinarySearch(Element[] aArray, int aTarget)
{
int Result = -1;
int left = 0;
int right = aArray.length - 1;
while (right >= left) {
int middle = (left + right) /
2; if (aArray[middle].Key >
aTarget)
right = middle - 1; else if
(aArray[middle].Key < aTarget)
left = middle + 1;
else
{
Result = middle;
break;
}
}
return Result;
}
Svaki korak u binarnom pretraživanju smanjuje broj kandidata na
pola. Znači, maksimalni broj poređenja ključeva je približno log2N gde je N
broj zapisa. Za malo N performanse algoritma nisu mnogo bolje od
sekvencijalnog pretraživanja, ali za veliko N binarno pretraživanje je
superiorno. Za N = 10
6
broj poređenja je približno 20 u odnosu na 500.000 kod
sekvencijalnog pretraživanja.
Na žalost, binarno pretraživanje se može primenjivati samo na
sortirane nizove (tj. kada su zapisi fizički susedni). To ima za posledicu da je
ubacivanje novih zapisa otežano, jer se mora vršiti pomeranje zapisa. Sve to
ograničava praktičnu primenu binarnog pretraživanja.
3 Interpolaciono pretraživanje
7
