En análisis matemático e informática , funciones que son el orden Z , la curva de Lebesgue , la curva de relleno de espacio de Morton , [1] el orden de Morton o el código de Morton asignan datos multidimensionales a una dimensión preservando la localidad de los puntos de datos. Lleva el nombre en Francia en honor a Henri Lebesgue , quien lo estudió en 1904, [2] y en los Estados Unidos en honor a Guy Macdonald Morton, quien aplicó por primera vez la orden a la secuenciación de archivos en 1966. [3] El valor z de un punto en multidimensiones se calcula simplemente entrelazando las representaciones binarias de sus valores de coordenadas. Una vez que los datos se clasifican en este orden, se puede utilizar cualquier estructura de datos unidimensional, como matrices unidimensionales simples , árboles de búsqueda binarios , árboles B , listas de omisión o (con bits poco significativos truncados) tablas hash . El orden resultante puede describirse de manera equivalente como el orden que se obtendría al atravesar primero en profundidad un árbol cuádruple o un ocárbol .
La siguiente figura muestra los valores Z para el caso bidimensional con coordenadas enteras 0 ≤ x ≤ 7, 0 ≤ y ≤ 7 (se muestran tanto en decimal como en binario). Intercalando los valores de coordenadas binarias (comenzando a la derecha con el bit x (en azul) y alternando a la izquierda con el bit y (en rojo)) se obtienen los valores z binarios (inclinados 45° como se muestra). Conectar los valores z en su orden numérico produce la curva recursivamente en forma de Z. Los valores Z bidimensionales también se conocen como valores de cuatro teclas.
Los valores Z de las coordenadas x se describen como números binarios de la secuencia Moser-de Bruijn , que tienen bits distintos de cero solo en sus posiciones pares:
x[] = {0b000000, 0b000001, 0b000100, 0b000101, 0b010000, 0b010001, 0b010100, 0b010101}La suma y la diferencia de dos valores de x se calculan mediante operaciones bit a bit :
x[i+j] = ((x[i] | 0b10101010) + x[j]) y 0b01010101x[i−j] = ((x[i] & 0b01010101) − x[j]) & 0b01010101 si i ≥ j
Esta propiedad se puede utilizar para compensar un valor Z, por ejemplo, en dos dimensiones, las coordenadas hacia arriba (y decreciente), abajo (y creciente), izquierda (x decreciente) y derecha (x creciente) del valor Z actual. z son:
arriba = (((z y 0b10101010) − 1) y 0b10101010) | (z & 0b01010101)abajo = (((z | 0b01010101) + 1) & 0b10101010) | (z & 0b01010101)izquierda = (((z y 0b01010101) − 1) y 0b01010101) | (z&0b10101010)derecha = (((z | 0b10101010) + 1) & 0b01010101) | (z y 0b10101010)
Y en general para sumar dos valores Z bidimensionales w y z :
suma = ((z | 0b10101010) + (w & 0b01010101) & 0b01010101) | ((z | 0b01010101) + (w & 0b10101010) & 0b10101010)
El orden Z se puede utilizar para construir eficientemente un árbol cuádruple (2D) o un ocárbol (3D) para un conjunto de puntos. [4] [5] La idea básica es ordenar el conjunto de entradas según el orden Z. Una vez ordenados, los puntos pueden almacenarse en un árbol de búsqueda binario y usarse directamente, lo que se denomina quadtree lineal, [6] o pueden usarse para construir un quadtree basado en punteros.
Los puntos de entrada generalmente se escalan en cada dimensión para que sean números enteros positivos, ya sea como una representación de punto fijo en el rango de unidades [0, 1] o correspondiente al tamaño de la palabra de la máquina. Ambas representaciones son equivalentes y permiten encontrar el bit distinto de cero de mayor orden en tiempo constante. Cada cuadrado en el árbol cuádruple tiene una longitud de lado que es una potencia de dos y coordenadas de esquina que son múltiplos de la longitud del lado. Dados dos puntos cualesquiera, el cuadrado derivado de los dos puntos es el cuadrado más pequeño que cubre ambos puntos. El entrelazado de bits de los componentes xey de cada punto se denomina mezcla aleatoria de xey y puede extenderse a dimensiones superiores. [4]
Los puntos se pueden ordenar según su orden aleatorio sin intercalar explícitamente los bits. Para ello, para cada dimensión, se examina el bit más significativo de la exclusiva o de las coordenadas de los dos puntos de esa dimensión. La dimensión para la cual el bit más significativo es mayor se utiliza luego para comparar los dos puntos y determinar su orden aleatorio.
La operación exclusiva o enmascara los bits de orden superior para los cuales las dos coordenadas son idénticas. Dado que la mezcla entrelaza bits de orden superior a orden inferior, al identificar la coordenada con el bit más grande y significativo, se identifica el primer bit en el orden de mezcla que difiere, y esa coordenada se puede utilizar para comparar los dos puntos. [7] Esto se muestra en el siguiente código Python:
def cmp_zorder ( lhs , rhs ) -> bool : """Comparar orden z.""" # Supongamos objetos de índices tipo matriz lhs y rhs. afirmar len ( lhs ) == len ( rhs ) # Contendrá la dimensión más significativa. msd = 0 # Recorre las otras dimensiones. para dim in range ( 1 , len ( lhs )): # Verifique si la dimensión actual es más significativa # comparando los bits más significativos. si less_msb ( lhs [ msd ] ^ rhs [ msd ], lhs [ dim ] ^ rhs [ dim ]): msd = tenue return lhs [ msd ] < rhs [ msd ] Una forma de determinar si el bit más significativo es más pequeño es comparar el piso del logaritmo de base 2 de cada punto. Resulta que la siguiente operación es equivalente y solo requiere operaciones exclusivas u: [7]
def less_msb ( x : int , y : int ) -> bool : retorno x < y y x < ( x ^ y )También es posible comparar números de coma flotante utilizando la misma técnica. La less_msbfunción se modifica para comparar primero los exponentes. Sólo cuando son iguales se less_msbutiliza la función estándar en las mantisas. [8]
Una vez que los puntos están ordenados, dos propiedades facilitan la construcción de un árbol cuádruple: la primera es que los puntos contenidos en un cuadrado del árbol cuádruple forman un intervalo contiguo en el orden ordenado. La segunda es que si más de un hijo de un cuadrado contiene un punto de entrada, el cuadrado es el cuadrado derivado de dos puntos adyacentes en el orden ordenado.
Para cada par de puntos adyacentes, se calcula el cuadrado derivado y se determina la longitud de su lado. Para cada cuadrado derivado, el intervalo que lo contiene está delimitado por el primer cuadrado más grande a la derecha y a la izquierda en orden. [4] Cada uno de estos intervalos corresponde a un cuadrado en el árbol cuádruple. El resultado de esto es un árbol cuádruple comprimido, donde solo están presentes nodos que contienen puntos de entrada o dos o más hijos. Se puede construir un árbol cuádruple no comprimido restaurando los nodos faltantes, si se desea.
En lugar de construir un árbol cuádruple basado en punteros, los puntos se pueden mantener ordenados en una estructura de datos como un árbol de búsqueda binario. Esto permite agregar y eliminar puntos en tiempo O (log n ) . Se pueden fusionar dos árboles cuádruples fusionando los dos conjuntos de puntos ordenados y eliminando duplicados. La ubicación del punto se puede realizar buscando los puntos que preceden y siguen al punto de consulta en el orden ordenado. Si el quadtree está comprimido, el nodo predecesor encontrado puede ser una hoja arbitraria dentro del nodo comprimido de interés. En este caso, es necesario encontrar el predecesor del ancestro menos común del punto de consulta y la hoja encontrada. [9]
Mediante el entrelazado de bits, los registros de la base de datos se convierten en una secuencia de bits (posiblemente muy larga). Las secuencias de bits se interpretan como números binarios y los datos se clasifican o indexan según los valores binarios, utilizando cualquier estructura de datos unidimensional, como se menciona en la introducción. Sin embargo, al consultar un rango de búsqueda multidimensional en estos datos, utilizar la búsqueda binaria no es realmente eficiente. Aunque el orden Z preserva bien la localidad, para búsquedas de rango eficientes es necesario un algoritmo para calcular, desde un punto encontrado en la estructura de datos, el siguiente valor Z posible que esté en el rango de búsqueda multidimensional:
En este ejemplo, el rango que se consulta ( x = 2, ..., 3, y = 2, ..., 6) se indica mediante el rectángulo de puntos. Su valor Z más alto (MAX) es 45. En este ejemplo, el valor F = 19 se encuentra al buscar una estructura de datos en la dirección creciente del valor Z, por lo que tendríamos que buscar en el intervalo entre F y MAX (área rayada ). Para acelerar la búsqueda, se calcularía el siguiente valor Z que está en el rango de búsqueda, llamado BIGMIN (36 en el ejemplo) y solo se buscaría en el intervalo entre BIGMIN y MAX (valores en negrita), omitiendo así la mayoría de los sombreados. área. La búsqueda en dirección decreciente es análoga a LITMAX , que es el valor Z más alto en el rango de consulta inferior a F. El problema de BIGMIN fue planteado por primera vez y su solución mostrada en Tropf y Herzog. [10]
Tropf proporciona en 2021 una explicación detallada del algoritmo de cálculo LITMAX/BIGMIN, junto con el código fuente Pascal (3D, fácil de adaptar a nD) y sugerencias sobre cómo manejar datos de punto flotante y posiblemente datos negativos: Aquí, el entrelazado de bits es no hecho explícitamente; la estructura de datos solo tiene punteros a los registros de la base de datos originales (sin clasificar). Con una función general de comparación de registros (mayor-menor-igual, en el sentido de valor z), se evitan complicaciones con secuencias de bits que exceden la longitud de la palabra de la computadora, y el código se puede adaptar fácilmente a cualquier número de dimensiones y cualquier registro. longitud de la palabra clave.
Como el enfoque no depende de la estructura de datos unidimensional elegida, todavía hay libertad de elección para estructurar los datos, por lo que se pueden utilizar métodos bien conocidos, como los árboles equilibrados, para hacer frente a datos dinámicos y mantener el equilibrio del árbol al insertar o eliminar. toma tiempo O (log n). El método también se utiliza en árboles UB (equilibrados), [11] con el nombre "GetNextZ-address" para BIGMIN.
La elección libre facilita la incorporación del método a las bases de datos existentes. Esto contrasta, por ejemplo, con los árboles R , donde se necesitan consideraciones especiales.
La aplicación del método jerárquicamente (según la estructura de datos disponible), opcionalmente en dirección creciente y decreciente, produce una búsqueda de rango multidimensional altamente eficiente que es importante tanto en aplicaciones comerciales como técnicas, por ejemplo, como procedimiento subyacente a las búsquedas de vecinos más cercanos. El orden Z es uno de los pocos métodos de acceso multidimensional que se ha introducido en los sistemas de bases de datos comerciales. [12] El método se utiliza en diversas aplicaciones técnicas de diferentes campos [13] y en sistemas de bases de datos comerciales. [14]
Ya en 1966, GMMorton propuso el orden Z para la secuenciación de archivos de una base de datos geográfica bidimensional estática. Las unidades de datos de área están contenidas en uno o varios marcos cuadráticos representados por sus tamaños y valores Z de la esquina inferior derecha, cumpliendo los tamaños con la jerarquía de orden Z en la posición de la esquina. Con una alta probabilidad, el cambio a un cuadro adyacente se realiza con uno o unos pocos pasos de escaneo relativamente pequeños. [3]
Como alternativa, se ha sugerido la curva de Hilbert, ya que tiene un mejor comportamiento de conservación del orden [5] y, de hecho, se utilizó en un índice optimizado, la geometría S2. [15]
El algoritmo de Strassen para la multiplicación de matrices se basa en dividir las matrices en cuatro bloques, y luego dividir recursivamente cada uno de estos bloques en cuatro bloques más pequeños, hasta que los bloques sean elementos únicos (o más prácticamente: hasta llegar a matrices tan pequeñas que la ecuación de Moser-de El algoritmo trivial de la secuencia de Bruijn es más rápido). Organizar los elementos de la matriz en orden Z mejora la localidad y tiene la ventaja adicional (en comparación con el orden principal por filas o columnas) de que la subrutina para multiplicar dos bloques no necesita conocer el tamaño total de la matriz, sino solo el Tamaño de los bloques y su ubicación en la memoria. Se ha demostrado el uso eficaz de la multiplicación de Strassen con orden Z; consulte el artículo de Valsalam y Skjellum de 2002. [dieciséis]
Buluç et al. presenta una estructura de datos matricial dispersa que ordena en Z sus elementos distintos de cero para permitir la multiplicación paralela de matrices y vectores. [17]
Las matrices en álgebra lineal también se pueden recorrer utilizando una curva de relleno de espacio. [18] Los bucles convencionales atraviesan una matriz fila por fila. Atravesar con la curva Z permite un acceso eficiente a la jerarquía de memoria . [19]
Algunas GPU almacenan mapas de textura en orden Z para aumentar la localidad espacial de referencia durante la rasterización del mapa de textura . Esto permite que las líneas de caché representen mosaicos rectangulares, lo que aumenta la probabilidad de que los accesos cercanos estén en el caché. A mayor escala, también disminuye la probabilidad de los costosos llamados "saltos de página" (es decir, el costo de cambiar filas ) en SDRAM/DDRAM. Esto es importante porque la renderización 3D implica transformaciones arbitrarias (rotaciones, escalado, perspectiva y distorsión por superficies animadas).
Estos formatos a menudo se denominan texturas swizzled o texturas giradas . También se pueden utilizar otros formatos de mosaico.
El algoritmo de Barnes-Hut requiere la construcción de un octree. Almacenar los datos como un árbol basado en punteros requiere muchas desreferencias de punteros secuenciales para iterar sobre el ocárbol en primer orden en profundidad (caro en una máquina de memoria distribuida). En cambio, si uno almacena los datos en una tabla hash , utilizando hash de octree, la curva de orden Z naturalmente itera el octree en primer orden en profundidad. [5]