[*]Te damos la bienvenida a nuestro sitio, en este sitio vas a encontrar la respuesta de lo que necesitas.
Solución:
[*]Un árbol de radix 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 árbol de base) almacena palabras completas.
[*]Ahora, asuma que tiene las palabras hello, hat y have. Para almacenarlos en un intentar, 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 de 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 radix toma menos memoria, pero es más difícil de implementar. De lo contrario, el caso de uso de ambos es prácticamente el mismo.
[*]Mi pregunta es si Trie estructura de datos y Radix Trie son lo mismo?
[*]En resumen, no. La categoría Radix Trie describe una categoría particular de Trie, pero eso no significa que todos los intentos sean intentos radix.
[*]Si ellos estan[n’t] lo mismo, entonces, ¿cuál es el significado de Radix trie (también conocida como Patricia Trie)?
[*]Supongo que querías escribir no son en tu pregunta, de ahí mi corrección.
[*]De manera similar, PATRICIA denota un tipo específico de intento de base, pero no todos los intentos de base son intentos de PATRICIA.
¿Qué es un trie?
[*]”Trie” describe una estructura de datos de árbol adecuada para su uso como asociación array, donde las ramas o los bordes corresponden a partes de un key. La definición de partes es bastante vago, aquí, porque diferentes implementaciones de intentos usan diferentes longitudes de bits para corresponder a los bordes. Por ejemplo, un trie binario tiene dos aristas por nodo que corresponden a un 0 o un 1, mientras que un trie de 16 vías tiene dieciséis aristas por nodo que corresponden a cuatro bits (o un dígito hexadecimal: 0x0 hasta 0xf).
[*]Este diagrama, obtenido de Wikipedia, parece representar un intento con (al menos) el keys ‘A’, ‘a’, ‘té’, ‘ted’, ‘diez’ y ‘posada’ insertados:
[*]
[*]Si este intento fuera a almacenar artículos para el keys ‘t’, ‘te’, ‘i’ o ‘in’ sería necesario que haya información adicional presente en cada nodo para distinguir entre nodos nulares y nodos con valores reales.
¿Qué es un radix trie?
[*]”Radix trie” parece describir una forma de trie que condensa prefix partes, como Ivaylo Strandjev describió en su respuesta. Considere que un trie de 256 vías que indexa el keys “sonríe”, “sonrió”, “sonríe” y “sonríe” con las siguientes static asignaciones:
root['s']['m']['i']['l']['e'][' '] = smile_item;
root['s']['m']['i']['l']['e']['d'][' '] = smiled_item;
root['s']['m']['i']['l']['e']['s'][' '] = smiles_item;
root['s']['m']['i']['l']['i']['n']['g'][' '] = smiling_item;
[*]Cada subíndice accede a un nodo interno. Eso significa recuperar smile_item, debe acceder a siete nodos. Ocho accesos a nodos corresponden a smiled_item y smiles_item, y de 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 un root que corresponde a ['s']['m']['i']['l'], se han optimizado cuatro accesos a nodos. Eso significa menos memoria y menos accesos a los nodos, lo cual es una muy buena indicación. La optimización se puede aplicar de forma recursiva para reducir la necesidad de acceder a bytes de sufijo innecesarios. Eventualmente, llegas a un punto en el que solo estás comparando diferencias entre la búsqueda key e indexado keys en ubicaciones indexadas por el trie. Este es un trie radical.
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 búsqueda key de “sonrisas” y un root.position de 4, accedemos 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" y "smiles", por lo que el próximo acceso será root["smiles"[5]]. Esto nos lleva a smiles_item, y el final de nuestro string. Nuestra búsqueda ha finalizado y se ha recuperado el elemento con solo tres accesos a nodos en lugar de ocho.
¿Qué es un ensayo PATRICIA?
[*]Un PATRICIA trie es una variante de radix tries para el que solo debería haber n nodos solían contener n elementos. En nuestro pseudocódigo de radix trie anteriormente demostrado, hay cinco nodos en total: root (que es un nodo nular; no contiene ningún valor real), root['e'], root['e']['d'], root['e']['s'] y root['i']. En un ensayo PATRICIA solo debería haber cuatro. Echemos un vistazo a cómo estos prefijos pueden diferir mirá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 momento, todos nuestros nodos tienen lo mismo prefix. smiled_node pertenece a smile_node[0]. La diferencia entre "smiled" y "smiles" ocurre en el bit 43, donde "smiles" tiene un bit ‘1’, entonces smiled_node[1] es smiles_node.
[*]En lugar de usar NULL como ramas y / o información interna adicional para indicar cuándo termina una búsqueda, las ramas enlazan hasta el árbol en algún lugar, por lo que una búsqueda termina cuando el desplazamiento para probar disminuye en lugar de aumentar. Aquí hay un diagrama simple de tal árbol (aunque PATRICIA realmente 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:
[*]
[*]Un algoritmo PATRICIA más complejo que involucra keys de longitud variante es posible, aunque algunas de las propiedades técnicas de PATRICIA se pierden en el proceso (es decir, que cualquier nodo contiene un común prefix con el nodo anterior):
[*]
[*]Al ramificarse 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 la realidad. Al menos una sucursal y como máximo k ramas (donde k es el número de bits en la búsqueda key) se siguen para localizar un artículo. Los nodos son diminuto, porque almacenan solo dos ramas cada una, lo que las hace bastante adecuadas para la optimización de la ubicación de la caché. Estas propiedades hacen de PATRICIA mi algoritmo favorito hasta ahora …
[*]Voy a acortar esta descripción aquí para reducir la gravedad de mi artritis inminente, pero si quieres saber más sobre PATRICIA puedes consultar libros como “El arte de la programación informática, volumen 3” de Donald Knuth. , o cualquiera de los “Algoritmos en su-idioma-favorito, partes 1-4” de Sedgewick.
[*]PRUEBA:
Podemos tener un esquema de búsqueda donde en lugar de comparar una búsqueda completa key con todo lo existente keys (como un esquema hash), también podríamos comparar cada carácter de la búsqueda key. Siguiendo esta idea, podemos construir una estructura (como se muestra a continuación) que tiene tres keys – “padre“,”lenguado“, y “taxi”.
[root]
...// | \...
|
c d
|
[*] [*]
...//|. ./|\... Fig-I
a a
/ /
[*] [*]
...//|.. ../|\...
/ /
B b d
/ /
[] [] []
(cab) (dab) (dad)
[*]Este es esencialmente un árbol M-ario con nodo interno, representado como [ * ] y nodo hoja, representado como [ ]. Esta estructura se llama intentar. 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 alfabetos ingleses en minúsculas az, R = 26; para alfabetos ASCII extendidos, R = 256 y para dígitos binarios / cadenas R = 2.
[*]TRIE compacto:
Normalmente, un nodo en un intentar usa un array con tamaño = R y, por lo tanto, provoca un desperdicio de memoria cuando cada nodo tiene menos bordes. Para eludir la preocupación por la memoria, se hicieron varias propuestas. Basado en esas variaciones intentar también se denominan “trie compacto” y “trie comprimido”. Si bien una nomenclatura consistente es rara, una versión más común de un compacto intentar se forma agrupando todos los bordes cuando los nodos tienen un solo borde. Usando este concepto, lo anterior (Fig-I) intentar con keys “Papá”, “dab” y “taxi” pueden tomar la forma siguiente.
[root]
...// | \...
|
cab da
|
[ ] [*] Fig-II
./|\...
|
b d
|
[] []
[*]Tenga en cuenta que cada uno de ‘c’, ‘a’ y ‘b’ es el único borde de su correspondiente nodo principal y, por lo tanto, están conglomerados en un solo borde “cab”. De manera similar, ‘d’ y a ‘se combinan en un solo borde etiquetado como “da”.
[*]Radix Trie:
El término base, en Matemáticas, significa la base de un sistema numérico, 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 base diez y el sistema binario es la base dos. 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 de representación subyacente, etiquetamos el concepto con el término “base”. Por ejemplo, “ordenación de base” para cierto algoritmo de ordenación. En la misma lgica, todas las variantes de intentar cuyas características (como profundidad, necesidad de memoria, tiempo de ejecución de búsqueda fallida / acertada, etc.) dependen de la base de los alfabetos subyacentes, podemos llamarlas “trie” de base. Por ejemplo, tanto un no compactado como un compactado intentar cuando usa alfabetos az, podemos llamarlo una base 26 intentar. Cualquier trie que use solo dos símbolos (tradicionalmente ‘0’ y ‘1’) se puede llamar una base 2 intentar. Sin embargo, de alguna manera mucha literatura restringió el uso del término “Radix Trie” solo para los compactos intentar.
[*]Preludio de PATRICIA Tree / Trie:
Sería interesante notar que incluso cadenas como keys se puede representar mediante alfabetos binarios. Si asumimos la codificación ASCII, entonces un key “Papá” se puede escribir en forma binaria escribiendo la representación binaria de cada carácter en secuencia, digamos como “011001000110000101100100”Escribiendo formas binarias de ‘d’, ‘a’ y ‘d’ secuencialmente. Usando este concepto, un intentar (con Radix Two) se puede formar. A continuación, representamos este concepto utilizando 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 Fig-III: Como se mencionó, para facilitar la descripció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, nuestro string keys “Papá”, “dab” y “taxi” se convierten en “110011”, “110001” y “100001” respectivamente. El intento 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 compactamos el binario anterior intentar (Fig-III) usando la compactación de un solo borde, tendría muchos menos nodos que los que se muestran arriba y, sin embargo, los nodos seguirían siendo más de 3, el número de keys contiene. Donald R. Morrison encontró (en 1968) una forma innovadora de utilizar binarios intentar para representar N keys usando solo N nodos y nombró esta estructura de datos PATRICIA. Su estructura trie básicamente eliminó los bordes simples (ramificación unidireccional); y al hacerlo, también se deshizo de la noción de dos tipos de nodos: los nodos internos (que no representan ningún key) y nodos de hojas (que representan keys). A diferencia de la lógica de compactación explicada anteriormente, este ensayo utiliza un concepto diferente en el que cada nodo incluye una indicación de cuántos bits de un key omitirse para tomar una decisión de ramificación. Otra característica más de su PATRICIA trie es que no almacena el keys – lo que significa que dicha estructura de datos no será adecuada para responder preguntas como, Listar todo keys que coinciden con un dado prefix, pero es bueno para encontrar si un key existe o no en el trie. No obstante, el término Patricia Tree o Patricia Trie, desde entonces, se ha utilizado en muchos sentidos diferentes pero similares, como, por ejemplo, para indicar un trie compacto. [NIST], o para indicar una base trie con base dos [as indicated in a subtle way in WIKI] etcétera.
[*]Prueba que puede que no sea una Radix Trie:
Trie de búsqueda ternaria (también conocido como árbol de búsqueda ternario) a menudo abreviado como TST es una estructura de datos (propuesta por J. Bentley y R. Sedgewick) que se parece mucho a un trie con ramificación de tres vías. Para tal árbol, cada nodo tiene un alfabeto característico ‘x’ de modo que la decisión de ramificación depende de si un carácter de un key es menor, igual o mayor que ‘x’. Debido a esta función de ramificació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 de (R-way) intentar, no tiene sus características influenciadas por R. Por ejemplo, la búsqueda perdida para TST es en (N) en contraposición Iniciar sesiónR(NORTE) para R-way Trie. Requisitos de memoria de TST, a diferencia de R-way intentar es NO una función de R también. Por lo tanto, debemos tener cuidado de llamar a un TST un radix-trie. Yo, personalmente, no creo que debamos llamarlo radix-trie ya que ninguna (hasta donde yo sé) de sus características está influenciada por la raíz, R, de sus alfabetos subyacentes.
[*]Si para ti ha resultado útil este post, sería de mucha ayuda si lo compartes con otros desarrolladores y nos ayudes a extender este contenido.