Крива облика З

четири итерације криве у облику слова З.

З-ордер цурве итератионс еxтендед то тхрее дименсионс.

У математичкој анализи и информатици, З-крива, Мортон ред, или Мортонов код је функција која мапира мултидимензионалне податке у једну димензију и притом чува локалитет тачака података. Г. M. Мортон ју је представио 1966 године. З-Вредност тачке у мултидимензијама се једноставно израчунава преплетањем бинарних репрезентација њених координатних вредности. Када се подаци сортирају по овом редоследу, било која једнодимензионална структура података се мозе користити као бинарно стабло претраге, Б-стабло, Скип листа или Хеш табеле. Добијени поредак се мозе еквивалентно описати као редослед који би се добио прослаком кроз квадратно стабло користећи алгоритам претраге у дубину; због блиске везе са квадратним стаблима, З-редослед се мозе користити за ефикасну конструкцију квадратних стабала и повезаних виседимензионалних структура података.

Вредности координата

Фигура испод показује З-вредности за дводимензионални случај са целобројним координатама 0 ≤ x ≤ 7, 0 ≤ y ≤ 7 (приказано и у децималном и бинарном систему). Преплетањем бинарних вредности координата добијамо бинарне з-вредности као сто је приказано. Повезивање з-вредности по њиховом нумеричком редоследу производи рекурзивно криву облика З.

Ефикасно формирање квадратних стабала

Као сто је поменуто, З-поредак се може користити за ефикасно формирање квадратних стабала за пар тачака. Основна идеја је да треба сортирати улазни пар преко З-поретка. Када се то сортира, тачке могу да се чувају или у бинарном стаблу претраге и користе директно, што се назива линеарно квадратно стабло, или се могу користити за формирање квадратног стабла заснованог на показивачима.

Улазне тачке су уобичајно скалиране у свакој димензији да буду позитивни цели бројеви, или као фиксна тачка са репрезентацијом представљеном преко опсега [0, 1] или тако да одговара величини машинске речи. Обе репрезентације су еквивалентне и омогућавају биту највеће тежине да буде пронађен у константном времену. Сваки квадрат у квадратном стаблу има бочну дужину која је степена два, и координате темена које су умношци дужина страна. Имајући у виду било које две тачке, добијени квадрат за те две тачке је најмањи квадрат који покрива обе тачке. Преплитање битова из X и Y компоненти сваке тачке се назива "репродукција" од X и Y и може се применити и на већим димензијама.

Тачке могу бити сортиране према њиховој репродукцији без експлицитног преплитања битова. Да бисмо ово урадили, за сваку димензију,испитује се бит највеце тезине добијен ексклуyивном дисјункцијом координата те две тачке за ту димензију. Димензија за коју бит највеце тежине је већи, користи се за поређење две тачке да би се утврдио редослед њихове репродукције.

Операција ексклузивне дисјункције маскира битове већег реда за које су те две координате идентичне. Пошто репродукција преплиће битове од вишег реда ка нижем, притом индентификујући координате већег бита са највећом тежином, идентификује се први бит у реду репродукције који се разликује, и помоцу те координате се могу поредити те две тачке. Ово је приказано у Пyтхон коду:

    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]

Један од начина да се утврди да ли је бит највеце тежине мањи, је поредјење доњег нивоа логаритма базе 2 сваке тачке. Испоставља се да је следећа операција еквивалентна и једино захтева операције ексклузивне дисјункције.

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

Такође је могуће поредити бројеве у покретном зарезу служећи се истом техником. лесс_мсб функција је модификована тако да прво пореди експоненте. Једино када су једнаки, онда стандардна функција лесс_мсб се користи у мантисама.

Када су тачке у сортираном поретку, постоје две особине које олакшавају грађу квадратног стабла: Прва је да тачке садржане у квадрату квадратног стабла формирају гранични интервал у сортираном поретку. Друга особина је та да уколико више од једног детета квадрата садржи улазну тачку, квадрат је добијени квадрат за две суседне тачке у сортираном поретку.

За сваки суседни пар тачака изведени квадрат је израчунат и његове бочне стране су одређене. За сваки изведени квадрат интервал који га садржи је везан првим вецим квадратом са десне и леве стране у сортираном поретку. Сваки такав интервал одговара квадрату у квадратном дрвету. Резултат овога је компресовано квадратно стабло, где су присутни само чворови који садрже улазне тачке или два или више детета. Не компресовано квадратно стабло мозе бити формирано тако што ћемо вратити чворове који недостају.

Уместо формирања квадратног стабла базираног на показивачима, тачке могу бити одржане у сортираном поретку у структури података као што је бинарне стабло претраге. Захваљујући овоме тачке могу бити додате и обрисане у О(лог н) времену. Два квадратна стабла се могу припојити спајањем два сета сортираних тачака и уклањањем дупликата. Локација тачке се мозе пронаћи тражењем тачака које претходе и јављају се после тачке упита у сортираном поретку. Ако је квадратно стабло компресовано, пронађени чвор предак мозе бити насумицни лист унутар траженог компресованог чвора. У овом случају неопхпдно је пронаћи претходника најмање заједничког претка упитне тачке и пронађеног листа.

Употреба са једнодимензионалним структурама података за тражење опсега

Иако добро очувава локалитет, за ефикасну претрагу опсега неопходан је алгоритам за рачунање, од тачке пронадјене у структури података следеће З-вредносити која се налази у мултидимензионалном опсегу претраге:

У овом примеру, опсег који се претразује (x = 2, ..., 3, y = 2, ..., 6) је означен испрекиданим правоугаоником. Његова највећа З-вредност (МАX) износи 45. У овом примеру вредност Ф = 19 пронађена је када се врши претрага структуре података у правцу пораста З-вредности, па бисмо морали да претражујемо у интервалу измедју Ф и МАX (Хатцх област). Како би убрзали претрагу могли би израчунати следећу З вредност која је у опсегу претраге, звана БИГМИН (36 у примеру) и претражити само у интервалу измедју БИГМИН и МАX (подебљане вредности), и тако бисмо избегли већи део Хатцх области. Претрага у правцу опадања је аналогна са ЛИТМАX који је највећа З-вредност у упитном опсегу мањем од Ф. БИГМИН проблем и његово решење су први пут изнети у Тропфу и Харзогу. Ово решење се такође користи у УБ-стаблима ("ГетНеxтЗ-аддресс"). Обзиром да приступ не зависи од изабраних једнодимензионалних структура података, и даље постоји избор структуирања података, тако да добро познате методе као што је балансирано стабло, се могу користити за рад са динамицким подацима (насупрот Р-стаблима где је неопходна посебна пажња). Слично, ова независност олакшава укључивање метода у већ постојеће базе података.

Примењујући метод хијерархијски, (у складу са структуром података у питању), опционо и у растућим и опадајућим правцима, добијамо високо ефикасне мултидимензионалне опсеге претрага који су битни и у комерцијалним и у техничким апликацијама. З-поредак је једна од неколико мултидимензионалних метода приступа које су се задржале у комерцијалним системима база падатака(Орацле датабасе 1995)

Још 1966. године, Г.M.Мортон је предложио З-редослед за секвенцирање статичних дводимензионалних геопграфских база. Просторне (континуалне) јединице података су садржане у једном или више квадратних фрејмова представљеним њиховим величинама и доњим десним углом З-вреднсти, величине испуњавају хијерархију З-поретка на позицији темена. Са великом вероватноћом, мењање на суседни фрејм се врши са једним или више, релативно малим корацима скенирања.

Сродне структуре

Као алтернатива, предложена је Хилбертова крива јер има боље понашање при одржавању реда, али су израчунавања много компликованија, што доводи до знацајног оптерећивања процесора. БИГМИН изворне кодове за З-криву и Хилбертову-криву је описао у патенту Х. Тропф.

Примене у линеарној алгебри

Штрасенов алгоритам за множење матрица је заснован на подели матрица на четири блока, где се сваки од тих блокова рекурзивно дели на четири мања, све док блокови не постану појединачни елементи (прецизније: све док добијене матрице не постану толико мале тако да је тривијлни алгориам бржи). Уређивање елемената матрице у З-поретку онда побољшава локалитет, и има додатну предност да подрутина за множење два блока не мора да зна величину матрице, вец само величину блокова и њихове локације у меморији.

Спољашње везе

• СТАНН: А либрарy фор аппроxимате неарест неигхбор сеарцх, усинг З-ордер цурве Архивирано на сајту Wayback Machine (20. април 2014)
• Метходс фор программинг бит интерлеавинг, Сеан Ерон Андерсон, Станфорд Университy