En informática , un árbol de fusión es un tipo de estructura de datos de árbol que implementa una matriz asociativa en enteros de w bits. Cuando opera en una colección de n pares clave-valor , utiliza el espacio O ( n ) y realiza búsquedas en el tiempo O (log w n ) , que es asintóticamente más rápido que un árbol de búsqueda binario autoequilibrado tradicional , y también mejor que el árbol de van Emde Boas para valores grandes de w. Alcanza esta velocidad explotando ciertas operaciones de tiempo constante que se pueden realizar en una palabra de máquina . Los árboles de fusión fueron inventados en 1990 por Michael Fredman y Dan Willard . [1]
Se han realizado varios avances desde el artículo original de 1990 de Fredman y Willard. En 1999 [2] se mostró cómo implementar árboles de fusión bajo un modelo de cálculo en el que todas las operaciones subyacentes del algoritmo pertenecen a AC 0 , un modelo de complejidad de circuito que permite operaciones booleanas de suma y bit a bit pero no permite las operaciones de multiplicación. utilizado en el algoritmo del árbol de fusión original. En 1996 se propuso una versión dinámica de árboles de fusión que usaban tablas hash [3], que coincidía con el tiempo de ejecución O (log w n ) de la estructura original esperado. En 2007 se propuso otra versión dinámica que utiliza un árbol exponencial [4], que produce tiempos de ejecución en el peor de los casos de O (log w n + log log n ) por operación. Queda pendiente si los árboles de fusión dinámica pueden lograr O (log w n ) por operación con alta probabilidad.
Cómo funciona
Un árbol de fusión es esencialmente un árbol B con un factor de ramificación de w 1/5 (también es posible cualquier exponente pequeño), lo que le da una altura de O (log w n ) . Para lograr los tiempos de ejecución deseados para actualizaciones y consultas, el árbol de fusión debe poder buscar un nodo que contenga hasta w 1/5 claves en tiempo constante. Esto se hace comprimiendo ("dibujando") las claves para que todas puedan caber en una palabra de máquina, lo que a su vez permite hacer comparaciones en paralelo.
Dibujar
El boceto es el método mediante el cual cada clave de w bits en un nodo que contiene k claves se comprime en solo k - 1 bits. Cada clave x puede considerarse como una ruta en el árbol binario completo de altura w que comienza en la raíz y termina en la hoja correspondiente ax . Para distinguir dos caminos, basta con mirar su punto de ramificación (el primer bit donde difieren las dos claves). Todas las k rutas juntas tienen k - 1 puntos de ramificación, por lo que se necesitan como máximo k - 1 bits para distinguir dos de las k claves.
Una propiedad importante de la función de dibujo es que conserva el orden de las teclas. Es decir, dibuje ( x )
Aproximando el boceto
Si las ubicaciones de los bits del esquema son b 1 < b 2 <··· < b r , entonces el esquema de la clave x w -1 ··· x 1 x 0 es el entero r -bit.
Con solo operaciones de palabras estándar, como las del lenguaje de programación C , es difícil calcular directamente el boceto de una clave en tiempo constante. En su lugar, los bits de croquis se pueden empaquetar en un rango de tamaño como máximo r 4 , utilizando AND y multiplicación bit a bit . La operación AND bit a bit sirve para borrar todos los bits que no son de boceto de la clave, mientras que la multiplicación desplaza los bits de boceto a un rango pequeño. Como el boceto "perfecto", el boceto aproximado conserva el orden de las teclas.
Se necesita algún procesamiento previo para determinar la constante de multiplicación correcta. Cada bit de croquis en la ubicación b i se desplazará a b i + m i mediante una multiplicación por m =2 m i . Para que el boceto aproximado funcione, deben cumplirse las siguientes tres propiedades:
- b i + m j son distintos para todos los pares ( i , j ). Esto asegurará que la multiplicación no corrompa los bits del boceto.
- b i + m i es una función estrictamente creciente de i . Es decir, se conserva el orden de los bits del boceto.
- ( segundo r + metro r ) - ( segundo 1 + metro 1 ) ≤ r 4 . Es decir, los bits de croquis se empaquetan en un rango de tamaño como máximo r 4 .
Un argumento inductivo muestra cómo se puede construir m i . Sea m 1 = w - b 1 . Suponga que 1 < t ≤ r y que m 1 , m 2 ... m t-1 ya han sido elegidos. Luego, elija el número entero más pequeño m t de modo que se satisfagan ambas propiedades (1) y (2). La propiedad (1) requiere que m t ≠ b i - b j + m l para todo 1 ≤ i , j ≤ r y 1 ≤ l ≤ t -1. Por lo tanto, hay menos de tr 2 ≤ r 3 valores que m t debe evitar. Dado que m t se elige como mínimo, ( b t + m t ) ≤ ( b t -1 + m t -1 ) + r 3 . Esto implica la propiedad (3).
Por tanto, el croquis aproximado se calcula de la siguiente manera:
- Enmascare todos los bits excepto los del boceto con un AND bit a bit.
- Multiplica la clave por la constante predeterminada m . Esta operación en realidad requiere dos palabras de máquina, pero aún se puede realizar en tiempo constante.
- Enmascare todos excepto los trozos de bocetos desplazados. Estos están ahora contenidos en un bloque contiguo de como máximo r 4 < w 4/5 bits.
Comparación paralela
El propósito de la compresión lograda al dibujar es permitir que todas las claves se almacenen en una palabra de w bits. Deje que el boceto de nodo de un nodo sea la cadena de bits
- 1
sketch
( x 1 ) 1sketch
( x 2 ) ... 1sketch
( x k )
Podemos suponer que la función de croquis usa exactamente b ≤ r 4 bits. Entonces, cada bloque usa 1 + b ≤ w 4/5 bits, y dado que k ≤ w 1/5 , el número total de bits en el esquema de nodo es como máximo w .
Un breve aparte de la notación: para una cadena de bits sy un entero no negativo m , denotemos s m la concatenación de s a sí mismo m veces. Si t también es una cadena de bits, st denota la concatenación de t a s .
El boceto de nodo permite buscar las claves para cualquier entero de b bits y . Sea z = (0 y ) k , que se puede calcular en tiempo constante (multiplicar y por la constante (0 b 1) k ). Tenga en cuenta que 1 sketch
( x i ) - 0 y es siempre positivo, pero conserva su 1 inicial sif sketch
( x i ) ≥ y . Por lo tanto, podemos calcular el índice más pequeño i tal que sketch
( x i ) ≥ y de la siguiente manera:
- Reste z del boceto de nodo.
- Tome el AND bit a bit de la diferencia y la constante (10 b ) k . Esto borra todo menos el bit principal de cada bloque.
- Encuentre la parte más significativa del resultado.
- Calcule i , utilizando el hecho de que el bit inicial del i -ésimo bloque tiene el índice i ( b +1).
Esbozar
Para una consulta arbitraria q , la comparación paralela calcula el índice i tal que
sketch
( x i -1 ) ≤sketch
( q ) ≤sketch
( x i )
Desafortunadamente, la función de croquis no conserva el orden en general fuera del conjunto de claves, por lo que no es necesariamente el caso de que x i -1 ≤ q ≤ x i . Lo que es cierto es que, entre todas las claves, x i -1 o x i tiene el prefijo común más largo con q . Esto se debe a que cualquier clave y con un prefijo común más largo con q también tendría más bits de croquis en común con q , y por lo tanto sketch
( y ) estaría más cerca de sketch
( q ) que cualquier sketch
( x j ).
La longitud de prefijo más larga común entre dos w bits números enteros una y b se puede calcular en tiempo constante por encontrar el bit más significativo de la XOR bit a bit entre una y b . Esto se puede usar para enmascarar todos los prefijos comunes excepto el más largo.
Tenga en cuenta que p identifica exactamente dónde se ramifica q del conjunto de claves. Si el siguiente bit de q es 0, entonces el sucesor de q está contenido en el subárbol p 1, y si el siguiente bit de q es 1, entonces el predecesor de q está contenido en el subárbol p 0. Esto sugiere el siguiente algoritmo:
- Utilice la comparación paralela para encontrar el índice i tal que
sketch
( x i -1 ) ≤sketch
( q ) ≤sketch
( x i ). - Calcule el prefijo común p más largo de q y x i -1 o x i (tomando el más largo de los dos).
- Sea l -1 la longitud del prefijo común más largo p .
- Si el l -ésimo bit de q es 0, sea e = p 10 w - l . Utilice la comparación paralela para buscar el sucesor de
sketch
( e ). Este es el antecesor real de q . - Si el l -ésimo bit de q es 1, sea e = p 01 w - l . Utilice la comparación paralela para buscar el predecesor de
sketch
( e ). Este es el sucesor real de q .
- Si el l -ésimo bit de q es 0, sea e = p 10 w - l . Utilice la comparación paralela para buscar el sucesor de
- Una vez que se encuentra el predecesor o el sucesor de q, se determina la posición exacta de q entre el conjunto de claves.
Hash de fusión
Willard dio una aplicación de árboles de fusión a tablas hash , quien describe una estructura de datos para hash en la que una tabla hash de nivel externo con encadenamiento hash se combina con un árbol de fusión que representa cada cadena hash. En el encadenamiento hash, en una tabla hash con un factor de carga constante, el tamaño medio de una cadena es constante, pero además, con una alta probabilidad, todas las cadenas tienen un tamaño O (log n / log log n ) , donde n es el número de elementos hash . Este tamaño de cadena es lo suficientemente pequeño como para que un árbol de fusión pueda manejar búsquedas y actualizaciones dentro de él en un tiempo constante por operación. Por lo tanto, el tiempo para todas las operaciones en la estructura de datos es constante con alta probabilidad. Más precisamente, con esta estructura de datos, para cada probabilidad cuasipolinomial inversa p ( n ) = exp ((log n ) O (1) ) , hay una constante C tal que la probabilidad de que exista una operación que exceda el tiempo C es como máximo p ( n ) . [5]
Referencias
- ^ Fredman, ML ; Willard, DE (1990), "BLASTING Through the Information Theoretic Barrier with FUSION TREES", Actas del Vigésimo Segundo Simposio Anual de ACM sobre Teoría de la Computación (STOC '90) , Nueva York, NY, EE. UU.: ACM, págs. 1 –7, doi : 10.1145 / 100216.100217 , ISBN 0-89791-361-2.
- ^ Andersson, Arne; Miltersen, Peter Bro; Thorup, Mikkel (1999), "Los árboles de fusión se pueden implementar solo con instrucciones AC 0 ", Theoretical Computer Science , 215 (1–2): 337–344, doi : 10.1016 / S0304-3975 (98) 00172-8 , MR 1678804.
- ^ Raman, Rajeev (1996), "Colas prioritarias: pequeñas, monótonas y trans-dicotómicas", Cuarto Simposio Europeo Anual de Algoritmos (ESA '96), Barcelona, España, 25 al 27 de septiembre de 1996 , Lecture Notes in Computer Science, 1136 , Berlín: Springer-Verlag, págs. 121-137, doi : 10.1007 / 3-540-61680-2_51 , MR 1469229.
- ^ Andersson, Arne; Thorup, Mikkel (2007), "Conjuntos ordenados dinámicos con árboles de búsqueda exponenciales", Journal of the ACM , 54 (3): A13, arXiv : cs / 0210006 , doi : 10.1145 / 1236457.1236460 , MR 2314255.
- ^ Willard, Dan E. (2000), "Examinando geometría computacional, árboles de van Emde Boas y hash desde la perspectiva del árbol de fusión", SIAM Journal on Computing , 29 (3): 1030–1049, doi : 10.1137 / S0097539797322425 , Señor 1740562.
enlaces externos
- MIT CS 6.897: Estructuras de datos avanzadas: Clase 4, Árboles de fusión , Prof. Erik Demaine (primavera de 2003)
- MIT CS 6.897: Estructuras de datos avanzadas: Clase 5, Más árboles de fusión; estructuras de datos autoorganizadas, movimiento al frente, optimización estática , Prof. Erik Demaine (primavera de 2003)
- MIT CS 6.851: Estructuras de datos avanzadas: lección 13, notas del árbol de fusión , profesor Erik Demaine (primavera de 2007)
- MIT CS 6.851: Estructuras de datos avanzadas: lección 12, notas del árbol de fusión , profesor Erik Demaine (primavera de 2012)