En informática, un trie ( / ˈtraɪ / , / ˈtriː / ), también llamado árbol digital o árbol de prefijos , [ 1] es un tipo de árbol de búsqueda : específicamente, una estructura de datos de árbol k-ario 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, cambiarlo o eliminarlo), se recorre el trie en profundidad , siguiendo los enlaces entre nodos, que representan cada carácter en 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 un valor asociado.
Todos los hijos de un nodo tienen un prefijo común de la cadena asociada con ese nodo padre, 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 bases .
Aunque los tries pueden codificarse con cadenas de caracteres, no es necesario que así sea. 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 con los bits individuales que forman una pieza de datos binarios de longitud fija, como un entero o una dirección de memoria . La complejidad de búsqueda de claves de un trie sigue siendo proporcional al tamaño de la clave. Se utilizan implementaciones de trie especializadas, como tries comprimidos, para lidiar con el enorme requisito de espacio de un trie en implementaciones ingenuas.
La idea de un trie para representar un conjunto de cadenas fue descrita de forma abstracta por primera vez por Axel Thue en 1912. [2] [3] Los tries fueron descritos por primera vez en un contexto informático por René de la Briandais en 1959. [4] [3] [5] : 336
La idea fue descrita independientemente en 1960 por Edward Fredkin , [6] quien acuñó el término trie , pronunciándolo / ˈt r iː / (como " árbol"), después de la sílaba media de retrieval . [7] [8] Sin embargo, otros autores lo pronuncian / ˈt r aɪ / (como "try"), en un intento de distinguirlo verbalmente de "árbol". [7] [8] [3]
Los tries son una forma de estructura de datos de búsqueda indexada en cadenas, que se utiliza para almacenar una lista de diccionario de palabras que se pueden buscar de una manera que permite la generación eficiente de listas de finalización . [9] [10] : 1 Un trie de prefijo es una estructura de datos de árbol ordenado que se utiliza en la representación de un conjunto de cadenas sobre un conjunto de alfabeto finito, que permite el almacenamiento eficiente de palabras con prefijos comunes. [1]
Los intentos pueden ser eficaces en algoritmos de búsqueda de cadenas como texto predictivo , coincidencia aproximada de cadenas y corrección ortográfica en comparación con árboles de búsqueda binarios. [11] [8] [12] : 358 Un trie puede verse como un autómata finito determinista en forma de árbol . [13]
Los tries admiten varias operaciones: inserción, eliminación y búsqueda de una clave de cadena. Los tries están compuestos de nodos que contienen enlaces, que apuntan a otros nodos secundarios de sufijo o null . Como en todos los árboles, cada nodo, excepto la raíz, es apuntado por un solo nodo más, llamado su padre . Cada nodo contiene tantos enlaces como el número de caracteres del alfabeto aplicable (aunque los tries tienden a tener un número sustancial de enlaces null ). En algunos casos, el alfabeto utilizado es simplemente el de la codificación de caracteres , lo que da como resultado, por ejemplo, un tamaño de 256 en el caso de ASCII (sin signo) . [14] : 732
Los enlaces nulos dentro de los hijos de un nodo enfatizan las siguientes características: [14] : 734 [5] : 336
Un tipo de estructura básica de nodos en el trie es el siguiente; puede contener un , opcional , que se asocia con cada clave almacenada en el último carácter de la cadena o nodo terminal.
La búsqueda de un valor en un trie se guía por los caracteres de la clave de la cadena de búsqueda, ya que cada nodo del trie contiene un enlace correspondiente a cada carácter posible en la cadena dada. Por lo tanto, seguir la cadena dentro del trie produce el valor asociado a la clave de la cadena dada. Un enlace nulo durante la búsqueda indica la inexistencia de la clave. [14] : 732-733
El siguiente pseudocódigo implementa el procedimiento de búsqueda para una clave de cadena dada en un trie raíz x . [15] : 135
En el pseudocódigo anterior, x y key corresponden al puntero del nodo raíz del trie y a la clave de cadena respectivamente. La operación de búsqueda, en un trie estándar, lleva tiempo, donde es el tamaño del parámetro de cadena , y corresponde al tamaño del alfabeto . [16] : 754 Los árboles binarios de búsqueda , por otro lado, toman en el peor de los casos, ya que la búsqueda depende de la altura del árbol ( ) del BST (en el caso de árboles balanceados ), donde y es el número de claves y la longitud de las claves. [12] : 358
El trie ocupa menos espacio en comparación con un BST en el caso de una gran cantidad de cadenas cortas, ya que los nodos comparten subsecuencias de cadena iniciales comunes y almacenan las claves implícitamente. [12] : 358 El nodo terminal del árbol contiene un valor no nulo, y es un acierto de búsqueda si el valor asociado se encuentra en el trie, y un error de búsqueda si no lo es. [14] : 733
La inserción en el trie se guía mediante el uso de los conjuntos de caracteres como índices de la matriz de hijos hasta que se alcanza el último carácter de la clave de cadena. [14] : 733-734 Cada nodo en el trie corresponde a una llamada de la rutina de ordenamiento por radix , ya que la estructura del trie refleja la ejecución del patrón de ordenamiento por radix de arriba hacia abajo. [15] : 135
Si se encuentra un enlace nulo antes de llegar al último carácter de la clave de cadena, se crea un nuevo nodo (línea 3). [14] : 745 El valor del nodo terminal se asigna al valor de entrada; por lo tanto, si el anterior no era nulo en el momento de la inserción, se sustituye con el nuevo valor.
La eliminación de un par clave-valor de un trie implica encontrar el nodo terminal con la clave de cadena correspondiente, marcar el indicador terminal y el valor como falso y nulo respectivamente. [14] : 740
El siguiente es un procedimiento recursivo para eliminar una clave de cadena de un trie raíz ( x ).
El procedimiento comienza examinando la clave ; null denota la llegada de un nodo terminal o el final de una clave de cadena. Si el nodo es terminal no tiene hijos, se elimina del trie (línea 14). Sin embargo, un final de clave de cadena sin que el nodo sea terminal indica que la clave no existe, por lo que el procedimiento no modifica el trie. La recursión continúa incrementando el índice de la clave .
Se puede utilizar un trie para reemplazar una tabla hash , sobre la cual tiene las siguientes ventajas: [12] : 358
Sin embargo, los intentos son menos eficientes que una tabla hash cuando se accede a los datos directamente en un dispositivo de almacenamiento secundario , como una unidad de disco duro que tiene un tiempo de acceso aleatorio más alto que la memoria principal . [6] Los intentos también son desventajosos cuando el valor de la clave no se puede representar fácilmente como una cadena, como números de punto flotante donde son posibles múltiples representaciones (por ejemplo, 1 es equivalente a 1.0, +1.0, 1.00, etc.), [12] : 359 sin embargo, se puede representar inequívocamente como un número binario en IEEE 754 , en comparación con el formato de complemento a dos . [17]
Los intentos se pueden representar de varias maneras, correspondientes a diferentes compensaciones entre el uso de memoria y la velocidad de las operaciones. [5] : 341 El uso de un vector de punteros para representar un trie consume un espacio enorme; sin embargo, el espacio de memoria se puede reducir a expensas del tiempo de ejecución si se utiliza una lista enlazada simple para cada vector de nodo, ya que la mayoría de las entradas del vector contienen . [3] : 495
Técnicas como la reducción del alfabeto pueden aliviar la alta complejidad espacial al reinterpretar la cadena original como una cadena larga sobre un alfabeto más pequeño, es decir, una cadena de n bytes puede considerarse alternativamente como una cadena de 2n unidades de cuatro bits y almacenarse en un trie con dieciséis punteros por nodo. Sin embargo, las búsquedas necesitan visitar el doble de nodos en el peor de los casos, aunque los requisitos de espacio se reducen en un factor de ocho. [5] : 347–352 Otras técnicas incluyen almacenar un vector de 256 punteros ASCII como un mapa de bits de 256 bits que representa el alfabeto ASCII, lo que reduce drásticamente el tamaño de los nodos individuales. [18]
Los intentos bit a bit se utilizan para abordar el enorme requisito de espacio para los nodos trie en una implementación simple e ingenua de vector puntero. Cada carácter en el conjunto de claves de cadena se representa a través de bits individuales, que se utilizan para recorrer el trie sobre una clave de cadena. Las implementaciones para estos tipos de trie utilizan instrucciones de CPU vectorizadas para encontrar el primer bit establecido en una entrada de clave de longitud fija (por ejemplo, la función intrínseca de GCC ). En consecuencia, el bit establecido se utiliza para indexar el primer elemento, o nodo hijo, en el árbol bit a bit basado en 32 o 64 entradas. Luego, la búsqueda continúa probando cada bit posterior en la clave. [19]__builtin_clz()
Este procedimiento también es local en caché y altamente paralelizable debido a la independencia de los registros , y por lo tanto tiene un buen rendimiento en CPU con ejecución fuera de orden . [19]
El árbol de base , también conocido como trie comprimido , es una variante optimizada en el espacio de un trie en el que cualquier nodo con un solo hijo se fusiona con su padre; la eliminación de las ramas de los nodos con un solo hijo da como resultado mejores métricas tanto en el espacio como en el tiempo. [20] [21] : 452 Esto funciona mejor cuando el trie permanece estático y el conjunto de claves almacenadas es muy disperso dentro de su espacio de representación. [22] : 3–16
Otro enfoque es "empaquetar" el trie, en el cual se aplica una implementación eficiente en términos de espacio de un trie empaquetado disperso a la separación automática de palabras , en la que los descendientes de cada nodo pueden intercalarse en la memoria. [8]
Los árboles Patricia son una implementación particular del trie binario comprimido que utiliza la codificación binaria de las claves de cadena en su representación. [23] [15] : 140 Cada nodo en un árbol Patricia contiene un índice, conocido como "número de salto", que almacena el índice de ramificación del nodo para evitar subárboles vacíos durante el recorrido. [15] : 140-141 Una implementación ingenua de un trie consume un almacenamiento inmenso debido a una mayor cantidad de nodos hoja causados por la distribución dispersa de claves; los árboles Patricia pueden ser eficientes para tales casos. [15] : 142 [24] : 3
A la derecha se muestra una representación de un árbol Patricia. Cada valor de índice adyacente a los nodos representa el "número de salto", el índice del bit con el que se debe decidir la ramificación. [24] : 3 El número de salto 1 en el nodo 0 corresponde a la posición 1 en el código binario ASCII donde el bit más a la izquierda difería en el conjunto de claves . [24] : 3-4 El número de salto es crucial para la búsqueda, inserción y eliminación de nodos en el árbol Patricia, y se realiza una operación de enmascaramiento de bits durante cada iteración. [15] : 143
Las estructuras de datos Trie se utilizan comúnmente en diccionarios de texto predictivo o de autocompletado , y en algoritmos de coincidencia aproximada . [11] Los tries permiten búsquedas más rápidas, ocupan menos espacio, especialmente cuando el conjunto contiene una gran cantidad de cadenas cortas, por lo que se utilizan en la corrección ortográfica , aplicaciones de separación de palabras y algoritmos de coincidencia de prefijo más largo . [8] [12] : 358 Sin embargo, si almacenar palabras del 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 un árbol de radix utilizarían menos espacio de almacenamiento que un trie. Esto se debe a que los DAFSA y los árboles de radix pueden comprimir ramas idénticas del trie que corresponden a los mismos sufijos (o partes) de diferentes palabras que se almacenan. Los diccionarios de cadenas también se utilizan en el procesamiento del lenguaje natural , como la búsqueda del léxico de un corpus de texto . [25] : 73
La ordenación lexicográfica de un conjunto de claves de cadena se puede implementar construyendo un trie para las claves dadas y recorriendo el árbol en modo preordenado ; [26] esto también es una forma de ordenación por radix . [27] Los tries también son estructuras de datos fundamentales para burstsort , que es notable por ser el algoritmo de ordenación de cadenas más rápido a partir de 2007, [28] logrado por su uso eficiente de la memoria caché de la CPU . [29]
Se puede utilizar un tipo especial de trie, llamado árbol de sufijos , para indexar todos los sufijos de un texto y realizar búsquedas rápidas de texto completo. [30]
En los motores de búsqueda web se utiliza un tipo especializado de trie, denominado trie comprimido, para almacenar los índices (una colección de todas las palabras que se pueden buscar). [31] Cada nodo terminal está asociado a una lista de URL (llamada lista de ocurrencias) que llevan a páginas que coinciden con la palabra clave. El trie se almacena en la memoria principal, mientras que la ocurrencia se guarda en un almacenamiento externo, frecuentemente en grandes clústeres , o el índice en memoria apunta a documentos almacenados en una ubicación externa. [32]
Los tries se utilizan en bioinformática , especialmente en aplicaciones de software de alineación de secuencias como BLAST , que indexa todas las diferentes subcadenas de longitud k (llamadas k-mers ) de un texto almacenando las posiciones de sus apariciones en bases de datos de secuencias de tries comprimidas. [25] : 75
Las variantes comprimidas de intentos, como las bases de datos para administrar la Base de información de reenvío (FIB), se utilizan para almacenar prefijos de direcciones IP dentro de enrutadores y puentes para la búsqueda basada en prefijos para resolver operaciones basadas en máscaras en el enrutamiento IP . [25] : 75
El preorden de los nodos en un trie es el mismo que el orden lexicográfico de las cadenas que representan, suponiendo que los hijos de un nodo están ordenados por las etiquetas de las aristas.
