Kriva oblika Z

U matematičkoj analizi i informatici, Z-kriva, Morton red, ili Mortonov kod je funkcija koja mapira multidimenzionalne podatke u jednu dimenziju i pritom čuva lokalitet tačaka podataka. G. M. Morton ju je predstavio 1966 godine. Z-Vrednost tačke u multidimenzijama se jednostavno izračunava prepletanjem binarnih reprezentacija njenih koordinatnih vrednosti. Kada se podaci sortiraju po ovom redosledu, bilo koja jednodimenzionalna struktura podataka se moze koristiti kao binarno stablo pretrage, B-stablo, Skip lista ili Heš tabele. Dobijeni poredak se moze ekvivalentno opisati kao redosled koji bi se dobio proslakom kroz kvadratno stablo koristeći algoritam pretrage u dubinu; zbog bliske veze sa kvadratnim stablima, Z-redosled se moze koristiti za efikasnu konstrukciju kvadratnih stabala i povezanih visedimenzionalnih struktura podataka.

četiri iteracije krive u obliku slova Z.

Z-order curve iterations extended to three dimensions.

Vrednosti koordinata

Figura ispod pokazuje Z-vrednosti za dvodimenzionalni slučaj sa celobrojnim koordinatama 0 ≤ x ≤ 7, 0 ≤ y ≤ 7 (prikazano i u decimalnom i binarnom sistemu). Prepletanjem binarnih vrednosti koordinata dobijamo binarne z-vrednosti kao sto je prikazano. Povezivanje z-vrednosti po njihovom numeričkom redosledu proizvodi rekurzivno krivu oblika Z.

Efikasno formiranje kvadratnih stabala

Kao sto je pomenuto, Z-poredak se može koristiti za efikasno formiranje kvadratnih stabala za par tačaka. Osnovna ideja je da treba sortirati ulazni par preko Z-poretka. Kada se to sortira, tačke mogu da se čuvaju ili u binarnom stablu pretrage i koriste direktno, što se naziva linearno kvadratno stablo, ili se mogu koristiti za formiranje kvadratnog stabla zasnovanog na pokazivačima.

Ulazne tačke su uobičajno skalirane u svakoj dimenziji da budu pozitivni celi brojevi, ili kao fiksna tačka sa reprezentacijom predstavljenom preko opsega [0, 1] ili tako da odgovara veličini mašinske reči. Obe reprezentacije su ekvivalentne i omogućavaju bitu najveće težine da bude pronađen u konstantnom vremenu. Svaki kvadrat u kvadratnom stablu ima bočnu dužinu koja je stepena dva, i koordinate temena koje su umnošci dužina strana. Imajući u vidu bilo koje dve tačke, dobijeni kvadrat za te dve tačke je najmanji kvadrat koji pokriva obe tačke. Preplitanje bitova iz X i Y komponenti svake tačke se naziva "reprodukcija" od X i Y i može se primeniti i na većim dimenzijama.

Tačke mogu biti sortirane prema njihovoj reprodukciji bez eksplicitnog preplitanja bitova. Da bismo ovo uradili, za svaku dimenziju,ispituje se bit najvece tezine dobijen ekskluyivnom disjunkcijom koordinata te dve tačke za tu dimenziju. Dimenzija za koju bit najvece težine je veći, koristi se za poređenje dve tačke da bi se utvrdio redosled njihove reprodukcije.

Operacija ekskluzivne disjunkcije maskira bitove većeg reda za koje su te dve koordinate identične. Pošto reprodukcija prepliće bitove od višeg reda ka nižem, pritom indentifikujući koordinate većeg bita sa najvećom težinom, identifikuje se prvi bit u redu reprodukcije koji se razlikuje, i pomocu te koordinate se mogu porediti te dve tačke. Ovo je prikazano u Python kodu:

    def cmp_zorder(a, b):
        j = 0
        k = 0
        x = 0
        for k in range(dim):
            y = a[k] ^ b[k]
            if less_msb(x, y):
                j = k
                x = y
        return a[j] - b[j]

Jedan od načina da se utvrdi da li je bit najvece težine manji, je poredjenje donjeg nivoa logaritma baze 2 svake tačke. Ispostavlja se da je sledeća operacija ekvivalentna i jedino zahteva operacije ekskluzivne disjunkcije.

    def less_msb(x, y):
        return x < y and x < (x ^ y)

Takođe je moguće porediti brojeve u pokretnom zarezu služeći se istom tehnikom. less_msb funkcija je modifikovana tako da prvo poredi eksponente. Jedino kada su jednaki, onda standardna funkcija less_msb se koristi u mantisama.

Kada su tačke u sortiranom poretku, postoje dve osobine koje olakšavaju građu kvadratnog stabla: Prva je da tačke sadržane u kvadratu kvadratnog stabla formiraju granični interval u sortiranom poretku. Druga osobina je ta da ukoliko više od jednog deteta kvadrata sadrži ulaznu tačku, kvadrat je dobijeni kvadrat za dve susedne tačke u sortiranom poretku.

Za svaki susedni par tačaka izvedeni kvadrat je izračunat i njegove bočne strane su određene. Za svaki izvedeni kvadrat interval koji ga sadrži je vezan prvim vecim kvadratom sa desne i leve strane u sortiranom poretku. Svaki takav interval odgovara kvadratu u kvadratnom drvetu. Rezultat ovoga je kompresovano kvadratno stablo, gde su prisutni samo čvorovi koji sadrže ulazne tačke ili dva ili više deteta. Ne kompresovano kvadratno stablo moze biti formirano tako što ćemo vratiti čvorove koji nedostaju.

Umesto formiranja kvadratnog stabla baziranog na pokazivačima, tačke mogu biti održane u sortiranom poretku u strukturi podataka kao što je binarne stablo pretrage. Zahvaljujući ovome tačke mogu biti dodate i obrisane u O(log n) vremenu. Dva kvadratna stabla se mogu pripojiti spajanjem dva seta sortiranih tačaka i uklanjanjem duplikata. Lokacija tačke se moze pronaći traženjem tačaka koje prethode i javljaju se posle tačke upita u sortiranom poretku. Ako je kvadratno stablo kompresovano, pronađeni čvor predak moze biti nasumicni list unutar traženog kompresovanog čvora. U ovom slučaju neophpdno je pronaći prethodnika najmanje zajedničkog pretka upitne tačke i pronađenog lista.

Upotreba sa jednodimenzionalnim strukturama podataka za traženje opsega

Iako dobro očuvava lokalitet, za efikasnu pretragu opsega neophodan je algoritam za računanje, od tačke pronadjene u strukturi podataka sledeće Z-vrednositi koja se nalazi u multidimenzionalnom opsegu pretrage:

U ovom primeru, opseg koji se pretrazuje (x = 2, ..., 3, y = 2, ..., 6) je označen isprekidanim pravougaonikom. Njegova najveća Z-vrednost (MAX) iznosi 45. U ovom primeru vrednost F = 19 pronađena je kada se vrši pretraga strukture podataka u pravcu porasta Z-vrednosti, pa bismo morali da pretražujemo u intervalu izmedju F i MAX (Hatch oblast). Kako bi ubrzali pretragu mogli bi izračunati sledeću Z vrednost koja je u opsegu pretrage, zvana BIGMIN (36 u primeru) i pretražiti samo u intervalu izmedju BIGMIN i MAX (podebljane vrednosti), i tako bismo izbegli veći deo Hatch oblasti. Pretraga u pravcu opadanja je analogna sa LITMAX koji je najveća Z-vrednost u upitnom opsegu manjem od F. BIGMIN problem i njegovo rešenje su prvi put izneti u Tropfu i Harzogu. Ovo rešenje se takođe koristi u UB-stablima ("GetNextZ-address"). Obzirom da pristup ne zavisi od izabranih jednodimenzionalnih struktura podataka, i dalje postoji izbor struktuiranja podataka, tako da dobro poznate metode kao što je balansirano stablo, se mogu koristiti za rad sa dinamickim podacima (nasuprot R-stablima gde je neophodna posebna pažnja). Slično, ova nezavisnost olakšava uključivanje metoda u već postojeće baze podataka.

Primenjujući metod hijerarhijski, (u skladu sa strukturom podataka u pitanju), opciono i u rastućim i opadajućim pravcima, dobijamo visoko efikasne multidimenzionalne opsege pretraga koji su bitni i u komercijalnim i u tehničkim aplikacijama. Z-poredak je jedna od nekoliko multidimenzionalnih metoda pristupa koje su se zadržale u komercijalnim sistemima baza padataka(Oracle database 1995)

Još 1966. godine, G.M.Morton je predložio Z-redosled za sekvenciranje statičnih dvodimenzionalnih geopgrafskih baza. Prostorne (kontinualne) jedinice podataka su sadržane u jednom ili više kvadratnih frejmova predstavljenim njihovim veličinama i donjim desnim uglom Z-vrednsti, veličine ispunjavaju hijerarhiju Z-poretka na poziciji temena. Sa velikom verovatnoćom, menjanje na susedni frejm se vrši sa jednim ili više, relativno malim koracima skeniranja.

Srodne strukture

Kao alternativa, predložena je Hilbertova kriva jer ima bolje ponašanje pri održavanju reda, ali su izračunavanja mnogo komplikovanija, što dovodi do znacajnog opterećivanja procesora. BIGMIN izvorne kodove za Z-krivu i Hilbertovu-krivu je opisao u patentu H. Tropf.

Primene u linearnoj algebri

Štrasenov algoritam za množenje matrica je zasnovan na podeli matrica na četiri bloka, gde se svaki od tih blokova rekurzivno deli na četiri manja, sve dok blokovi ne postanu pojedinačni elementi (preciznije: sve dok dobijene matrice ne postanu toliko male tako da je trivijlni algoriam brži). Uređivanje elemenata matrice u Z-poretku onda poboljšava lokalitet, i ima dodatnu prednost da podrutina za množenje dva bloka ne mora da zna veličinu matrice, vec samo veličinu blokova i njihove lokacije u memoriji.

Spoljašnje veze

• STANN: A library for approximate nearest neighbor search, using Z-order curve Архивирано на сајту Wayback Machine (20. април 2014)
• Methods for programming bit interleaving, Sean Eron Anderson, Stanford University