En informática , un árbol de radix (también radix trie o árbol de prefijo compacto ) es una estructura de datos que representa un trie (árbol de prefijo) optimizado para el espacio en el que cada nodo que es el único hijo se fusiona con su padre. El resultado es que el número de hijos de cada nodo interno es a lo sumo la base r del árbol de la base, donde r es un número entero positivo y una potencia x de 2, teniendo x ≥ 1. A diferencia de los árboles normales, los bordes se pueden etiquetar con secuencias de elementos así como con elementos individuales. Esto hace que los árboles de radix sean mucho más eficientes para conjuntos pequeños (especialmente si las cadenas son largas) y para conjuntos de cadenas que comparten prefijos largos.
A diferencia de los árboles normales (donde las claves completas se comparan en masa desde su inicio hasta el punto de desigualdad), la clave en cada nodo se compara fragmento de bits por fragmento de bits, donde la cantidad de bits en ese fragmento es ese nodo es la base r de la base trie. Cuando r es 2, la base trie es binaria (es decir, compare la porción de 1 bit de la clave de ese nodo), lo que minimiza la dispersión a expensas de maximizar la profundidad de la trie, es decir, maximizar hasta la fusión de cadenas de bits no divergentes en el clave. Cuando r es una potencia entera de 2 que tiene r ≥ 4, entonces el trie de la raíz es un trie r -ary, lo que disminuye la profundidad del trie de la raíz a expensas de la escasez potencial.
Como optimización, las etiquetas de borde se pueden almacenar en tamaño constante usando dos punteros a una cadena (para el primer y último elemento). [1]
Tenga en cuenta que aunque los ejemplos de este artículo muestran cadenas como secuencias de caracteres, el tipo de elementos de cadena se puede elegir arbitrariamente; por ejemplo, como un bit o un byte de la representación de la cadena cuando se utilizan codificaciones de caracteres multibyte o Unicode .
Aplicaciones
Los árboles de radix son útiles para construir matrices asociativas con claves que se pueden expresar como cadenas. Encuentran una aplicación particular en el área de enrutamiento IP , [2] [3] [4] donde la capacidad de contener grandes rangos de valores con algunas excepciones es particularmente adecuada para la organización jerárquica de direcciones IP . [5] También se utilizan para índices invertidos de documentos de texto en la recuperación de información .
Operaciones
Los árboles de radix admiten operaciones de inserción, eliminación y búsqueda. La inserción agrega una nueva cadena al trie mientras intenta minimizar la cantidad de datos almacenados. La eliminación elimina una cadena del trie. Las operaciones de búsqueda incluyen (pero no se limitan necesariamente a) la búsqueda exacta, encontrar predecesor, encontrar sucesor y encontrar todas las cadenas con un prefijo. Todas estas operaciones son O ( k ) donde k es la longitud máxima de todas las cadenas en el conjunto, donde la longitud se mide en la cantidad de bits igual a la base de la base trie.
Buscar
La operación de búsqueda determina si existe una cadena en un trie. La mayoría de las operaciones modifican este enfoque de alguna manera para manejar sus tareas específicas. Por ejemplo, el nodo donde termina una cadena puede ser importante. Esta operación es similar a la de los intentos, excepto que algunos bordes consumen varios elementos.
El siguiente pseudocódigo asume que existen estas clases.
Borde
- Nodo targetNode
- etiqueta de cuerda
Nodo
- Matriz de aristas de bordes
- función isLeaf ()
búsqueda de función ( cadena x){ // Comenzar en la raíz sin elementos encontrados Node traverseNode: = root ; int elementsFound: = 0; // Recorrer hasta encontrar una hoja o no es posible continuar while (traverseNode! = Null &&! TraverseNode.isLeaf () && elementsFound) { // Obtener el siguiente borde para explorar en función de los elementos que aún no se han encontrado en x Edge nextEdge: = seleccionar borde de traverseNode.edges donde edge.label es un prefijo de x.suffix (elementsFound) // x.suffix (elementsFound) devuelve los últimos (x.length - elementsFound) elementos de x // ¿Se encontró una ventaja? si (nextEdge! = null ) { // Establecer el siguiente nodo para explorar traverseNode: = nextBorde.targetNode; // Incrementar los elementos encontrados en base a la etiqueta almacenada en el borde elementsFound + = nextBorde.label.length; } demás { // Termina el bucle traverseNode: = null ; } } // Se encuentra una coincidencia si llegamos a un nodo hoja y hemos usado exactamente x.length elementos return (traverseNode! = Null && traverseNode.isLeaf () && elementsFound == x.length);}
Inserción
Para insertar una cadena, buscamos en el árbol hasta que no podamos avanzar más. En este punto, agregamos un nuevo borde saliente etiquetado con todos los elementos restantes en la cadena de entrada, o si ya hay un borde saliente que comparte un prefijo con la cadena de entrada restante, lo dividimos en dos bordes (el primero etiquetado con el común prefijo) y continúe. Este paso de división asegura que ningún nodo tenga más hijos que los posibles elementos de cadena.
A continuación se muestran varios casos de inserción, aunque pueden existir más. Tenga en cuenta que r simplemente representa la raíz. Se supone que los bordes se pueden etiquetar con cadenas vacías para terminar cadenas donde sea necesario y que la raíz no tiene un borde entrante. (El algoritmo de búsqueda descrito anteriormente no funcionará cuando se utilizan bordes de cadena vacía).
Inserte 'agua' en la raíz
Inserte 'más lento' mientras mantiene 'lento'
Inserte 'prueba' que es un prefijo de 'tester'
Inserte 'equipo' mientras divide 'prueba' y crea una nueva etiqueta de borde 'st'
Inserte 'tostada' mientras divide 'te' y mueve las cuerdas anteriores un nivel más bajo
Supresión
Para eliminar una cadena x de un árbol, primero ubicamos la hoja que representa x. Luego, asumiendo que x existe, eliminamos el nodo hoja correspondiente. Si el padre de nuestro nodo hoja solo tiene otro hijo, entonces la etiqueta entrante de ese hijo se agrega a la etiqueta entrante del padre y el hijo se elimina.
Operaciones adicionales
- Buscar todas las cadenas con prefijo común: devuelve una matriz de cadenas que comienzan con el mismo prefijo.
- Buscar predecesor: ubica la cadena más grande menor que una cadena dada, por orden lexicográfico.
- Buscar sucesor: ubica la cadena más pequeña mayor que una cadena dada, por orden lexicográfico.
Historia
Donald R. Morrison describió por primera vez lo que Donald Knuth , páginas 498-500 en el Volumen III de The Art of Computer Programming , llama "árboles de Patricia" en 1968. [6] Gernot Gwehenberger inventó y describió independientemente la estructura de datos aproximadamente al mismo tiempo. [7] Los árboles PATRICIA son árboles de radix con radix igual a 2, lo que significa que cada bit de la clave se compara individualmente y cada nodo es una rama de dos vías (es decir, izquierda versus derecha).
Comparación con otras estructuras de datos
(En las siguientes comparaciones, se supone que las claves tienen una longitud k y la estructura de datos contiene n miembros).
A diferencia de los árboles equilibrados , los árboles de base permiten la búsqueda, inserción y eliminación en tiempo O ( k ) en lugar de O (log n ). Esto no parece una ventaja, ya que normalmente k ≥ log n , pero en un árbol balanceado cada comparación es una comparación de cadenas que requiere O ( k ) tiempo en el peor de los casos, muchos de los cuales son lentos en la práctica debido a los largos prefijos comunes (en el caso donde las comparaciones comienzan al comienzo de la cadena). En un intento, todas las comparaciones requieren un tiempo constante, pero se necesitan m comparaciones para buscar una cadena de longitud m . Los árboles de radix pueden realizar estas operaciones con menos comparaciones y requieren muchos menos nodos.
Sin embargo, los árboles de radix también comparten las desventajas de los intentos: como solo se pueden aplicar a cadenas de elementos o elementos con un mapeo de cadenas reversible de manera eficiente, carecen de la generalidad completa de los árboles de búsqueda equilibrados, que se aplican a cualquier tipo de datos con un total ordenar . Se puede usar un mapeo reversible a cadenas para producir el orden total requerido para árboles de búsqueda balanceados, pero no al revés. Esto también puede ser problemático si un tipo de datos solo proporciona una operación de comparación, pero no una operación de (des) serialización .
Se dice comúnmente que las tablas hash tienen tiempos de inserción y eliminación O (1) esperados, pero esto solo es cierto cuando se considera que el cálculo del hash de la clave es una operación de tiempo constante. Cuando se tiene en cuenta el hash de la clave, las tablas hash tienen tiempos esperados de inserción y eliminación de O ( k ), pero pueden llevar más tiempo en el peor de los casos, dependiendo de cómo se manejen las colisiones. Los árboles de radix tienen inserción y eliminación de O ( k ) en el peor de los casos . Las operaciones sucesoras / predecesoras de los árboles de base tampoco se implementan mediante tablas hash.
Variantes
Una extensión común de árboles de radix usa dos colores de nodos, 'negro' y 'blanco'. Para comprobar si una cadena determinada está almacenada en el árbol, la búsqueda comienza desde la parte superior y sigue los bordes de la cadena de entrada hasta que no se puede avanzar más. Si se consume la cadena de búsqueda y el nodo final es un nodo negro, la búsqueda ha fallado; si es blanco, la búsqueda se ha realizado correctamente. Esto nos permite agregar una amplia gama de cadenas con un prefijo común al árbol, usando nodos blancos, luego eliminar un pequeño conjunto de "excepciones" de una manera eficiente en el espacio insertándolos usando nodos negros.
El HAT-trie es una estructura de datos consciente de la caché basada en árboles de radix que ofrece un almacenamiento y una recuperación de cadenas eficientes e iteraciones ordenadas. El rendimiento, con respecto al tiempo y al espacio, es comparable a la tabla hash consciente de la memoria caché . [8] [9] Véanse las notas de implementación de la prueba HAT en [1]
Un trie PATRICIA es una variante especial del trie radix 2 (binario), en el que en lugar de almacenar explícitamente cada bit de cada clave, los nodos almacenan solo la posición del primer bit que diferencia dos subárboles. Durante el recorrido, el algoritmo examina el bit indexado de la clave de búsqueda y elige el subárbol izquierdo o derecho según corresponda. Las características notables del trie PATRICIA incluyen que el trie solo requiere que se inserte un nodo por cada clave única almacenada, lo que hace que PATRICIA sea mucho más compacta que un trie binario estándar. Además, dado que las claves reales ya no se almacenan explícitamente, es necesario realizar una comparación de claves completa en el registro indexado para confirmar una coincidencia. A este respecto, PATRICIA tiene cierto parecido con la indexación mediante una tabla hash. [10]
El árbol de la base adaptativa es una variante del árbol de la base que integra los tamaños de los nodos adaptativos al árbol de la base. Un gran inconveniente de los árboles de base habituales es el uso del espacio, ya que utiliza un tamaño de nodo constante en todos los niveles. La principal diferencia entre el árbol de la base y el árbol de la base adaptativa es su tamaño variable para cada nodo en función del número de elementos secundarios, que crece al agregar nuevas entradas. Por lo tanto, el árbol de radix adaptativo conduce a un mejor uso del espacio sin reducir su velocidad. [11] [12] [13]
Una práctica común es relajar el criterio de no permitir a los padres con un solo hijo en situaciones en las que el padre representa una clave válida en el conjunto de datos. Esta variante de árbol de radix logra una mayor eficiencia espacial que la que solo permite nodos internos con al menos dos hijos. [14]
Ver también
- Árbol de prefijos (también conocido como Trie)
- Autómata de estado finito acíclico determinista (DAFSA)
- Intentos de búsqueda ternaria
- Hachís trie
- Autómatas finitos deterministas
- Matriz de Judy
- Algoritmo de búsqueda
- Hash extensible
- Matriz hash mapeada trie
- Prefijo árbol hash
- Burstsort
- Algoritmo de Luleå
- Codificación Huffman
Referencias
- ^ Morin, Patrick. "Estructuras de datos para cadenas" (PDF) . Consultado el 15 de abril de 2012 .
- ^ "rtfree (9)" . www.freebsd.org . Consultado el 23 de octubre de 2016 .
- ^ Los regentes de la Universidad de California (1993). "/sys/net/radix.c" . Referencia cruzada BSD . NetBSD . Consultado el 25 de julio de 2019 .
Rutinas para construir y mantener árboles de radix para búsquedas de enrutamiento.
- ^ "Árboles Radix / Patricia sin cerrojo, atómicos y genéricos" . NetBSD . 2011.
- ^ Knizhnik, Konstantin. "Patricia Tries: Un mejor índice para búsquedas de prefijos" , Dr. Dobb's Journal , junio de 2008.
- ^ Morrison, Donald R. PATRICIA - Algoritmo práctico para recuperar información codificada en alfanumérico
- ^ G. Gwehenberger, Anwendung einer binären Verweiskettenmethode beim Aufbau von Listen. Elektronische Rechenanlagen 10 (1968), págs. 223–226
- ^ Askitis, Nikolas; Sinha, Ranjan (2007). HAT-trie: Una estructura de datos basada en Trie consciente de la caché para cadenas . Actas de la 30ª Conferencia Australasia sobre Ciencias de la Computación . 62 . págs. 97-105. ISBN 1-920682-43-0.
- ^ Askitis, Nikolas; Sinha, Ranjan (octubre de 2010). "Ingeniería escalable, caché y eficientes intentos de espacio para cadenas". El diario VLDB . 19 (5): 633–660. doi : 10.1007 / s00778-010-0183-9 .
- ^ Morrison, Donald R. Algoritmo práctico para recuperar información codificada en alfanumérico
- ^ Kemper, Alfons; Eickler, André (2013). Datenbanksysteme, Eine Einführung . 9 . págs. 604–605. ISBN 978-3-486-72139-3.
- ^ "armon / libart: Adaptive Radix Trees implementado en C" . GitHub . Consultado el 17 de septiembre de 2014 .
- ^ http://www-db.in.tum.de/~leis/papers/ART.pdf
- ^ ¿Puede un nodo del árbol Radix que representa una clave válida tener un hijo?
enlaces externos
- Material de investigación y referencia sobre algoritmos y estructuras de datos: PATRICIA , por Lloyd Allison, Universidad de Monash
- Patricia Tree , Diccionario de algoritmos y estructuras de datos del NIST
- Árboles de bits críticos , por Daniel J. Bernstein
- API Radix Tree en el kernel de Linux , por Jonathan Corbet
- Kart (árbol de radix de alteración clave) , por Paul Jarc
- Adaptive Radix Tree: Indexación ARTful para bases de datos de memoria principal , por Viktor Leis, Alfons Kemper, Thomas Neumann, Universidad Técnica de Munich
Implementaciones
- Implementación de FreeBSD , utilizada para paginación, reenvío y otras cosas.
- Implementación del Kernel de Linux , utilizado para la caché de la página, entre otras cosas.
- La biblioteca estándar GNU C ++ tiene una implementación trie
- Implementación Java de Concurrent Radix Tree , por Niall Gallagher
- Implementación en C # de un árbol Radix
- Biblioteca de plantillas de algoritmos prácticos , una biblioteca de C ++ sobre PATRICIA intenta (VC ++> = 2003, GCC G ++ 3.x), por Roman S. Klyujkov
- Implementación de la clase de plantilla Patricia Trie C ++ , por Radu Gruian
- Implementación de la biblioteca estándar de Haskell "basada en árboles patricia big-endian". Código fuente navegable en la web .
- Implementación de Patricia Trie en Java , por Roger Kapsi y Sam Berlin
- Árboles de bits críticos bifurcados a partir del código C por Daniel J. Bernstein
- Implementación de Patricia Trie en C , en libcprops
- Patricia Trees: conjuntos y mapas eficientes sobre enteros en OCaml , por Jean-Christophe Filliâtre
- Implementación de Radix DB (Patricia trie) en C , por GB Versiani
- Libart - Adaptive Radix Trees implementado en C , por Armon Dadgar con otros colaboradores (código abierto, licencia BSD de 3 cláusulas)
- Implementación nim de un árbol de bits críticos
- rax , una implementación de árbol de radix en ANSI C por Salvatore Sanfilippo (el creador de REDIS )