Laskennassa ja tietojenkäsittelytieteessä Mortonin käyrä , Z-sekvenssi , Z-järjestys , Lebesgue-käyrä , Mortonin järjestys tai Morton- koodi on funktio , joka kartoittaa moniulotteisen tiedon yksiulotteiseksi dataksi säilyttäen samalla tietopisteiden sijainnin. Guy MacDonald Morton esitteli toiminnon vuonna 1966 [1] . Moniulotteisen avaruuden pisteen Z-arvo on helppo laskea vuorotellen sen koordinaattiarvojen binäärilukuja . Kun tiedot tallennetaan tässä järjestyksessä, voidaan käyttää mitä tahansa yksiulotteisia rakenteita, kuten binäärihakupuita , B-puita , ohituslistoja tai hash-taulukoita (jossa pienet bitit hylätään). Näin luotua järjestystä voidaan vastaavasti kuvata järjestykseksi, joka voidaan saada nelipuun syvyys -ensimmäisellä läpikulkulla .
Alla oleva kuva näyttää Z-arvot 2D-tapaukselle kokonaislukukoordinaateilla 0 ⩽ x ⩽ 7, 0 ⩽ y ⩽ 7 (sekä desimaali- että binääriarvot on esitetty). Koordinaattien binäärilukujen vuorottelu tuottaa binääriset z -arvot, kuten kuvassa näkyy. Yhdistämällä z - arvot niiden tavanomaiseen numeeriseen järjestykseen saadaan rekursiivinen Z-käyrä. Kaksiulotteisia Z-arvoja kutsutaan myös kvadranttiavaimiksi.
Z-arvot x - akselilla kuvataan binäärilukuina Moser-de Bruijn-sekvenssistä , joissa on nollasta poikkeavia bittejä vain niiden parillisissa paikoissa:
x[] = {0b000000, 0b000001, 0b000100, 0b000101, 0b010000, 0b010001, 0b010100, 0b010101}Kahden arvon summa ja ero suhteessa x -koordinaattiin lasketaan bittikohtaisilla operaatioilla :
x[i+j] = ((x[i] | 0b10101010) + x[j]) & 0b01010101 x[ij] = ((x[i] & 0b01010101) - x[j]) & 0b01010101, jos i >= jZ-järjestystä voidaan käyttää rakentamaan tehokkaasti nelipuu pistejoukolle [2] . Perusideana on lajitella syötepisteiden joukko Z-järjestyksen mukaan. Kun pisteet on lajiteltu, ne voidaan tallentaa binäärihakupuuksi ja käyttää suoraan, jota kutsutaan lineaariseksi nelipuuksi [3] , tai niitä voidaan käyttää osoitinpohjaisen nelipuun muodostamiseen.
Syöttöpisteet skaalataan tyypillisesti kutakin ulottuvuutta pitkin positiivisten kokonaislukujen tuottamiseksi joko kiinteän pisteen numeroina välillä [0, 1] tai konesanaa vastaavassa välissä. Molemmat esitykset ovat vastaavia ja mahdollistavat merkittävimmän nollasta poikkeavan bitin löytämisen vakioajassa. Minkä tahansa neliön neliön sivun pituus on potenssi kaksi, ja kulmakoordinaatit ovat sivun pituuden kerrannaisia. Jos annetaan kaksi pistettä, näiden kahden pisteen johdettu neliö on pienin neliö, joka peittää molemmat pisteet. Vuorottelevia bittejä kunkin pisteen x- ja y-koordinaateista kutsutaan x- ja y- sekoitukseksi , ja ne voidaan laajentaa suurempiin ulottuvuuksiin [2] .
Pisteet voidaan lajitella niiden sekoituksen mukaan ilman nimenomaista bittikiertoa. Tätä varten jokaisessa mittauksessa tarkistetaan kyseisen mittauksen kahden pisteen koordinaattien korkean kertaluvun XOR - bitti . Dimensiota, jonka merkitsevin bitti on suurempi, käytetään sitten kahden pisteen vertaamiseen niiden sekoitusjärjestyksen määrittämiseksi.
XOR-operaatio poistaa samat korkeat bitit, jotka ovat samat molemmille koordinaateille. Koordinaatin löytäminen merkitsevimmän bitin kanssa määrittää ensimmäisen bitin, joka poikkeaa sekoitusjärjestyksessä, ja tätä koordinaattia voidaan käyttää kahden pisteen vertailuun [4] . Tämä näkyy seuraavassa Python-koodissa:
def cmp_zorder ( a , b ): j = 0 k = 0 x = 0 k :lle alueella ( dim ) : y = a [ k ] ^ b [ k ] jos vähemmän_msb ( x , y ): j = k x = y palauttaa a [ j ] - b [ j ]Yksi tapa määrittää, onko merkittävin bitti pienempi, on verrata kunkin pisteen pyöristettyä binaarilogaritmia. Osoittautuu, että seuraava operaatio on ekvivalentti ja vaatii vain XOR-operaation [4] :
def less_msb ( x , y ): palauttaa x < y ja x < ( x ^ y )Liukulukuja on mahdollista verrata samalla tekniikalla. less_msb -funktiota muutetaan vertaamaan eksponenteja ensin. Vain jos ne täsmäävät, vakiofunktio less_msb suoritetaan mantissoilla [5] .
Kun pisteet on lajiteltu, kaksi ominaisuutta helpottaa nelipuun rakentamista. Ensimmäinen ominaisuus on, että nelipuun neliön sisältämät pisteet muodostavat lajittelussa yhtenäisen välin. Toinen ominaisuus on, että jos useampi kuin yksi nelikulmainen lapsi sisältää syötepisteen, neliö on lajittelun kahden vierekkäisen pisteen johdettu neliö .
Jokaiselle vierekkäiselle pisteparille lasketaan johdettu neliö ja sen sivun pituus. Jokaisen johdetun neliön kohdalla sen sisältävä väli rajataan lajittelun oikealla ja vasemmalla ensimmäisellä suurimmalla neliöllä [2] . Jokainen tällainen intervalli vastaa neliötä neliössä. Tuloksena on pakattu nelipuu, jossa on vain sisääntulopisteitä sisältävät solmut tai kaksi tai useampia jälkeläisiä. Pakkaamaton quadtree voidaan rakentaa palauttamalla puuttuvat solmut tarvittaessa.
Pistepohjaisen nelipuun rakentamisen sijaan pisteitä voidaan käsitellä lajiteltuun järjestykseen käyttämällä tietorakenteita, kuten binaarihakupuuta. Tämä mahdollistaa pisteiden lisäämisen ja poistamisen O(log n) -ajassa. Kaksi nelipuuta voidaan yhdistää yhdistämällä kaksi lajiteltua pistejoukkoa ja poistamalla kaksoiskappaleet. Pisteen sijainti voidaan määrittää tarkastelemalla kyselyn pistettä edeltäviä ja seuraavia pisteitä lajittelujärjestyksessä. Jos nelipuu on pakattu, edellinen löydetty solmu voi olla mielivaltainen lehti kiinnostavan pakatun solmun sisällä. Tässä tapauksessa on tarpeen löytää kyselystä ja löydetystä taulukosta edellinen yhteinen pistesolmu [6] .
Tehokas aluehaku vaatii algoritmin seuraavan Z-arvon laskemiseksi, jonka on oltava moniulotteisen hakualueen sisällä:
Tässä esimerkissä hakualue ( x = 2, …, 3, y = 2, …, 6) on korostettu pisteviivalla. Suurin Z-arvo (MAX) tällä alueella on 45. Tässä esimerkissä arvo F = 19 esiintyy, kun tarkastellaan tietoja nousevassa Z-arvojärjestyksessä, joten meidän on etsittävä F:n ja MAX:n välillä (varjostettu alue). . Haun nopeuttamiseksi on toivottavaa laskea seuraava hakualueeseen kuuluva Z-arvo nimeltä BIGMIN (esimerkissämme 36) ja sitten etsiä vain BIGMIN ja MAX väliltä (näkyy lihavoituna), jolloin hävittää suurimman osan varjostetusta alueesta. Alaspäin suuntautuva haku on samanlainen, tässä LITMAX on kyselyn suurin Z-arvo alueella, joka on pienempi kuin F. BIGMIN-hakutehtävä muotoiltiin ensin ja ratkaisu ongelmaan esitettiin Tropfin ja Herzogin työssä [7] . Tätä ratkaisua käytetään UB-puissa ("GetNextZ-osoite"). Koska lähestymistapa ei riipu valitusta yksiulotteisesta tietorakenteesta, sen valinnassa on vapaus, jolloin voidaan käyttää hyvin tunnettuja menetelmiä, kuten balansoituja puita, työskennellä muuttuvan datan kanssa (toisin kuin esim. o R-puut ). , joissa tarvitaan erityissopimuksia). Lisäksi tämä riippumattomuus helpottaa menetelmän käyttöä olemassa olevissa tietokannoissa.
Hierarkkisesti käytettynä (kyseisen tietorakenteen mukaan) menetelmä tarjoaa erittäin tehokkaan etäisyyshaun molempiin suuntiin (laskeva tai nouseva), mikä on tärkeää sekä kaupallisissa että teollisissa sovelluksissa, esimerkiksi proseduurin muodossa. jonka perusteella etsitään lähin naapuri. Z-order on yksi harvoista menetelmistä päästä käsiksi moniulotteiseen dataan, joka on löytänyt tiensä kaupallisiin tietokantoihin ( Oracle Database 1995 ( Gaede, Guenther 1998 ), Transbase 2000 ( Ramsak, Markl, Fenk, Zirkel, Elhardt, Bayer 2000 ).).
Vuonna 1966 G. M. Morton ehdotti Z-järjestystä tiedostojen järjestämiseksi staattiseen kaksiulotteiseen maantieteelliseen tietokantaan. Pintatietoyksiköt sisältyvät yhteen useista neliölaatikoista, joita edustavat laatikon koko ja oikean alakulman Z-arvo. Suurella todennäköisyydellä siirtyminen viereiseen kehykseen suoritetaan yhdellä tai useammalla suhteellisen pienellä haulla.
Vaihtoehtona suositellaan Hilbertin käyrän käyttöä , koska se säilyttää järjestyksen paremmin, mutta laskelmat ovat tässä tapauksessa huomattavasti monimutkaisempia, mikä johtaa raskaaseen suorittimen käyttöön. BIGMIN-lähdekoodit sekä Z- että Hilbert-käyrälle on kuvattu H. Tropfin patentissa. [kahdeksan]
Yleiskatsauksen monimuuttujatietojen käsittelystä, mukaan lukien lähimmän naapurin hausta, katso Hanan Samet [9] .
Strassenin matriisin kertolaskualgoritmi perustuu matriisien osiointiin neljään lohkoon ja kunkin lohkon jakamiseen rekursiivisesti neljään pienempään lohkoon, kunnes lohkosta tulee identiteettielementti (tai käytännöllisemmin, kunnes tuloksena olevat matriisit ovat niin pieniä, että on triviaalia, että algoritmi toimii niissä nopeammin). Matriisin elementtien järjestäminen Z-järjestykseen parantaa lokaliteettia ja sillä on lisäetu (verrattuna rivi- tai sarakejärjestykseen), että kahden lohkon kertomisaliohjelman ei tarvitse tietää matriisin täyttä kokoa, riittää kun tietää lohkon koko ja sijainti muistissa. Tehokas Z-järjestyksen Strassen-algoritmi on esitetty Valsalamin ja Skjellumin vuoden 2002 artikkelissa [10] .
Buluk et ai. ehdottivat harvaa matriisiesitysrakennetta vektori-matriisikertolaskun rinnastamiseksi . Tässä esityksessä nollasta poikkeavat elementit on järjestetty Z-järjestykseen [11] .
Jotkut grafiikkasuorittimet tallentavat pintakuvioita Z-järjestyksessä lisätäkseen spatiaalisen viitepaikan pintakuvioiden rasteroinnin . Tämän ansiosta välimuistirivit voivat edustaa neliömäisiä ruutuja, mikä lisää todennäköisyyttä, että suljetut kyselyt päätyvät välimuistiin. Tämä on merkittävää, koska renderöinti 3D-tilassa sisältää mielivaltaisia muunnoksia (pintojen kierto, skaalaus, perspektiivi ja kaarevuus). Myös muita mosaiikkiformaatteja voidaan käyttää.