Hay varias formas de representar los tries, que corresponden a diferentes compensaciones entre el uso de memoria y la velocidad de las operaciones. La forma básica es la de un conjunto enlazado de nodos, donde cada nodo contiene una matriz de punteros hijos, uno por cada símbolo del alfabeto (así, para el alfabeto inglés, se almacenarían 26 punteros hijos y para el alfabeto de bytes, 256 punteros). Esto es sencillo pero derrochador en términos de memoria: utilizando el alfabeto de bytes (tamaño 256) y punteros de cuatro bytes, cada nodo requiere un kilobyte de almacenamiento, y cuando hay poco solapamiento en los prefijos de las cadenas, el número de nodos necesarios es aproximadamente la longitud combinada de las cadenas almacenadas.:341 Dicho de otro modo, los nodos cercanos a 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.
El problema de almacenamiento puede aliviarse mediante una técnica de implementación llamada reducción del alfabeto, por la que 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 como una cadena de 2n unidades de cuatro bits y almacenarse en un trie con dieciséis punteros por nodo. En el peor de los casos, las búsquedas necesitan visitar el doble de nodos, pero los requisitos de almacenamiento se reducen en un factor de ocho.:347-352
Una implementación alternativa representa un nodo como un triple (símbolo, hijo, siguiente) y enlaza los hijos de un nodo como una lista enlazada individualmente: hijo apunta al primer hijo del nodo, siguiente al siguiente hijo del nodo padre. El conjunto de hijos también puede representarse como un árbol de búsqueda binario; un ejemplo de esta idea es el árbol de búsqueda ternario desarrollado por Bentley y Sedgewick.:353
Otra alternativa para evitar el uso de una matriz de 256 punteros (ASCII), como se sugirió antes, es almacenar la matriz del alfabeto como un mapa de bits de 256 bits que representa el alfabeto ASCII, reduciendo drásticamente el tamaño de los nodos.
Bitwise triesEdit
Los intentos de bits son muy parecidos a los de 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. Por lo general, las implementaciones utilizan una instrucción especial de la CPU para encontrar rápidamente el primer bit establecido en una clave de longitud fija (por ejemplo, la intrínseca __builtin_clz() de GCC). Este valor se utiliza entonces para indexar una tabla de 32 o 64 entradas que apunta al primer elemento de la tríada de bits con ese número de bits cero a la izquierda. La búsqueda entonces procede probando cada bit subsiguiente en la clave y eligiendo child o child apropiadamente hasta que se encuentra el elemento.
Aunque este proceso puede parecer lento, es muy localizado en la caché y altamente paralelizable debido a la falta de dependencias de registro y por lo tanto, de hecho, tiene un excelente rendimiento en las CPUs modernas de ejecución fuera de orden. Un árbol rojo-negro, por ejemplo, rinde mucho más sobre el papel, pero es muy poco amigable con la caché y provoca múltiples paradas en la tubería y en la TLB en las CPUs modernas, lo que hace que ese algoritmo esté limitado por la latencia de la memoria más que por la velocidad de la CPU. En comparación, un trie a nivel de bits rara vez accede a la memoria, y cuando lo hace, lo hace sólo para leer, evitando así la sobrecarga de coherencia de la caché SMP. Por ello, se está convirtiendo cada vez más en el algoritmo elegido para el código que realiza muchas inserciones y eliminaciones rápidas, como los asignadores de memoria (por ejemplo, las versiones recientes del famoso asignador de Doug Lea (dlmalloc) y sus descendientes). El peor caso de pasos para la búsqueda es el mismo que el de los bits utilizados para indexar las casillas en el árbol.
Alternativamente, el término «bitwise trie» puede referirse de forma más general a una estructura de árbol binario que contiene valores enteros, ordenándolos por su prefijo binario. Un ejemplo es el trie x-fast.
Comprimir triesEdit
Comprimir el trie y fusionar las ramas comunes a veces puede producir grandes ganancias de rendimiento. Esto funciona mejor bajo 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).
- Sólo se necesitan búsquedas.
- Los nodos del trie no tienen claves de datos específicos del nodo, o los datos de los nodos son comunes.
- El conjunto total de claves almacenadas es muy escaso dentro de su espacio de representación (por lo que la compresión compensa).
Por ejemplo, puede utilizarse para representar conjuntos de bits escasos; es decir, subconjuntos de un conjunto enumerable fijo mucho mayor. En este caso, la clave del trie es la posición del elemento de bit dentro del conjunto completo. La clave se crea a partir de la cadena de bits necesaria para codificar la posición integral de cada elemento. Estos intentos tienen una forma muy degenerada con muchas ramas perdidas. Después de detectar la repetición de patrones comunes o de rellenar los huecos no utilizados, los nodos de hoja únicos (cadenas de bits) pueden almacenarse y comprimirse 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. Estas podrían incluir tablas de mapeo de mayúsculas y minúsculas (por ejemplo, para la letra griega pi, de Π a π), o tablas de búsqueda que normalizan la combinación de caracteres base y de combinación (como la a-umlaut en alemán, ä, o la dalet-patah-dagesh-ole en hebreo bíblico, דַּ֫). Para este tipo de aplicaciones, la representación es similar a la transformación de una tabla muy grande, unidimensional y dispersa (por ejemplo, los puntos de código Unicode) en una matriz multidimensional de sus combinaciones y, a continuación, utilizar las coordenadas de la hipermatriz como la clave de la cadena de un trie sin comprimir para representar el carácter resultante. La compresión consistirá entonces 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 completo y multibyte de cada elemento que forma una columna de la 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 sólo es necesario almacenar el desplazamiento (normalmente un solo byte). El vector resultante es en sí mismo compresible cuando también es disperso, por lo que cada dimensión (asociada a un nivel de capa en el trie) puede comprimirse por separado.
Algunas implementaciones soportan dicha compresión de datos dentro de los tries dinámicos dispersos y permiten inserciones y eliminaciones en los tries comprimidos. Sin embargo, esto suele tener un coste significativo cuando los segmentos comprimidos deben dividirse o fusionarse. Hay que hacer algún tipo de 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.
El resultado de dicha compresión puede parecer similar a intentar transformar el trie en un grafo 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 viene determinada por la forma de la clave elegida para indexar los nodos, lo que a su vez limita la compresión posible.
Otra estrategia de compresión consiste en «desenredar» la estructura de datos en una única matriz de bytes.Este enfoque elimina la necesidad de punteros de nodos, reduciendo sustancialmente los requisitos de memoria. Esto, a su vez, permite el mapeo de la memoria y el uso de la memoria virtual para cargar eficientemente los datos desde el disco.
Un enfoque más es «empaquetar» el trie. Liang describe una implementación de espacio eficiente de un trie empaquetado disperso aplicado a la separación automática de sílabas, en el que los descendientes de cada nodo pueden intercalarse en la memoria.
Intentos de memoria externaEdit
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 una combinación de trie y B-tree, llamada B-trie para esta tarea; en comparación con los árboles de sufijos, están limitados en las operaciones soportadas pero también son más compactos, a la vez que realizan las operaciones de actualización más rápidamente.