Prueba

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

K-ary search tree data structure

Fig. 1: Un trío para llaves "A", "a", "tea", "ted", "ten", "i", "in", y "inn". Cada palabra inglesa completa tiene un valor entero arbitrario asociado con él.

En informática, un trie, también llamado árbol digital o árbol de prefijos, es un tipo de árbol de búsqueda k-ario, un estructura de datos de árbol utilizada para ubicar 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 recorre primero en profundidad, siguiendo los enlaces entre 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 necesariamente tienen 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 memoria empleando un árbol radix.

Aunque los intentos se pueden codificar mediante cadenas de caracteres, no es necesario. Los mismos algoritmos se pueden adaptar para listas ordenadas de cualquier tipo subyacente, p. permutaciones de dígitos o formas. En particular, un trie bit a bit se teclea en los bits individuales que forman una pieza de datos binarios de longitud fija, como un número 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. Las implementaciones de trie especializadas, como los intentos comprimidos, se utilizan para lidiar con el enorme requisito de espacio de un trie en implementaciones ingenuas.

Historia, etimología y pronunciación

La idea de un trie para representar un conjunto de cadenas fue descrita de forma abstracta por primera vez 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 (como "árbol"), después de la sílaba media de recuperación . Sin embargo, otros autores lo pronuncian (como "try"), en un intento de distinguirlo verbalmente de "árbol".

Resumen

Los intentos son una forma de estructura de datos de búsqueda indexada por cadena, que se utiliza para almacenar una lista de diccionario de palabras que se pueden buscar de una manera que permita la generación eficiente de listas de finalización. Un prefijo trie es una estructura de datos de árbol ordenado que se utiliza en la representación de un conjunto de cadenas sobre un conjunto finito de alfabetos, lo que permite el almacenamiento eficiente de palabras con prefijos comunes.

Los intentos pueden ser eficaces en los algoritmos de búsqueda de cadenas, como el texto predictivo, la coincidencia aproximada de cadenas y la revisión ortográfica en comparación con los árboles de búsqueda binarios. Un trie puede verse como un autómata finito determinista en forma de árbol.

Operaciones

Fig. 2: Trie representación de los conjuntos de cuerda: mar, vende, y ella.

Tries soporta varias operaciones: inserción, eliminación y búsqueda de una clave de cuerda. Tries se componen de ${displaystyle {text{nodes}}}$ que contienen enlaces que son referencias a otros nodos de niños sufijos, o ${displaystyle {text{nil}}}$ . Excepto root, cada nodo es apuntado por sólo otro nodo, llamado el padre. Cada nodo contiene ${displaystyle {text{R}}}$ enlaces, donde ${displaystyle {text{R}}}$ es la cardenalidad del conjunto de alfabetos, aunque los intentos tienen un número sustancial de ${displaystyle {text{nil}}}$ enlaces. En la mayoría de los casos, el tamaño de ${displaystyle {text{Children}}}$ array es bitlength de la codificación de caracteres - 256 en el caso de (sin firma) ASCII.

El ${displaystyle {text{nil}}}$ enlaces dentro ${displaystyle {text{Children}}}$ dentro ${displaystyle {text{Node}}}$ subraya las siguientes características:

Los caracteres y las teclas de cadena se almacenan implícitamente en la representación de la estructura de datos trie, e incluyen un valor centinela de carácter que indica la duración de la cadena.
Cada nodo contiene un posible enlace a un prefijo de teclas fuertes del conjunto.

Un tipo de estructura básica de nodos en el trie es el siguiente: ${displaystyle {text{Node}}}$ puede contener un opcional ${displaystyle {text{Value}}}$ , que se asocia con cada llave almacenada en el último carácter de cuerda, o nodo terminal.

 estructura Node
Niños Nodo[Alphabet-Size]Is-Terminal BooleanValor Data-Type estructura final

Buscando

Buscando un ${displaystyle {text{Value}}}$ en un trío se guía por los caracteres en la tecla de cadena de búsqueda, ya que cada nodo en el trío contiene un enlace correspondiente a cada personaje posible en la cadena dada. Por lo tanto, siguiendo la cadena dentro del trie rinde el asociado ${displaystyle {text{Value}}}$ para la llave de cuerda dada. A ${displaystyle {text{nil}}}$ enlace dentro de la ejecución de búsqueda indica la inexistencia de la clave.

Siguiendo el pseudocódigo implementa el procedimiento de búsqueda de una clave de cadena dada ( ${displaystyle {text{key}}}$ ) en un trie arraigado ( ${displaystyle {text{x}}}$ ).

 Trie-Find(x, key)
 para 0 ≤ i 0 llave. longitud do si x.Children[i] = nil entonces retorno falso
 terminar six:= x.Children[key[i]
 repetición retorno x. Valor

En el pseudocódigo anterior, ${displaystyle {text{x}}}$ y ${displaystyle {text{key}}}$ corresponde al puntero del nodo raíz de trie y la llave de cadena respectivamente. La operación de búsqueda, en un trie estándar, toma ${displaystyle O({text{dm}})}$ , ${displaystyle {text{m}}}$ es el tamaño del parámetro de cadena ${displaystyle {text{key}}}$ , y $text{d}$ corresponde al tamaño del alfabeto. Árboles de búsqueda binarios, por otro lado, tomar ${displaystyle O(mlog n)}$ en el peor caso, ya que la búsqueda depende de la altura del árbol ( $log n$ ) del BST (en caso de árboles equilibrados), donde ${displaystyle {text{n}}}$ y ${displaystyle {text{m}}}$ ser número de llaves y la longitud de las llaves.

Los tries ocupan menos espacio en comparación con BST si abarca un gran número de cuerdas cortas, ya que los nodos comparten las subsecuencias iniciales comunes y almacena las teclas implícitamente en la estructura. El nodo terminal del árbol contiene un no-nil ${displaystyle {text{Value}}}$ , y es un búsqueda si el valor asociado se encuentra en el trie, y búsqueda si no lo es.

Inserción

La inserción en trie se guía utilizando los conjuntos de caracteres como índices en los ${displaystyle {text{Children}}}$ array hasta el último carácter de la tecla de cuerda se alcanza. Cada nodo en el trie corresponde a una llamada de la rutina de clasificación de ráx, ya que la estructura trie refleja la ejecución de patten del tipo de ráx de arriba abajo.

1 Trie-Insert(x, clave, valor)
2 para 0 ≤ i 0 llave. longitud do3 si x.Children[i] = nil entonces4 x.Niños [key[i]:= Nodo()
5 terminar si6 x:= x.Children[key[i]
7 repetición8 x.Valor:= valor
9 x.Is-Terminal:= Cierto.

Si ${displaystyle {text{nil}}}$ enlace se encuentra antes de alcanzar el último carácter de la tecla de cadena, un nuevo ${displaystyle {text{Node}}}$ se crea, tal como las líneas 3-5. ${displaystyle {text{x.Value}}}$ se asigna a la entrada ${displaystyle {text{value}}}$ ; si ${displaystyle {text{x.Value}}}$ no ${displaystyle {text{nil}}}$ en el momento de la inserción, el valor asociado con la tecla de cadena dada se sustituye con la actual.

Eliminación

La eliminación de un par de valor clave de un trie implica encontrar el nodo terminal con la llave de cadena correspondiente, marcando el indicador terminal y el valor a falso y ${displaystyle {text{nil}}}$ correspondientemente.

A continuación es un procedimiento recursivo para eliminar una clave de cadena ( ${displaystyle {text{key}}}$ ) de la trie arraigada ( ${displaystyle {text{x}}}$ ).

1 Trie-Delete(x, clave)
2 si llave = nil entonces3 si x.Is-Terminal = True entonces4 x.Is-Terminal:= Falso
5 x.Valor:= Nil
6 terminar si7 para 0 ≤ i 0
8 si x.Children[i]!= Nil
9 retorno x
10 terminar si11 repetición12 retorno Nil
13 terminar si14 x.Children[key[0]:= Trie-Delete(x.Children[key[0]], key[1:]
15 retorno x

Los procedimientos comienzan examinando ${displaystyle {text{key}}}$ ; ${displaystyle {text{nil}}}$ denota la llegada de un nodo terminal o el final de la tecla de cuerda. Si terminal y si no tiene hijos, el nodo se elimina del trie (línea 14 asigna el índice de caracteres a ${displaystyle {text{nil}}}$ ). Sin embargo, un extremo de llave de cadena sin el nodo de terminal indica que la clave no existe, por lo tanto el procedimiento no modifica el trío. La recursión procede aumentando ${displaystyle {text{key}}}$ Es un índice.

Reemplazar 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 un nodo con una clave asociada de tamaño $m$ tiene la complejidad $O(m)$ , mientras que una función de hash imperfecta puede tener numerosas teclas colliding, y la velocidad de búsqueda peor de una tabla sería $O(N)$ , donde $N$ denota el número total de nodos dentro del cuadro.
Los tries no necesitan una función de hash para la operación, a diferencia de una tabla de hash; tampoco hay colisiones de diferentes teclas en un trie.
Los cubos en un trie, que son análogos a los cubos de mesa de hash que almacenan colisiones clave, son necesarios sólo si una sola clave se asocia con más de un valor.
Las teclas de cuerda dentro del trie se pueden clasificar usando un orden alfabético predeterminado.

Sin embargo, los intentos son menos eficientes que una tabla hash cuando se accede directamente a los datos 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. 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 coma flotante donde son posibles múltiples representaciones (por ejemplo, 1 es equivalente a 1.0, +1.0, 1.00, etc.), sin embargo, se puede representar sin ambigüedades como un número binario en IEEE 754, en comparación con el formato complemento a dos.

Estrategias de implementación

Fig. 3: Un trie implementado como un árbol binario de la derecha del niño izquierdo: las flechas verticales son niño punteros, flechas horizontales desgarradas son siguiente apuntadores. El conjunto de cuerdas almacenadas en este trie es {baby, bad, bank, box, papa, dance}. Las listas están clasificadas para permitir el traversal en orden lexicográfico.

Los tries pueden ser representados de varias maneras, correspondientes a los distintos intercambios entre el uso de la memoria y la velocidad de las operaciones. Usar 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 ligada cantar para cada vector de nodos, ya que la mayoría de las entradas del vector contiene ${displaystyle {text{nil}}}$ .

Técnicas como la reducción del alfabeto pueden aliviar la gran complejidad del espacio al reinterpretar la cadena original como una cadena larga sobre un alfabeto más pequeño, es decir, una cadena de $n$ bytes se pueden considerar alternativamente como una cadena de $2 n$ unidades de cuatro bits y almacenarse en un intente con dieciséis punteros por nodo. Sin embargo, las búsquedas deben visitar el doble de nodos en el peor de los casos, aunque los requisitos de espacio se reducen en un factor de ocho. Otras técnicas incluyen el almacenamiento de un vector de 256 punteros ASCII como un mapa de bits de 256 bits que representan el alfabeto ASCII, lo que reduce drásticamente el tamaño de los nodos individuales.

Intentos bit a bit

Los intentos bit a bit se utilizan para abordar el enorme requisito de espacio para los nodos trie en implementaciones de vector de puntero simples e ingenuas. Cada carácter en el conjunto de claves de cadena se representa a través de bits individuales, que se utilizan para atravesar el trie sobre una clave de cadena. Las implementaciones para estos tipos de trie usan 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 __builtin_clz() de GCC). En consecuencia, el bit establecido se utiliza para indexar el primer elemento, o nodo secundario, en el árbol bit a bit basado en 32 o 64 entradas. Luego, la búsqueda continúa probando cada bit subsiguiente en la clave.

Este procedimiento también es local en caché y altamente paralelizable debido a la independencia del registro y, por lo tanto, funciona en CPU de ejecución fuera de orden.

Intentos comprimidos

El árbol Radix, también conocido como trie comprimido, es una variante de espacio optimizado de un trie en la que los nodos con un solo hijo se fusionan con sus padres; la eliminación de ramas de los nodos con un solo hijo da como resultado mejores métricas tanto de espacio como de tiempo. Esto funciona mejor en las siguientes condiciones, donde el trie permanece estático y el conjunto de claves almacenadas es muy escaso dentro de su espacio de representación.

Un enfoque más es "empacar" el trie, en el que se aplica una implementación eficiente en el espacio de un trie empaquetado disperso a la partición automática, en el que los descendientes de cada nodo pueden intercalarse en la memoria.

Patricia árboles

Fig. 4: Patricia árbol representación de llaves de cuerda: en, entero, intervalo, cuerda y estructura.

Los árboles Patricia son una implementación particular de trie binario comprimido que utiliza la codificación binaria de las claves de cadena en su representación. Cada nodo en un árbol de 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. Una implementación ingenua de un trie consume una gran cantidad de almacenamiento debido a una mayor cantidad de nodos de hoja causados por una distribución escasa de claves; Los árboles Patricia pueden ser eficientes para estos casos.

Una representación de un árbol Patricia con llaves de cuerda ${displaystyle {in,integer,interval,string,structure}}$ se muestra en la figura 4, y cada valor de índice adyacente a los nodos representa el "número de error" - el índice del bit con el que se decidirá la ramificación. El patrón número 1 en el nodo 0 corresponde a la posición 1 en el ASCII codificado binario donde el bit más izquierdo difería en el conjunto clave $X$ . El número de salto es crucial para la búsqueda, inserción y eliminación de nodos en el árbol de Patricia, y un poco de operación de enmascaramiento se realiza durante cada iteración.

Aplicaciones

Las estructuras de datos Trie se usan comúnmente en texto predictivo o diccionarios de autocompletado y algoritmos de coincidencia aproximada. Los intentos 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 revisión ortográfica, aplicaciones de guiones y algoritmos de coincidencia de prefijos más largos. Sin embargo, si todo lo que se requiere es almacenar palabras del diccionario (es decir, no es necesario almacenar metadatos asociados con cada palabra), un autómata de estado finito acíclico determinista mínimo (DAFSA) o un árbol radix usaría menos espacio de almacenamiento que un trie. Esto se debe a que los árboles DAFSA y radix pueden comprimir ramas idénticas del trie que corresponden a los mismos sufijos (o partes) de diferentes palabras almacenadas. Los diccionarios de cadenas también se utilizan en el procesamiento del lenguaje natural, como encontrar el léxico de un corpus de texto.

Clasificación

La clasificación lexicográfica de un conjunto de claves de cadena se puede implementar creando un trie para las claves dadas y recorriendo el árbol en forma de orden anticipado; esta es también una forma de clasificación radix. Los intentos también son estructuras de datos fundamentales para burstsort, que se destaca por ser el algoritmo de clasificación de cadenas más rápido a partir de 2007, acompañado por su uso eficiente de la memoria caché de la CPU.

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 para realizar búsquedas rápidas de texto completo.

Motores de búsqueda web

Un tipo especializado de trie llamado trie comprimido se utiliza en los motores de búsqueda web para almacenar los índices, una colección de todas las palabras que se pueden buscar. Cada nodo terminal está asociado con una lista de URL, llamada lista de ocurrencia, 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, con frecuencia en grandes grupos, o el índice en memoria apunta a documentos almacenados en una ubicación externa.

Bioinformática

Los intentos 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 ocurrencias en bases de datos de secuencias trie comprimidas.

Enrutamiento de Internet

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 búsquedas basadas en prefijos para resolver operaciones basadas en máscaras en el enrutamiento IP.

Contenido relacionado

Más resultados...