programacion node lexicografico busqueda arboles arbol algoritmo algorithm data-structures tree patricia-trie radix-tree

algorithm - node - trie programacion



¿Cuál es la diferencia entre las estructuras de datos trie y radix trie? (3)

¿Son las estructuras de datos trie y radix trie lo mismo?

Si son iguales, ¿cuál es el significado de radix trie (AKA Patricia trie)?

Mi pregunta es si la estructura de datos Trie y Radix Trie son la misma cosa.

En resumen, no. La categoría Radix Trie describe una categoría particular de Trie , pero eso no significa que todos los intentos sean radix tries.

Si no son [iguales], ¿cuál es el significado de Radix trie (también conocida como Patricia Trie)?

Supongo que quisiste escribir , no estás en tu pregunta, de ahí mi corrección.

Del mismo modo, PATRICIA denota un tipo específico de raíz trie, pero no todos los intentos de raíz son intentos de PATRICIA.

¿Qué es un trie?

"Trie" describe una estructura de datos de árbol adecuada para su uso como una matriz asociativa, donde las ramas o los bordes corresponden a partes de una clave. La definición de partes es bastante vaga, porque diferentes implementaciones de intentos usan diferentes longitudes de bits para corresponder a los bordes. Por ejemplo, un trie binario tiene dos bordes por nodo que corresponden a un 0 o un 1, mientras que un trie de 16 vías tiene dieciséis bordes por nodo que corresponden a cuatro bits (o un dígito hexadecimal: 0x0 a 0xf).

Este diagrama, obtenido de Wikipedia, parece representar un trie con (al menos) las teclas ''A'', ''to'', ''tea'', ''ted'', ''ten'' y ''inn'' insertados:

Si este trie fuera a almacenar elementos para las teclas ''t'', ''te'', ''i'' o ''in'', debería haber información adicional presente en cada nodo para distinguir entre nodos nulary y nodos con valores reales.

¿Qué es un Radix Trie?

"Radix trie" parece describir una forma de trie que condensa partes de prefijo comunes, como Ivaylo Strandjev describió en su respuesta. Considere que un trie de 256 vías que indexa las teclas "sonríe", "sonríe", "sonríe" y "sonríe" usando las siguientes asignaciones estáticas:

root[''s''][''m''][''i''][''l''][''e''][''/0''] = smile_item; root[''s''][''m''][''i''][''l''][''e''][''d''][''/0''] = smiled_item; root[''s''][''m''][''i''][''l''][''e''][''s''][''/0''] = smiles_item; root[''s''][''m''][''i''][''l''][''i''][''n''][''g''][''/0''] = smiling_item;

Cada subíndice tiene acceso a un nodo interno. Eso significa recuperar smile_item , debe acceder a siete nodos. Ocho accesos de nodos corresponden a smiled_item y smiles_item , y nueve a smiling_item . Para estos cuatro elementos, hay catorce nodos en total. Sin embargo, todos tienen los primeros cuatro bytes (correspondientes a los primeros cuatro nodos) en común. Al condensar esos cuatro bytes para crear una root que corresponde a [''s''][''m''][''i''][''l''] , se han optimizado cuatro accesos de nodo. Eso significa menos memoria y menos accesos a nodos, lo cual es una muy buena indicación. La optimización se puede aplicar recursivamente para reducir la necesidad de acceder a bytes de sufijos innecesarios. Eventualmente, llegas al punto en el que solo comparas las diferencias entre la clave de búsqueda y las claves indexadas en las ubicaciones indexadas por el trie . Esta es una raíz trie.

root = smil_dummy; root[''e''] = smile_item; root[''e''][''d''] = smiled_item; root[''e''][''s''] = smiles_item; root[''i''] = smiling_item;

Para recuperar elementos, cada nodo necesita una posición. Con una clave de búsqueda de "sonrisas" y una posición root.position de 4, accedemos a root["smiles"[4]] , que resulta ser root[''e''] . Almacenamos esto en una variable llamada current . current.position es 5, que es la ubicación de la diferencia entre "smiled" "smiles" y "smiles" , por lo que el siguiente acceso será root["smiles"[5]] . Esto nos lleva a smiles_item , y al final de nuestra cadena. Nuestra búsqueda ha finalizado y el elemento se ha recuperado, con solo tres accesos de nodo en lugar de ocho.

¿Qué es un trie PATRICIA?

Un trie PATRICIA es una variante de intentos de radix para los que solo debe haber n nodos que contengan n elementos. En nuestro pseudocódigo de rootix crudamente demostrado anteriormente, hay cinco nodos en total: root (que es un nodo nullary, no contiene ningún valor real), root[''e''] , root[''e''][''d''] , root[''e''][''s''] y root[''i''] . En un trie PATRICIA solo debería haber cuatro. Echemos un vistazo a cómo podrían diferir estos prefijos viéndolos en binario, ya que PATRICIA es un algoritmo binario.

smile: 0111 0011 0110 1101 0110 1001 0110 1100 0110 0101 0000 0000 0000 0000 smiled: 0111 0011 0110 1101 0110 1001 0110 1100 0110 0101 0110 0100 0000 0000 smiles: 0111 0011 0110 1101 0110 1001 0110 1100 0110 0101 0111 0011 0000 0000 smiling: 0111 0011 0110 1101 0110 1001 0110 1100 0110 1001 0110 1110 0110 0111 ...

Consideremos que los nodos se agregan en el orden en que se presentan arriba. smile_item es la raíz de este árbol. La diferencia, en negrita para que sea un poco más fácil de detectar, está en el último byte de "smile" , en el bit 36. Hasta este punto, todos nuestros nodos tienen el mismo prefijo. smiled_node pertenece a smile_node[0] . La diferencia entre "smiled" "smiles" "smiled" y "smiles" ocurre en el bit 43, donde "smiles" tiene un "1" bit, por lo que smiled_node[1] es smiles_node .

En lugar de utilizar NULL como ramas y / o información interna adicional para indicar cuándo finaliza una búsqueda, las ramas vinculan una copia de seguridad del árbol en alguna parte, por lo que la búsqueda finaliza cuando el desplazamiento a prueba disminuye en lugar de aumentar. Aquí hay un diagrama simple de dicho árbol (aunque PATRICIA en realidad es más un gráfico cíclico, que un árbol, como verá), que se incluyó en el libro de Sedgewick que se menciona a continuación:

Es posible un algoritmo PATRICIA más complejo que implica claves de longitud variable, aunque algunas de las propiedades técnicas de PATRICIA se pierden en el proceso (es decir, que cualquier nodo contiene un prefijo común con el nodo anterior):

Al bifurcar de esta manera, hay una serie de beneficios: cada nodo contiene un valor. Eso incluye la raíz. Como resultado, la longitud y complejidad del código se vuelve mucho más corta y probablemente un poco más rápida en realidad. Se sigue al menos una rama y como máximo k ramas (donde k es la cantidad de bits en la clave de búsqueda) para localizar un elemento. Los nodos son pequeños , ya que almacenan solo dos ramas cada uno, lo que los hace bastante adecuados para la optimización de la ubicación del caché. Estas propiedades hacen que PATRICIA sea mi algoritmo favorito hasta ahora ...

Voy a resumir esta descripción aquí, para reducir la gravedad de mi artritis inminente, pero si quieres saber más sobre PATRICIA puedes consultar libros como "The Art of Computer Programming, Volume 3" de Donald Knuth. , o cualquiera de los "Algoritmos en {your-favorite-language}, parts 1-4" de Sedgewick.

Un árbol de raíz es una versión comprimida de un trie. En un trie, en cada borde escribe una sola letra, mientras que en un árbol PATRICIA (o un árbol de raíz) almacena palabras completas.

Ahora, supongamos que tiene las palabras hello , hat y have . Para almacenarlos en un trie , se vería así:

e - l - l - o / h - a - t / v - e

Y necesitas nueve nodos. He colocado las letras en los nodos, pero de hecho etiquetan los bordes.

En un árbol Radix, tendrás:

* / (ello) / * - h - * -(a) - * - (t) - * / (ve) / *

y solo necesitas cinco nodos. En la imagen de arriba, los nodos son los asteriscos.

Entonces, en general, un árbol de raíz consume menos memoria , pero es más difícil de implementar. De lo contrario, el caso de uso de ambos es prácticamente el mismo.

TRIE:
Podemos tener un esquema de búsqueda en el que en lugar de comparar una clave de búsqueda completa con todas las claves existentes (como un esquema de hash), también podríamos comparar cada carácter de la clave de búsqueda. Siguiendo esta idea, podemos construir una estructura (como se muestra a continuación) que tiene tres claves existentes: " papá ", " dab " y " taxi ".

[root] ...// | //... | / c d | / [*] [*] ...//|/. ./|//... Fig-I a a / / [*] [*] ...//|/.. ../|//... / / / B b d / / / [] [] [] (cab) (dab) (dad)

Esto es esencialmente un árbol M-ary con nodo interno, representado como [*] y nodo de hoja, representado como []. Esta estructura se llama trie . La decisión de ramificación en cada nodo se puede mantener igual al número de símbolos únicos del alfabeto, digamos R. Para los alfabetos en inglés de minúsculas az, R = 26; para alfabetos ASCII extendidos, R = 256 y para dígitos binarios / cadenas R = 2.

TRIE compacto:
Típicamente, un nodo en un trie utiliza una matriz con tamaño = R y por lo tanto causa pérdida de memoria cuando cada nodo tiene menos bordes. Para eludir la preocupación por la memoria, se hicieron varias propuestas. En función de esas variaciones, también se denominan " trie compacto " y " trie comprimido ". Mientras que una nomenclatura consistente es rara, una versión más común de un trie compacto se forma agrupando todos los bordes cuando los nodos tienen un solo borde. Usando este concepto, el trie de arriba (Fig-I) con las teclas "papá", "dab" y "taxi" puede tomar debajo de la forma.

[root] ...// | //... | / cab da | / [ ] [*] Fig-II ./|//... | / b d | / [] []

Tenga en cuenta que cada una de ''c'', ''a'' y ''b'' es el borde único para su nodo principal correspondiente y, por lo tanto, están conglomeradas en un solo borde "cab". Del mismo modo, ''d'' y a ''se fusionan en un solo borde etiquetado como "da".

Radix Trie:
El término raíz , en Matemáticas, significa una base de un sistema de números, y esencialmente indica el número de símbolos únicos necesarios para representar cualquier número en ese sistema. Por ejemplo, el sistema decimal es la raíz diez, y el sistema binario es la segunda raíz. Usando el concepto similar, cuando estamos interesados ​​en caracterizar una estructura de datos o un algoritmo por el número de símbolos únicos del sistema representacional subyacente, etiquetamos el concepto con el término "raíz". Por ejemplo, "clasificación de radix" para cierto algoritmo de clasificación. En la misma línea de lógica, todas las variantes de trie cuyas características (como profundidad, necesidad de memoria, búsqueda fallida / hit runtime, etc.) dependen de la raíz de los alfabetos subyacentes, podemos llamarlos radix "trie''s". Por ejemplo, un trie no compactado y uno compacto cuando usa alfabetos az, podemos llamarlo radix 26 trie . Cualquier trie que use solo dos símbolos (tradicionalmente ''0'' y ''1'') puede llamarse radix 2 trie . Sin embargo, de alguna manera, muchas literaturas restringieron el uso del término "Radix Trie" solo para el trie compactado.

Preludio a PATRICIA Tree / Trie:
Sería interesante observar que incluso las cadenas como claves se pueden representar utilizando alfabetos binarios. Si asumimos la codificación ASCII, entonces se puede escribir una clave "papá" en forma binaria escribiendo la representación binaria de cada carácter en secuencia, digamos como " 01100100 01100001 01100100 " escribiendo formas binarias de ''d'', ''a'', y ''d'' secuencialmente. Usando este concepto, se puede formar un trie (con Radix Two). A continuación mostramos este concepto usando una suposición simplificada de que las letras ''a'', ''b'', ''c'' y ''d'' son de un alfabeto más pequeño en lugar de ASCII.

Nota para la figura III: Como se mencionó, para facilitar la representación, supongamos un alfabeto con solo 4 letras {a, b, c, d} y sus representaciones binarias correspondientes son "00", "01", "10" y "11" respectivamente. Con esto, nuestras teclas "dad", "dab" y "cab" se convierten en "110011", "110001" y "100001", respectivamente. El trie para esto será como se muestra a continuación en la Fig-III (los bits se leen de izquierda a derecha al igual que las cadenas se leen de izquierda a derecha).

[root] /1 / [*] 0/ /1 / / [*] [*] 0/ / / /0 [*] [*] 0/ / / /0 [*] [*] 0/ 0/ /1 Fig-III / / / [*] [*] [*] /1 /1 /1 / / / [] [] [] (cab) (dab) (dad)

PATRICIA Trie / Árbol:
Si comparamos el trie binario anterior (Fig-III) usando la compactación de un solo borde, tendría muchos menos nodos que los mostrados anteriormente y, sin embargo, los nodos aún serían más que el 3, el número de claves que contiene. Donald R. Morrison encontró (en 1968) una forma innovadora de utilizar trie binario para representar claves N usando solo N nodos y designó a esta estructura de datos PATRICIA . Su estructura trie esencialmente se deshizo de los bordes individuales (ramificación en una sola dirección); y al hacerlo, también se deshizo de la noción de dos tipos de nodos: los nodos internos (que no muestran ninguna clave) y los nodos de las hojas (que representan las claves). A diferencia de la lógica de compactación explicada anteriormente, su trie usa un concepto diferente donde cada nodo incluye una indicación de cuántos bits de una clave se omiten para tomar una decisión de ramificación. Otra característica de su tía PATRICIA es que no almacena las claves, lo que significa que dicha estructura de datos no será adecuada para responder preguntas como, enumerar todas las claves que coinciden con un prefijo dado , pero es bueno para encontrar si existe una clave o no en el trie . Sin embargo, el término Patricia Tree o Patricia Trie se ha usado desde entonces en muchos sentidos diferentes pero similares, por ejemplo, para indicar un trie compacto [NIST], o para indicar un radix trie con radix two [como se indica en una sutil manera en WIKI] y así sucesivamente.

Trie que puede no ser una Radix Trie:
Ternary Search Trie (también conocido como Ternary Search Tree) abreviado a menudo como TST es una estructura de datos (propuesta por J. Bentley y R. Sedgewick ) que se ve muy similar a una trie con ramificación de tres vías. Para dicho árbol, cada nodo tiene un alfabeto característico ''x'', de modo que la decisión de bifurcación depende de si el carácter de una clave es menor, igual o mayor que ''x''. Debido a esta característica de bifurcación fija de 3 vías, proporciona una alternativa de memoria eficiente para trie, especialmente cuando R (radix) es muy grande, como para los alfabetos Unicode. Curiosamente, el TST, a diferencia del (R-way) trie , no tiene sus características influenciadas por R. Por ejemplo, la búsqueda fallida para TST es ln (N) en oposición al log R (N) para R-way Trie. Los requisitos de memoria de TST, a diferencia de R-way trie, NO son una función de R también. Por lo tanto, debemos tener cuidado de llamar a un TST un radix-trie. Personalmente, no creo que debamos llamarlo radix-trie ya que ninguno (hasta donde yo sé) de sus características está influenciado por la raíz, R, de sus alfabetos subyacentes.