En informática , un trie , también llamado árbol digital o árbol de prefijos , es un tipo de árbol de búsqueda , una estructura de datos de árbol utilizada para localizar claves específicas dentro de un conjunto. Estas claves suelen ser cadenas , con enlaces entre nodos definidos no por la clave completa, sino por caracteres individuales . Para acceder a una clave (para recuperar su valor, cambiarla o eliminarla), el trie se atraviesa primero en profundidad , siguiendo los enlaces entre los nodos, que representan cada carácter de la clave.
A diferencia de un árbol de búsqueda binario , los nodos del trie no almacenan su clave asociada. En cambio, la posición de un nodo en el trie define la clave con la que está asociado. Esto distribuye el valor de cada clave en la estructura de datos y significa que no todos los nodos tienen necesariamente una clave asociada.
Todos los hijos de un nodo tienen un prefijo común de la cadena asociada con ese nodo principal, y la raíz está asociada con la cadena vacía . Esta tarea de almacenar datos accesibles por su prefijo se puede lograr de una manera optimizada para la memoria empleando un árbol de base .
Aunque los intentos pueden estar codificados por cadenas de caracteres, no es necesario que lo estén. Los mismos algoritmos se pueden adaptar para listas ordenadas de cualquier tipo subyacente, por ejemplo, permutaciones de dígitos o formas. En particular, un trie bit a bit se codifica en los bits individuales que componen una pieza de datos binarios de longitud fija, como un número entero o una dirección de memoria .
Historia, etimología y pronunciación
La idea de un trie para representar un conjunto de cadenas fue descrita por primera vez de forma abstracta por Axel Thue en 1912. [1] [2] Los tries fueron descritos por primera vez en un contexto informático por René de la Briandais en 1959. [3] [4] [ 2] la idea fue descrito independientemente en 1960 por Edward Fredkin , [5] que acuñó el término trie , pronunciándolo / t r i / (como "árbol"), después de la sílaba medio de recuperación . [6] [7] Sin embargo, otros autores lo pronuncian / t r aɪ / (como "tratar"), en un intento de distinguir verbalmente de "árbol". [6] [7] [2]
Aplicaciones
Representación de diccionario
Las aplicaciones comunes de los intentos incluyen almacenar un texto predictivo o un diccionario autocompletado e implementar algoritmos de coincidencia aproximada, [8] como los que se usan en el software de revisión ortográfica y separación de palabras [7] . Estas aplicaciones aprovechan la capacidad de un ensayo para buscar, insertar y eliminar entradas rápidamente. Sin embargo, si almacenar palabras de diccionario es todo lo que se requiere (es decir, no hay necesidad de almacenar metadatos asociados con cada palabra), un autómata de estado finito acíclico determinista mínimo (DAFSA) o árbol de base utilizaría menos espacio de almacenamiento que un trie. Esto se debe a que los DAFSA y los árboles de base pueden comprimir ramas idénticas del trie que corresponden a los mismos sufijos (o partes) de diferentes palabras que se almacenan.
Reemplazo de otras estructuras de datos
Reemplazo para tablas hash
Se puede usar un trie para reemplazar una tabla hash , sobre la cual tiene las siguientes ventajas:
- Buscar datos en un trie es más rápido en el peor de los casos, tiempo O (m) (donde m es la longitud de una cadena de búsqueda), en comparación con una tabla hash imperfecta. Una tabla hash imperfecta puede tener colisiones de claves. Una colisión de claves es la asignación de la función hash de diferentes claves a la misma posición en una tabla hash. La velocidad de búsqueda en el peor de los casos en una tabla hash imperfecta es el tiempo O (N) , pero mucho más típicamente es O (1), con O (m) tiempo dedicado a evaluar el hash.
- No hay colisiones de diferentes teclas en un intento.
- Los depósitos en un trie, que son análogos a los depósitos de la tabla hash que almacenan colisiones de claves, son necesarios solo si una sola clave está asociada con más de un valor.
- No es necesario proporcionar una función hash o cambiar las funciones hash a medida que se agregan más claves a un trie.
- Un trie puede proporcionar un orden alfabético de las entradas por clave.
Sin embargo, un trie también tiene algunos inconvenientes en comparación con una tabla hash:
- La búsqueda de Trie puede ser más lenta que la búsqueda de tablas hash, especialmente si se accede directamente a los datos en una unidad de disco duro o en algún otro dispositivo de almacenamiento secundario donde el tiempo de acceso aleatorio es alto en comparación con la memoria principal. [5]
- Algunas claves, como los números de coma flotante, pueden generar cadenas largas y prefijos que no son particularmente significativos. Sin embargo, un trie bit a bit puede manejar números de coma flotante de formato simple y doble IEEE estándar. [ cita requerida ]
- Algunos intentos pueden requerir más espacio que una tabla hash, ya que se puede asignar memoria para cada carácter en la cadena de búsqueda, en lugar de una sola porción de memoria para toda la entrada, como en la mayoría de las tablas hash.
Representación DFSA
Un trie puede verse como un autómata finito determinista en forma de árbol . Cada lenguaje finito es generado por un autómata trie, y cada trie puede comprimirse en un autómata de estado finito acíclico determinista .
Algoritmos
El trie es un árbol de nodos que admite operaciones de búsqueda e inserción. Find devuelve el valor de una cadena de clave e Insert inserta una cadena (la clave) y un valor en el trie. Tanto Insertar como Buscar se ejecutan en tiempo O ( m ) , donde m es la longitud de la clave.
Se puede usar una clase de nodo simple para representar nodos en el trie:
class Node : def __init__ ( self ) -> None : # Tenga en cuenta que el uso de un diccionario para niños (como en esta implementación) # no clasificaría lexicográficamente a los niños por defecto, que es # requerido por la clasificación lexicográfica en la sección Ordenación. # Para la clasificación lexicográfica, podemos usar una matriz de nodos. yo . children : Dict [ str , Node ] = {} # mapeo del personaje al Nodo self . valor : Opcional [ Cualquiera ] = Ninguno
Tenga en cuenta que children
es un diccionario de caracteres para los hijos de un nodo; y se dice que un nodo "terminal" es aquel que representa una cadena completa.
El valor de un trie se puede buscar de la siguiente manera:
def buscar ( nodo : nodo , clave : str ) -> Opcional [ Cualquiera ]: "" "Buscar valor por clave en el nodo." "" para char en clave : si char en nodo . hijos : nodo = nodo . children [ char ] else : return None return node . valor
Se pueden utilizar ligeras modificaciones de esta rutina.
- para comprobar si hay alguna palabra en el trie que comience con un prefijo determinado (ver § Autocompletar ), y
- para devolver el nodo más profundo correspondiente a algún prefijo de una cadena dada.
La inserción procede recorriendo el trie de acuerdo con la cadena que se va a insertar, luego agregando nuevos nodos para el sufijo de la cadena que no está contenido en el trie:
def insert ( nodo : Nodo , clave : str , valor : Cualquiera ) -> Ninguno : "" "Inserte el par clave / valor en el nodo." "" para char en clave : si char no en nodo . hijos : nodo . hijos [ char ] = nodo () nodo = nodo . nodo de niños [ char ] . valor = valor
La eliminación de una clave se puede hacer de forma perezosa (borrando solo el valor dentro del nodo correspondiente a una clave), o con entusiasmo limpiando cualquier nodo principal que ya no sea necesario. La eliminación ansiosa se describe en el pseudocódigo aquí: [9]
def delete ( root : Node , key : str ) -> bool : "" "Elimina ansiosamente la clave del trie enraizado en` root`. Devuelve si el trie enraizado en `root` ahora está vacío. " "" def _delete ( nodo : Nodo , clave : str , d : int ) -> bool : "" "Limpia el nodo correspondiente a la clave [d], y elimina la clave secundaria [d + 1] si esa subtrie está completamente vacía, y devuelve si `nodo` ha sido borrado. " "" if d == len ( clave ): nodo . valor = Ninguno más : c = clave [ d ] si c en el nodo . hijos y _delete ( nodo . hijos [ c ], clave , d + 1 ): del nodo . children [ c ] # Devuelve si la subtrie enraizada en `node` ahora está completamente vacía return node . el valor es Ninguno y len ( nodo . hijos ) == 0 return _delete ( raíz , clave , 0 )
Autocompletar
Los intentos se pueden utilizar para devolver una lista de claves con un prefijo determinado. Esto también se puede modificar para permitir comodines en la búsqueda de prefijo. [9]
def keys_with_prefix ( root : Node , prefix : str ) -> List [ str ]: resultados : List [ str ] = [] x = _get_node ( root , prefix ) _collect ( x , list ( prefix ), results ) devuelve resultadosdef _collect ( x : Opcional [ Nodo ], prefijo : Lista [ str ], resultados : Lista [ str ]) -> Ninguno : "" " Agregar claves debajo del nodo` x` que coincida con el prefijo dado con `resultados`. prefijo: lista de caracteres "" " si x es Ninguno : devuelve si x . el valor no es None : prefix_str = '' . unirse ( prefijo ) resultados . añadir ( prefix_str ) para c en x . niños : prefijo . append ( c ) _collect ( x . children [ c ], prefix , results ) del prefix [ - 1 ] # eliminar el último carácter def _get_node ( nodo : Nodo , clave : str ) -> Opcional [ Nodo ]: "" " Buscar nodo por clave. Es lo mismo que la función` buscar` definida anteriormente, pero devuelve el nodo encontrado en sí en lugar del nodo encontrado. valor. "" " para char en la clave : si char en el nodo . hijos : nodo = nodo . niños [ char ] else : return None return node
Clasificación
La clasificación lexicográfica de un conjunto de claves se puede lograr construyendo un trie a partir de ellas, con los hijos de cada nodo ordenados lexicográficamente y atravesándolo en preorden , imprimiendo cualquier valor en los nodos interiores o en los nodos hoja. [10] Este algoritmo es una forma de ordenación por base . [11]
Un trie es la estructura de datos fundamental de Burstsort , que (en 2007) fue el algoritmo de clasificación de cadenas más rápido conocido debido a su uso eficiente de la caché . [12] Ahora hay otros más rápidos. [13]
Búsqueda de texto completo
Se puede usar un tipo especial de trie, llamado árbol de sufijos , para indexar todos los sufijos en un texto con el fin de realizar búsquedas rápidas de texto completo.
Estrategias de implementación
Hay varias formas de representar los intentos, correspondientes a diferentes compensaciones entre el uso de la memoria y la velocidad de las operaciones. La forma básica es la de un conjunto vinculado de nodos, donde cada nodo contiene una matriz de punteros secundarios, uno para cada símbolo en el alfabeto (por lo tanto, para el alfabeto inglés , uno almacenaría 26 punteros secundarios y para el alfabeto de bytes, 256 punteros). Esto es simple pero derrochador en términos de memoria: usando el alfabeto de bytes (tamaño 256) y punteros de cuatro bytes, cada nodo requiere un kilobyte de almacenamiento, y cuando hay poca superposición en los prefijos de las cadenas, el número de nodos requeridos es aproximadamente la longitud combinada de las cadenas almacenadas. [4] : 341 Dicho de otra manera, los nodos cerca de la parte inferior del árbol tienden a tener pocos hijos y hay muchos de ellos, por lo que la estructura desperdicia espacio almacenando punteros nulos. [14]
El problema de almacenamiento puede aliviarse mediante una técnica de implementación denominada reducción alfabética , mediante la cual las cadenas originales se reinterpretan como cadenas más largas sobre un alfabeto más pequeño. Por ejemplo, una cadena de n bytes puede considerarse alternativamente como una cadena de 2 n unidades de cuatro bits y almacenarse en un trie con dieciséis punteros por nodo. Las búsquedas deben visitar el doble de nodos en el peor de los casos, pero los requisitos de almacenamiento se reducen en un factor de ocho. [4] : 347–352
Una implementación alternativa representa un nodo como un triple (símbolo, hijo, siguiente) y vincula a los hijos de un nodo como una lista enlazada individualmente : child apunta al primer hijo del nodo, junto al siguiente hijo del nodo padre. [14] [15] El conjunto de hijos también se puede representar como un árbol de búsqueda binario ; un ejemplo de esta idea es el árbol de búsqueda ternario desarrollado por Bentley y Sedgewick . [4] : 353
Otra alternativa para evitar el uso de una matriz de 256 punteros (ASCII), como se sugirió anteriormente, es almacenar la matriz alfabética como un mapa de bits de 256 bits que representa el alfabeto ASCII, reduciendo drásticamente el tamaño de los nodos. [dieciséis]
Intentos bit a bit
Los intentos bit a bit son muy parecidos a un trie normal basado en caracteres, excepto que los bits individuales se utilizan para atravesar lo que efectivamente se convierte en una forma de árbol binario. Generalmente, las implementaciones utilizan una instrucción de CPU especial para encontrar muy rápidamente el primer bit establecido en una clave de longitud fija (por ejemplo, la __builtin_clz()
intrínseca de GCC ). Este valor se usa luego para indexar una tabla de 32 o 64 entradas que apunta al primer elemento en el ensayo bit a bit con ese número de bits cero a la izquierda. La búsqueda prosigue probando cada bit subsiguiente en la clave y eligiendo child[0]
o child[1]
apropiadamente hasta que se encuentra el elemento.
Aunque este proceso puede parecer lento, es muy local en caché y altamente paralelizable debido a la falta de dependencias de registro y, por lo tanto, tiene un rendimiento excelente en CPU modernas de ejecución fuera de orden . Un árbol rojo-negro, por ejemplo, se desempeña mucho mejor en papel, pero es muy poco amigable con el caché y causa múltiples bloqueos de canalización y TLB en las CPU modernas, lo que hace que ese algoritmo esté limitado por la latencia de la memoria en lugar de la velocidad de la CPU. En comparación, un trie bit a bit rara vez accede a la memoria, y cuando lo hace, lo hace solo para leer, evitando así la sobrecarga de coherencia de la caché SMP. Por lo tanto, se está convirtiendo cada vez más en el algoritmo de elección para el código que realiza muchas inserciones y eliminaciones rápidas, como asignadores de memoria (por ejemplo, versiones recientes del famoso asignador de Doug Lea (dlmalloc) y sus descendientes ). El peor caso de los pasos de búsqueda es el mismo que el de los bits que se utilizan para indexar bins en el árbol. [17]
Alternativamente, el término "trie bit a bit" puede referirse más generalmente a una estructura de árbol binario que contiene valores enteros, ordenándolos por su prefijo binario. Un ejemplo es el trie x-fast .
Comprimir intentos
Comprimir el trie y fusionar las ramas comunes a veces puede producir grandes ganancias de rendimiento. Esto funciona mejor en las siguientes condiciones:
- El trie es (en su mayoría) estático, por lo que no se requieren inserciones o eliminaciones de claves (por ejemplo, después de la creación masiva del trie).
- Solo se necesitan búsquedas.
- Los nodos de prueba no están codificados por datos específicos del nodo, o los datos de los nodos son comunes. [18]
- El conjunto total de claves almacenadas es muy escaso dentro de su espacio de representación (por lo que la compresión vale la pena).
Por ejemplo, puede usarse para representar conjuntos de bits dispersos ; es decir, subconjuntos de un conjunto enumerable fijo mucho más grande. En tal caso, el trie está codificado por la posición del elemento de bit dentro del conjunto completo. La clave se crea a partir de la cadena de bits necesarios para codificar la posición integral de cada elemento. Tales intentos tienen una forma muy degenerada con muchas ramas faltantes. Después de detectar la repetición de patrones comunes o llenar los huecos no utilizados, los nodos de hoja únicos (cadenas de bits) se pueden almacenar y comprimir fácilmente, reduciendo el tamaño total del trie.
Esta compresión también se utiliza en la implementación de las diversas tablas de búsqueda rápida para recuperar las propiedades de los caracteres Unicode . Estos podrían incluir tablas de mapeo de casos (por ejemplo, para la letra griega pi , de Π a π), o tablas de búsqueda que normalizan la combinación de caracteres base y combinados (como a- umlaut en alemán , ä, o dalet - patah - dagesh - ole en hebreo bíblico , דַּ֫ ). Para tales aplicaciones, la representación es similar a transformar una tabla muy grande, unidimensional y dispersa (por ejemplo, puntos de código Unicode) en una matriz multidimensional de sus combinaciones, y luego usar las coordenadas en la hipermatriz como la clave de cadena de un código sin comprimir. intente representar el carácter resultante. La compresión consistirá en detectar y fusionar las columnas comunes dentro de la hipermatriz para comprimir la última dimensión de la clave. Por ejemplo, para evitar almacenar el punto de código Unicode multibyte completo de cada elemento que forma una columna de matriz, se pueden aprovechar las agrupaciones de puntos de código similares. Cada dimensión de la hipermatriz almacena la posición inicial de la siguiente dimensión, de modo que solo es necesario almacenar el desplazamiento (normalmente un solo byte). El vector resultante es en sí mismo comprimible cuando también es escaso, por lo que cada dimensión (asociada a un nivel de capa en el trie) se puede comprimir por separado.
Algunas implementaciones admiten dicha compresión de datos dentro de intentos dispersos dinámicos y permiten inserciones y eliminaciones en intentos comprimidos. Sin embargo, esto generalmente tiene un costo significativo cuando los segmentos comprimidos deben dividirse o fusionarse. Se debe hacer una compensación entre la compresión de datos y la velocidad de actualización. Una estrategia típica es limitar el rango de búsquedas globales para comparar las ramas comunes en el trie disperso. [ cita requerida ]
El resultado de dicha compresión puede parecer similar a intentar transformar el trie en un gráfico acíclico dirigido (DAG), porque la transformación inversa de un DAG a un trie es obvia y siempre posible. Sin embargo, la forma del DAG está determinada por la forma de la clave elegida para indexar los nodos, lo que a su vez restringe la posible compresión.
Otra estrategia de compresión es "desentrañar" la estructura de datos en una matriz de un solo byte. [19] Este enfoque elimina la necesidad de punteros de nodo, lo que reduce sustancialmente los requisitos de memoria. Esto, a su vez, permite la asignación de memoria y el uso de memoria virtual para cargar de manera eficiente los datos del disco.
Un enfoque más es "empacar" el trie. [7] Liang describe una implementación eficiente en el espacio de un trie empaquetado disperso aplicado a la separación automática de palabras , en la que los descendientes de cada nodo pueden estar intercalados en la memoria.
Intentos de memoria externa
Varias variantes de trie son adecuadas para mantener conjuntos de cadenas en la memoria externa , incluidos los árboles de sufijos. También se ha sugerido para esta tarea una combinación de trie y árbol B , denominada B-trie ; en comparación con los árboles de sufijos, están limitados en las operaciones admitidas, pero también son más compactos, mientras realizan operaciones de actualización más rápido. [20]
Ver también
- Árbol de sufijo
- Árbol de radix
- Gráfico de palabras acíclicas dirigidas (también conocido como DAWG)
- Autómatas finitos deterministas acíclicos
- Hachís trie
- Autómatas finitos deterministas
- Matriz de Judy
- Algoritmo de búsqueda
- Hash extensible
- Matriz de hash mapeado trie
- Árbol de hash de prefijo
- Burstsort
- Algoritmo de Luleå
- Codificación de Huffman
- Ctrie
- HAT-trie
Referencias
- ↑ Thue, Axel (1912). "Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen" . Skrifter udgivne af Videnskabs-Selskabet i Christiania . 1912 (1): 1-67. Citado por Knuth.
- ^ a b c Knuth, Donald (1997). "6.3: Búsqueda digital". El arte de la programación informática Volumen 3: Clasificación y búsqueda (2ª ed.). Addison-Wesley. pag. 492. ISBN 0-201-89685-0.
- ^ de la Briandais, René (1959). Búsqueda de archivos mediante teclas de longitud variable (PDF) . Proc. Western J. Computer Conf. págs. 295-298. Archivado desde el original (PDF) el 2020-02-11. Citado por Brass y por Knuth.
- ^ a b c d Latón, Peter (2008). Estructuras de datos avanzadas . Prensa de la Universidad de Cambridge. pag. 336.
- ^ a b Edward Fredkin (1960). "Trie Memory". Comunicaciones de la ACM . 3 (9): 490–499. doi : 10.1145 / 367390.367400 .
- ^ a b Black, Paul E. (16 de noviembre de 2009). "trie" . Diccionario de algoritmos y estructuras de datos . Instituto Nacional de Estándares y Tecnología . Archivado desde el original el 29 de abril de 2011.
- ^ a b c d Franklin Mark Liang (1983). Word Hy-phen-a-ción Por Com-put-er (PDF) (Tesis de Doctorado en Filosofía). Universidad Stanford. Archivado (PDF) desde el original el 11 de noviembre de 2005 . Consultado el 28 de marzo de 2010 .
- ^ Aho, Alfred V .; Corasick, Margaret J. (junio de 1975). "Coincidencia de cadenas eficiente: una ayuda para la búsqueda bibliográfica" (PDF) . Comunicaciones de la ACM . 18 (6): 333–340. doi : 10.1145 / 360825.360855 .
- ^ a b Sedgewick, Robert; Wayne, Kevin (12 de junio de 2020). "Intenta" . algs4.cs.princeton.edu . Consultado el 11 de agosto de 2020 .
- ^ Kärkkäinen, Juha. "Conferencia 2" (PDF) . Universidad de Helsinki .
El preorden de los nodos en un trie es el mismo que el orden lexicográfico de las cadenas que representan, asumiendo que los hijos de un nodo están ordenados por las etiquetas de los bordes.
- ^ Kallis, Rafael (2018). "El árbol de la raíz adaptable (Informe n. ° 14-708-887)" (PDF) . Universidad de Zurich: Departamento de Informática, Publicaciones de investigación .
- ^ Ranjan Sinha y Justin Zobel y David Ring (febrero de 2006). "Clasificación de cadenas con uso de caché eficaz mediante copia" (PDF) . Revista ACM de algoritmos experimentales . 11 : 1–32. doi : 10.1145 / 1187436.1187439 .
- ^ J. Kärkkäinen y T. Rantala (2008). "Engineering Radix Sort for Strings". En A. Amir y A. Turpin y A. Moffat (ed.). Procesamiento de cadenas y recuperación de información, Proc. SPIRE . Apuntes de conferencias en informática. 5280 . Saltador. págs. 3-14. doi : 10.1007 / 978-3-540-89097-3_3 .
- ^ a b Allison, Lloyd. "Intenta" . Consultado el 18 de febrero de 2014 .
- ^ Sahni, Sartaj. "Intenta" . Estructuras de datos, algoritmos y aplicaciones en Java . Universidad de Florida . Consultado el 18 de febrero de 2014 .
- ^ Bellekens, Xavier (2014). "Un esquema de compresión de memoria altamente eficiente para sistemas de detección de intrusiones acelerados por GPU". Actas de la VII Conferencia Internacional sobre Seguridad de la Información y las Redes - SIN '14 . Glasgow, Escocia, Reino Unido: ACM. págs. 302: 302–302: 309. arXiv : 1704.02272 . doi : 10.1145 / 2659651.2659723 . ISBN 978-1-4503-3033-6.
- ^ Lee, Doug. "Un asignador de memoria" . Consultado el 1 de diciembre de 2019 . HTTP para el código fuente . Binary Trie se describe en la Versión 2.8.6, Sección "Estructuras de datos superpuestas", Estructura "malloc_tree_chunk".
- ^ Jan Daciuk; Stoyan Mihov; Bruce W. Watson; Richard E. Watson (2000). "Construcción incremental de autómatas de estado finito acíclicos mínimos" . Lingüística computacional . Asociación de Lingüística Computacional. 26 : 3-16. arXiv : cs / 0007009 . doi : 10.1162 / 089120100561601 . Archivado desde el original el 30 de septiembre de 2011 . Consultado el 28 de mayo de 2009 .
Este artículo presenta un método para la construcción directa de un autómata de estados finitos acíclicos mínimos que reconoce una lista finita dada de palabras en orden lexicográfico. Nuestro enfoque es construir un autómata mínimo en una sola fase agregando nuevas cadenas una por una y minimizando el autómata resultante sobre la marcha.
URL alternativa - ^ Ulrich Germann; Eric Joanis; Samuel Larkin (2009). "Intentos muy compactos: cómo colocar modelos grandes en la memoria y hacer que también se carguen rápido" (PDF) . Talleres de ACL: Actas del taller sobre ingeniería de software, pruebas y garantía de calidad para el procesamiento del lenguaje natural . Asociación de Lingüística Computacional. págs. 31–39.
Presentamos Tightly Packed Tries (TPT), una implementación compacta de estructuras trie comprimidas de solo lectura con paginación rápida bajo demanda y tiempos de carga cortos. Demostramos los beneficios de los TPT para almacenar modelos de lenguaje de retroceso de n-gramas y tablas de frases para la traducción automática estadística . Codificadas como TPT, estas bases de datos requieren menos espacio que las representaciones de archivos de texto plano de los mismos datos comprimidos con la utilidad gzip. Al mismo tiempo, se pueden mapear en memoria rápidamente y buscar directamente en el tiempo lineal en la longitud de la clave, sin la necesidad de descomprimir todo el archivo. La sobrecarga para la descompresión local durante la búsqueda es marginal.
- ^ Askitis, Nikolas; Zobel, Justin (2008). "B-tries para la gestión de cadenas basada en disco" (PDF) . Revista VLDB : 1–26. ISSN 1066-8888 .
enlaces externos
- Diccionario de NIST de algoritmos y estructuras de datos: Trie