Pretrazivanje

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 studenata ime studenta uzme kao ključ, takav ključ verovatno neće biti jedinstven. Ovakvi ključevi se nazivaju sekundarni ključevi.
Proces pretraživanja je algoritam koji prihvata argument a i pronalazi jedan ili više zapisa u datoteci ili tabeli čija vrednost ključa je a. Može se desiti da proces pretraživanja bude neuspešan, t.j. da ne postoji zapis sa takvim ključem. U tom slučaju, često je poželjno u datoteku ubaciti zapis sa takvim ključem. Takvo pretraživanje se naziva pretraživanje sa ubacivanjem.
Primetite da do sada nismo ništa rekli o strukturi podataka u kojoj se datoteka implementira. To može biti niz, spregnuta lista, stablo ili čak mreža (graf). Pošto su različite metode pretraživanja pogodnije za neke strukture podataka, izbor implementacije datoteke (t.j. izbor strukture podataka) je često određen metodom pretraživanja koja se ima na umu.





2 Sekvencijalno pretraživanje

Najprostiji algoritam pretraživanja je sekvencijalno pretraživanje koji se primenjuje na nizove i spregnute liste. On se sastoji u tome da se ključ svakog zapisa ispituje u redosledu kako su zapisi smešteni sve dok se ne nađe traženi zapis. Neka se u nizu čuvaju zapisi deklarisani kao

class Element {
public int Key; public object Value;
}

i neka promenljiva Poz sadrži indeks zapisa koji tražimo ako on postoji ili -1 ako on ne postoji. Algoritam sekvencijalnog pretraživanja izgleda:

public static int SequentialSearch(Element[] aArray, int aTargetKey)
{
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;

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.

2.2 Pretraživanje sortirane datoteke

Ako je datoteka smeštena u rastućem ili opadajućem redosledu vrednosti ključeva, jedna očigledna prednost u odnosu na nesortiranu datoteku kod sekvencijalnog pretraživanja je da se može otkriti da nema zapisa sa traženim ključem pre nego što ispitamo sve zapise. Naime, čim prilikom pretraživanja naiđemo na zapis čiji ključ je veći ( u slučaju da su zapis sortirani u rastućem redosledu) od traženog tada možemo zaključiti da ne postoji zapis sa traženim ključem.
Međutim, postoje metode pretraživanja koje takođe pretražuje sortiranu datoteku, ali su mnogo efikasnije od sekvencijalnog pretraživanja.

2.3 Binarno pretraživanje

Najefikasniji metod za pretraživanje sortirane tabele bez upotrebe dodatnog prostora je binarno pretraživanje. Argument traženja se poredi ključem zapisa koji se nalazi u sredini tabele. Ako su jednaki onda se pretraživanje uspešno završava. Inače, bilo jedna ili druga polovina tabele se na isti način pretražuje, a koja, zavisi od rezultata poređenja i redosleda sortiranja tabele. Ako je argument manji od ključa zapisa na sredini tabele i ako je tabela sortirana u rastućem redosledu tada se pretražuje prva polovina tabele; inače druga. Dakle, algoritam je rekurzivan:

public static int BinRek(Element[] aArray,int aTarget,int aLeft, int aRight)
{
if (aLeft <= aRight)
{
int middle = (aLeft + aRight) / 2; if (aArray[middle].Key == aTarget) return middle;
if (aArray[middle].Key <= aTarget)
return BinRek(aArray, aTarget, middle, aRight);
else
return BinRek(aArray, aTarget, aLeft, middle);
}
return -1;
}

Međutim, sporost izvršavanja rekurzivne procedure čini je nepogodnom za primene gde je efikasnost primarna. U takvim slučajevima se koristi nerekurzivna procedura:


lektira, studentski, poslovna, megatrend, diplomski radovi , magistarski radovi, maturalni radovi, diplomski rad, eseji, maturski radovi, seminarski radovi, diplomski radovi, master radovi, magistarski radovi, domaci radovi, domaci zadaci, projekti, maturalni, maturalne radnje, seminarski, maturski, diplomski, ekonomija, ekonomski, pravo, prava, menadzment, marketing, instalacija, tutorijal, tutorijali, tutorial, baze, baza, sistemi, informatika, ekonomika preduzeca, analiza, racunovodstvo, bankarstvo, osiguranje, spoljnotrgovinsko poslovanje, poreski sistem, politika, inteligencija, psihologija, sociologija, geografija, etika, kultura, fizika, seminarski rad, maturski rad