Interpolaciona pretraga

U računarstvu, interpolaciona pretraga je unapređena verzija algoritma binarne pretrage za pretraživanje indeksiranog niza koji je uređen po vrednosti ključa. Bazira se na linearnoj interpolaciji vrednosti (ključa) koja se traži i vrednostima na krajevima prostora pretrage. U literaturi se može naći i termin ekstrapolaciona pretraga.

Uvod[uredi | uredi izvor]

U okviru binarne pretrage prostor pretrage se svaki put polovi, što garantuje logaritamsku vremensku složenost. Međutim, ako se u toku pretrage naiđe na vrednost vrlo blisku traženom broju z, izgleda razumno da se pretraga usredsredi na okolinu tog indeksa umesto da se nastavi sa polovljenjem naslepo. Specijalno, ako je vrednost z vrlo mala, može se započeti sa pretragom negde na početku niza umesto od srednjeg indeksa.^[1]

Ovaj način pretrage može da se uporedi sa načinom na koji ljudi koriste rečnik. Ako tražimo reč koja počinje na slovo B, rečnik ćemo odmah otvoriti negde blizu početka. Jasno je da u ovakvom slučaju prosta binarna pretraga daje lošije rezultate. U interpolaciono-sekvencijalnom pretraživanju, interpolacija se koristi da bi se locirao element koji je najbliži traženom, a zatim se koristi linearna pretraga za pronalaženje tačnog elementa. U svakom koraku pretrage izračunava se u kom prostoru pretrage bi ključna vrednost mogla da se nalazi. To se izvršava na osnovu vrednosti na krajevima datog prostora pretrage i vrednosti ključa koji se traži. Izdvojena vrednost ključa se zatim upoređuje sa traženom i ukoliko nisu jednake, preostali prostor pretrage se, u zavisnosti od poređenja, dodatno redukuje na deo pre ili posle pronađene vrednosti.

Složenost[uredi | uredi izvor]

Interpolaciona pretraga je vrlo efikasna za ulaze sa približno uniformno raspodeljenim elementima.^[1] U proseku, složenost interpolacionog algoritma pretrage (ukoliko su elementi uniformno raspoređeni) je O (log (log (n))), gde je n broj elemenata niza koji se pretražuje. U najgorem slučaju (na primer, ukoliko numerička vrednost ključa raste eksponencijalno) broj poređenja može dostići i red veličine O (n).^[2]

Pseudokod[uredi | uredi izvor]

Umesto da polovimo prostor pretrage, mi ga delimo tako da bude najveća verovatnoća uspeha.^[1]

 Улаз: X (низ од n неопдајуће уређених бројева) i z (број који се тражи).
 Излаз: Poz (индекс i такав да је X[i] = z, ili 0 ако такав индекс не постоји).

 begin
    if z < X[1] or z > X[n] 
       then Poz := 0 {неуспешна претрага}
    else 
       Poz := iNadji(z, 1, n);
 end
 function iNadji(z; Levi;Desni) : integer
 begin
      if X[Levi] = z 
         then i_Nadji := Levi;
      else if Levi = Desni or X[Levi] = X[Desni] 
         then iNadji := 0;
      else 
         Srednji :=  $\lfloor$ Levi + (z - X[Levi])*(Desni - Levi) / (X[Desni] - X[Levi]) $\rfloor$ ;
         if z < X[Srednji] 
            then iNadji := iNadji(z, Levi, Srednji - 1);
         else 
            iNadji := iNadji(z, Srednji, Desni);
 end

Primer[uredi | uredi izvor]

Kratak primer koji ilustruje operacije interpolacione pretrage.

Traži se vrednost v = 7 u sledećem nizu:

2	4	7	9	12	21	26	31	37

Na početku, leva (L) i desna (D) granica intervala pretrage su postavljene na početni i krajnji element niza. U ovom trenutku, naredni element podele intervala se računa na osnovu sledeće formule: $x=l+{\frac {v-A[l]}{A[d]-A[l]}}\cdot (d-l)$

Specijalno za dati niz (crveno = prostor pretrage, plavo = x, boldovano = traženi element):

$x=1+{\frac {7-2}{37-2}}\cdot (9-1)\approx 2,15\to 2$

2	4	7	9	12	21	26	31	37

Zatim se vrednost elementa x upoređuje sa traženom vrednošću. Ako su jednake tu je kraj, jer je pronađena vrednost. U suprotnom se podešavaju granice prostora pretrage. Ako je x manje, to znači da moramo da gledamo desno, odnosno podešavamo vrednost leve granice na x+1, u suprotnom desna granica dobija vrednost x-1.

Pošto je u našem slučaju vrednost A[2] = 4 manja od tražene, postavljamo levu granicu na L = x+1 = 3. Desna granica ne menja svoju vrednost i formula za sledeći element podele novog intervala ima sledeći oblik:

$x=3+{\frac {7-7}{37-7}}\cdot (9-3)=3\to 3$

Sada, naš niz izgleda ovako:

2	4	7	9	12	21	26	31	37

Pošto je A[x] = A[3] = 7 = v, sledi da je tražena vrednost pronađena i prekida se izvršavanje algoritma.

Implementacija[uredi | uredi izvor]

Implementacija jednostavne verzije interpolacionog algoritma pretrage.

C[uredi | uredi izvor]

/* Funkcija trazi u sortiranom nizu a[] duzine n broj x. 
 * Vraca indeks pozicije проnadjenog elementa 
 * ili -1 ako element nije pronadjen */

int interpolaciona_pretraga(int a[], int n, int x)
{
    int l = 0;
    int d = n - 1;
    int s;

    /* sve dok je indeks l levo od indeksa d  */
    while (l <= d) {

	/* Ako je element manji od pocetnog ili veci od poslednjeg clana
           u delu niza a[l],...,a[d], tada nije u tom delu niza.
	 Provera je neophodna, da se ne bi izaslo izvan opsega indeksa [l,d] */
	if (x < a[l] || x > a[d])
	 return -1;

	/* U suprotnom, x je izmedju a[l] i a[d], 
           ako a[l]==a[d] tada je x jednako ovim vrednostima, pa vracamo indeks l (ili d).
           Provera je neophodna, zbog potencijalnog deljenja nulom pri izracunavanju s. */
	else if (a[l] == a[d])
	 return l;

	/* Racunamo sredisnji indeks */
	s = l + ((double) (x - a[l]) / (a[d] - a[l])) * (d - l);

	/* Ako je sredisnji element veci od x, 
           tada se x mora nalaziti u levoj polovini niza */
	if (x < a[s])
	 d = s - 1;

	/* Ako je sredisnji element manji od x,
	 tada se x mora nalaziti u desnoj polovini niza */
	else if (x > a[s])
	 l = s + 1;

	else
	 /* Ako je sredisnji element jednak x, 
	 tada smo pronasli x na poziciji s */
	 return s;
    }

    /* ako nije pronadjen vraca -1 */
    return -1;
}

Prilagođavanje različitim skupovima podataka[uredi | uredi izvor]

Kada su ključevi za sortiranje uniformno raspoređeni brojevi, linearna interpolacija se implementira relativno jednostavno i pronalazi indeks koji je vrlo blizu tražene vrednosti. Sa druge strane, za telefonski imenik sortiran po prezimenima, takav način implementacije interpolacione pretrage ne može da se primeni. Neki principi visokog nivoa ipak i dalje važe - npr. moguće je proceniti poziciju traženog unosa u imeniku koristeći relativnu frekvenciju slova.

Neke implementacije interpolacione pretrage ne rade na zadovoljavajući način ako se primene na skup podataka koji poseduje niz jednakih vrednosti ključeva. Najjednostavnija implementacija interpolacione pretrage neće nužno izabrati prvi (ili poslednji) element u takvom nizu.

Primene[uredi | uredi izvor]

Pre nego što se odlučimo za ovaj algoritam pretrage treba imati na umu da je kod izbora narednog indeksa potrebno izvršiti nešto komplikovanije aritmetičke operacije. Ova vrsta pretrage može biti korisna za pronalaženje određenog podatka u velikoj sortiranoj datoteci na disku, gde svako poređenje podrazumeva pretraživanje diska, što je mnogo skuplje od interpolacione aritmetike.

Indeksirane strukture podataka kao što je B-stablo takođe redukuju broj pristupa disku, i češće se koriste za indeksiranje podataka na tvrdim diskovima, delom zato što mogu da obrađuju različite tipove podataka i imaju mogućnost onlajn ažuriranja. Međutim, interpolaciona pretraga može biti korisna ako je potrebno pretražiti sortiran, ali neindeksiran skup velikih datoteka.

Vidi još[uredi | uredi izvor]

Reference[uredi | uredi izvor]

^ ^a ^b ^v Živković, Miodrag, Algoritmi (PDF), Matematički fakultet, Univerzitet u Beogradu, str. 84—84
^ Sedgewick, Robert (1990), Algorithms in C (3rd izd.), Addison-Wesley, str. 500—501

Spoljašnje veze[uredi | uredi izvor]

[algziv-1] v Živković, Miodrag, Algoritmi (PDF), Matematički fakultet, Univerzitet u Beogradu, str. 84—84

[sedgw-2] Sedgewick, Robert (1990), Algorithms in C (3rd izd.), Addison-Wesley, str. 500—501

[1]

[2]