Inom kalkyl och datavetenskap är en Morton-kurva , Z-sekvens , Z-ordning , Lebesgue-kurva , Mortonordning eller Morton -kod en funktion som mappar flerdimensionell data till endimensionell data samtidigt som lokaliseringen av datapunkterna bevaras. Funktionen introducerades 1966 av Guy MacDonald Morton [1] . Z-värdet för en punkt i flerdimensionell rymd beräknas enkelt genom att alternera de binära siffrorna i dess koordinatvärden. När data lagras i denna ordning kan alla endimensionella strukturer användas, såsom binära sökträd .B-träd , hoppa över listor eller hashtabeller (med låga bitar kasserade). Den sålunda skapade ordningen kan på samma sätt beskrivas som den ordning som kan erhållas genom en djup- först genomgång av ett quadtree .
Bilden nedan visar Z-värdena för 2D-fallet med heltalskoordinater 0 ⩽ x ⩽ 7, 0 ⩽ y ⩽ 7 (både decimala och binära värden visas). Alterneringen de binära siffrorna i koordinaterna ger binära z -värden, som visas i figuren. Om vi kopplar z -värdena i deras vanliga numeriska ordning får vi en rekursiv Z-kurva. Tvådimensionella Z-värden kallas även kvadrantnycklar.
Z-värden längs x -axeln beskrivs som binära tal från Moser-de Bruijn-sekvensen , med bitar som inte är noll bara i sina jämna positioner:
x[] = {0b000000, 0b000001, 0b000100, 0b000101, 0b010000, 0b010001, 0b010100, 0b010101}Summan och skillnaden mellan två värden i förhållande till x -koordinaten beräknas med hjälp av bitvisa operationer :
x[i+j] = ((x[i] | 0b10101010) + x[j]) & 0b01010101 x[ij] = ((x[i] & 0b01010101) - x[j]) & 0b01010101 om i >= jZ-ordning kan användas för att effektivt bygga ett quadtree för en uppsättning punkter [2] . Grundidén är att sortera uppsättningen av ingångspunkter enligt Z-ordningen. När de har sorterats kan punkterna lagras som ett binärt sökträd och användas direkt, vilket kallas ett linjärt quadtree [3] , eller så kan de användas för att konstruera ett pekarbaserat quadtree.
Inmatningspunkterna skalas typiskt längs var och en av dimensionerna för att producera positiva heltal, antingen som fixpunktsnummer i intervallet [0, 1] eller i det intervall som motsvarar maskinordet. Båda representationerna är likvärdiga och låter dig hitta den mest signifikanta biten som inte är noll i konstant tid. Varje kvadrat i fyrträdet har en sidolängd som är en potens av två, och hörnkoordinaterna är multiplar av sidolängden. Om två poäng ges är den härledda kvadraten för dessa två poäng den minsta kvadraten som täcker båda punkterna. Alternerande bitar från x- och y-koordinaterna för varje punkt kallas x- och y -blandning och kan utökas till högre dimensioner [2] .
Punkterna kan sorteras enligt deras blandning utan explicit bitrotation. För att göra detta, för varje mätning, kontrolleras XOR - biten av hög ordning för koordinaterna för de två punkterna i den mätningen. Den dimension för vilken den mest signifikanta biten är större används sedan för att jämföra de två punkterna för att bestämma deras blandade ordning.
XOR-operationen tar bort samma höga bitar som är desamma för båda koordinaterna. Att hitta koordinaten med den mest signifikanta biten bestämmer den första biten som skiljer sig i blandningsordning, och denna koordinat kan användas för att jämföra två punkter [4] . Detta visas i följande Python-kod:
def cmp_zorder ( a , b ): j = 0 k = 0 x = 0 för k i intervallet ( dim ): y = a [ k ] ^ b [ k ] om mindre_msb ( x , y ): j = k x = y returnera a [ j ] - b [ j ]Ett sätt att avgöra om den mest signifikanta biten är mindre är att jämföra den avrundade binära logaritmen för varje punkt. Det visar sig att följande operation är likvärdig och kräver endast XOR-operationen [4] :
def less_msb ( x , y ): returnera x < y och x < ( x ^ y )Det är möjligt att jämföra flyttalstal med samma teknik. Funktionen less_msb modifieras för att jämföra exponenter först. Endast om de matchar, exekveras standardfunktionen less_msb på mantissor [5] .
När punkterna väl är sorterade gör två egenskaper det lättare att bygga ett quadtree. Den första egenskapen är att punkterna i en fyrträdsruta bildar ett sammanhängande intervall i sorteringen. Den andra egenskapen är att om mer än ett kvadratiskt barn innehåller en inmatningspunkt, är kvadraten den härledda kvadraten för de två intilliggande punkterna i sorteringen.
För varje angränsande punkterpar beräknas den härledda kvadraten och dess sidolängd. För varje härledd kvadrat avgränsas intervallet som innehåller den av den första största kvadraten till höger och vänster i sorteringen [2] . Varje sådant intervall motsvarar en kvadrat i fyrträdet. Resultatet är ett komprimerat quadtree där endast noder som innehåller ingångspunkter eller två eller flera avkomlingar finns. Ett okomprimerat quadtree kan byggas genom att återställa saknade noder om det behövs.
Istället för att bygga ett punktbaserat quadtree kan punkter bearbetas i sorterad ordning med hjälp av datastrukturer som ett binärt sökträd. Detta gör det möjligt att lägga till och ta bort punkter i O(log n) tid. Två quadtrees kan slås samman genom att sammanfoga två sorterade punktuppsättningar och ta bort dubbletter. Positionen för en punkt kan bestämmas genom att titta på punkterna före och efter punkten i frågan i sorteringsordning. Om quadtreet är komprimerat kan den tidigare hittade noden vara ett godtyckligt blad inom den komprimerade noden av intresse. I det här fallet är det nödvändigt att hitta den tidigare gemensamma punktnoden från frågan och det hittade arket [6] .
En effektiv intervallsökning kräver en algoritm för att beräkna följande Z-värde, som måste ligga inom det flerdimensionella sökintervallet:
I det här exemplet är sökintervallet ( x = 2, …, 3, y = 2, …, 6) markerat med en prickad ruta. Det största Z-värdet (MAX) i detta intervall är 45. I det här exemplet uppstår värdet F = 19 när vi tittar på data i stigande Z-värdesordning, så vi måste söka mellan F och MAX (skuggat område) . För att påskynda sökningen är det önskvärt att beräkna nästa Z-värde som hör till sökområdet, kallat BIGMIN (i vårt exempel, 36), och sedan söka endast i intervallet mellan BIGMIN och MAX (visas i fet stil), därigenom kassera det mesta av det skuggade området. Sökning nedåt är liknande, här är LITMAX det största Z-värdet i frågan över ett intervall mindre än F. BIGMIN-sökningsproblemet formulerades först och lösningen på problemet visades i Tropfs och Herzogs arbete [7] . Denna lösning används i UB-träd ("GetNextZ-adress"). Eftersom tillvägagångssättet inte är beroende av den valda endimensionella datastrukturen finns det frihet att välja den, så att välkända metoder som balanserade träd kan användas för att arbeta med föränderlig data (till skillnad från t.ex. o R-träd , där särskilda konventioner behövs). Detta oberoende gör det också lättare att använda metoden i befintliga databaser.
När den används hierarkiskt (enligt den aktuella datastrukturen) ger metoden en mycket effektiv räckviddssökningsmetod i båda riktningarna (fallande eller stigande), vilket är viktigt i både kommersiella och industriella tillämpningar, till exempel i form av en procedur baserat på som används för att söka efter närmaste granne. Z-order är en av få metoder för att komma åt flerdimensionell data som har hittat sin väg in i kommersiella databaser ( Oracle Database 1995 ( Gaede, Guenther 1998 ), Transbase 2000 ( Ramsak, Markl, Fenk, Zirkel, Elhardt, Bayer 2000 ). ).
1966 föreslog G. M. Morton en Z-order för att beställa filer i en statisk tvådimensionell geografisk databas. Ytdataenheterna finns i en av flera kvadratiska rutor, representerade av rutans storlek och Z-värdet i det nedre högra hörnet. Med en hög grad av sannolikhet utförs övergången till en intilliggande ram genom en eller flera relativt små sökningar.
Som ett alternativ föreslås det att använda Hilbert-kurvan eftersom den har ett bättre ordningsbevarande beteende, men beräkningarna i det här fallet blir betydligt mer komplexa, vilket resulterar i hög CPU-användning. BIGMIN-källkoder för både Z-ordningens kurva och Hilbert-kurvan beskrivs i H. Tropfs patent. [åtta]
För en översikt över multivariat databehandling, inklusive sökning efter närmaste granne, se Hanan Samet [9] .
Strassens algoritm för matrismultiplikation bygger på att dela upp matriserna i fyra block och sedan rekursivt dela upp vart och ett av dessa block i fyra mindre block tills blocket blir ett identitetselement (eller mer praktiskt tills de resulterande matriserna är så små att det är trivialt algoritmen fungerar snabbare på dem). Att organisera elementen i en matris i Z-ordning förbättrar lokaliteten och har den ytterligare fördelen (jämfört med ordning efter rader eller kolumner) att subrutinen för att multiplicera två block inte behöver känna till matrisens fulla storlek, det räcker med att veta blockets storlek och dess position i minnet. En effektiv Z-order Strassen-algoritm ges i en artikel från 2002 av Valsalam och Skjellum [10] .
Buluk et al föreslog en gles matrisrepresentationsstruktur för parallellisering av vektor-matrismultiplikation. I denna representation är element som inte är noll ordnade i Z-ordning [11] .
Vissa GPU :er lagrar texturer i Z-ordning för att öka rumslig referenslokalitet texturrastrering . Detta tillåter cache-rader att representera fyrkantiga brickor, vilket ökar sannolikheten för att stängningsfrågor hamnar i cachen. Detta är viktigt eftersom rendering i 3D-rymden involverar godtyckliga transformationer (rotation, skalning, perspektiv och krökning av ytor). Andra mosaikformat kan också användas.