Trie - Trie
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 un valor asociado.
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, se teclea un trie bit a bit 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 cuerdas fue descrita por primera vez de forma abstracta por Axel Thue en 1912. Los tries fueron descritos por primera vez en un contexto informático por René de la Briandais en 1959. La idea fue descrita de forma independiente en 1960 por Edward Fredkin , quien acuñó el término trie , pronunciándolo / t r i / (como "árbol"), después de la sílaba medio de recuperación . Sin embargo, otros autores lo pronuncian / t r aɪ / (como "tratar"), en un intento de distinguir verbalmente de "árbol".
Aplicaciones
Representación de diccionario
Las aplicaciones comunes de los intentos incluyen almacenar un texto predictivo o un diccionario de autocompletar e implementar algoritmos de coincidencia aproximada, como los que se usan en el software de revisión ortográfica y división de palabras . Estas aplicaciones aprovechan la capacidad de un ensayo para buscar, insertar y eliminar entradas rápidamente. 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 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. 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. (Una tabla hash imperfecta puede tener colisiones de claves. Una colisión de claves es la asignación de funciones hash de diferentes claves a la misma posición en una tabla hash).
- 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.
- Algunas claves, como los números de coma flotante, pueden dar lugar a 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.
- 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:
# Note that using a dictionary for children (as in this implementation)
# would not by default lexicographically sort the children, which is
# required by the lexicographic sorting in the Sorting section.
# For lexicographic sorting, we can instead use an array of Nodes.
self.children: Dict[str, Node] = {} # mapping from character to Node
self.value: Optional[Any] = None
Tenga en cuenta que childrenes 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 find(node: Node, key: str) -> Optional[Any]:
"""Find value by key in node."""
for char in key:
if char in node.children:
node = node.children[char]
else:
return None
return node.value
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(node: Node, key: str, value: Any) -> None:
"""Insert key/value pair into node."""
for char in key:
if char not in node.children:
node.children[char] = Node()
node = node.children[char]
node.value = value
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í:
def delete(root: Node, key: str) -> bool:
"""Eagerly delete the key from the trie rooted at `root`.
Return whether the trie rooted at `root` is now empty.
"""
def _delete(node: Node, key: str, d: int) -> bool:
"""Clear the node corresponding to key[d], and delete the child key[d+1]
if that subtrie is completely empty, and return whether `node` has been
cleared.
"""
if d == len(key):
node.value = None
else:
c = key[d]
if c in node.children and _delete(node.children[c], key, d+1):
del node.children[c]
# Return whether the subtrie rooted at `node` is now completely empty
return node.value is None and len(node.children) == 0
return _delete(root, key, 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.
def keys_with_prefix(root: Node, prefix: str) -> List[str]:
results: List[str] = []
x = _get_node(root, prefix)
_collect(x, list(prefix), results)
return results
def _collect(x: Optional[Node], prefix: List[str], results: List[str]) -> None:
"""
Append keys under node `x` matching the given prefix to `results`.
prefix: list of characters
"""
if x is None:
return
if x.value is not None:
prefix_str = ''.join(prefix)
results.append(prefix_str)
for c in x.children:
prefix.append(c)
_collect(x.children[c], prefix, results)
del prefix[-1] # delete last character
def _get_node(node: Node, key: str) -> Optional[Node]:
"""
Find node by key. This is the same as the `find` function defined above,
but returning the found node itself rather than the found node's value.
"""
for char in key:
if char in node.children:
node = node.children[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. Este algoritmo es una forma de ordenación por base .
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é . Ahora hay otros más rápidos.
Búsqueda de texto completo
Se puede utilizar 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 enlazado 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. 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.
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.
Una implementación alternativa representa un nodo como una triple (símbolo, niño, al lado) y vincula los hijos de un nodo juntos como una lista enlazada : niño puntos al primer hijo del nodo, junto al próximo hijo del nodo principal. 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 .
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.
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 usan 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 para la búsqueda es el mismo que el de los bits que se utilizan para indexar bins en el árbol.
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.
- 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 explotar 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 realizar 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.
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. 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. Liang describe una implementación de uso eficiente del espacio de un trie empaquetado disperso aplicado a la separación de sílabas automática , en la que los descendientes de cada nodo se pueden intercalar 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, al tiempo que realizan operaciones de actualización más rápido.
Ver también
- Árbol de sufijo
- Árbol de radix
- Gráfico de palabras acíclico dirigido (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 hash mapeada trie
- Prefijo árbol hash
- Burstsort
- Algoritmo de Luleå
- Codificación Huffman
- Ctrie
- HAT-trie
- Trie bit a bit con mapa de bits