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

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

Si no son iguales, ¿cuál es el significado de radix trie (también conocido como Patricia trie)?

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, supongamos que tiene las palabras hello, haty 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 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 base requiere 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 la estructura de datos de 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.

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

Supongo que tu intención de escribir no está 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 una matriz asociativa, donde las ramas o los bordes corresponden a partes de una clave. La definición de partes es bastante vaga, aquí, 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 hasta 0xf).

Este diagrama, obtenido de Wikipedia, parece representar un trie con (al menos) las claves 'A', 'a', 'té', 'ted', 'diez' e 'posada' insertadas:

Si este intento fuera a almacenar elementos para las claves 't', 'te', 'i' o 'in', se necesitaría 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 partes de prefijos comunes, como Ivaylo Strandjev describió en su respuesta. Considere que un trie de 256 vías que indexa las teclas "sonríe", "sonrió", "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 accede a un nodo interno. Eso significa que para recuperar smile_item, debe acceder a siete nodos. Ocho accesos a nodos corresponden a smiled_itemy 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 un rootque corresponda ['s']['m']['i']['l'], se han optimizado los accesos de cuatro 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, llega a un punto en el que solo está comparando las diferencias entre la clave de búsqueda y las claves indexadas 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 clave de búsqueda de "sonrisas" y una root.positionde 4, accedemos root["smiles"[4]], que resulta ser root['e']. Almacenamos esto en una variable llamada current. current.positiones 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 al smiles_itemfinal de nuestra cadena. Nuestra búsqueda ha finalizado y se ha recuperado el elemento con solo tres accesos a nodos en lugar de ocho.

¿Qué es un PATRICIA trie?

Un PATRICIA trie es una variante de radix tries para el cual solo debería haber nnodos usados ​​para contener nelementos. En nuestro radix trie pseudocódigo 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 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_itemes 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_nodepertenece a smile_node[0]. La diferencia entre "smiled"y "smiles"ocurre en el bit 43, donde "smiles"tiene un bit '1', también lo smiled_node[1]es smiles_node.

En lugar de usar NULLcomo ramas y / o información interna adicional para indicar cuándo termina una búsqueda, las ramas enlazan una copia de seguridad del á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 dicho á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 mencionado a continuación:

Es posible un algoritmo PATRICIA más complejo que involucra 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 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 realidad. Se sigue al menos una rama y la mayoría de las kramas (donde kestá el número de bits en la clave de búsqueda) para localizar un elemento. Los nodos son pequeños , porque 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 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.

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 llaves existentes: " papá ", " dab " y " cabina ".

         [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 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 alfabetos ingleses en minúsculas az, R = 26; para alfabetos ASCII extendidos, R = 256 y para dígitos binarios / cadenas R = 2.

TRIE compacto: por lo
general, un nodo en un trie usa una matriz 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. Según esas variaciones, los trie 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 trie compacto se forma agrupando todos los bordes cuando los nodos tienen un solo borde. El uso de este concepto, el de arriba (fig-I) trie con las teclas “padre”, “DAB”, y “cabina” puede tomar siguiente formulario.

         [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 radix , 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 un 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 línea de lógica, todas las variantes de triecuyas 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, un trie no compactado así como un trie compactado cuando usa alfabetos az, podemos llamarlo un trie de base 26 . Cualquier trie que use solo dos símbolos (tradicionalmente '0' y '1') se puede llamar un trie de base 2 . Sin embargo, de alguna manera muchas publicaciones restringieron el uso del término “Radix Trie” solo para el trie compactado .

Preludio de PATRICIA Tree / Trie:
Sería interesante notar que incluso las cadenas como claves se pueden representar usando alfabetos binarios. Si asumimos la codificación ASCII, entonces una clave "papá" se puede escribir en forma binaria escribiendo la representación binaria de cada carácter en secuencia, digamos " 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, 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, nuestras teclas de cadena "papá", "dab" y "cab" 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 / Tree:
Si compactamos el trie binario anterior (Fig-III) usando 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, la cantidad de claves que contiene . Donald R. Morrison encontró (en 1968) una forma innovadora de usar trie binario para representar N claves usando solo N nodos y llamó a esta estructura de datos PATRICIA. Su estructura trie esencialmente eliminó los bordes simples (ramificación unidireccional); y al hacerlo, también se deshizo de la noción de dos tipos de nodos: nodos internos (que no representan ninguna clave) y nodos hoja (que representan claves). 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 una clave se deben omitir para tomar una decisión de ramificación. Otra característica más de su prueba 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. No obstante, el término Patricia Tree o Patricia Trie, desde entonces, se ha utilizado en muchos sentidos diferentes pero similares, como para indicar un trie compacto [NIST], o para indicar un trie de radix con radix dos [como se indica en un sutil en WIKI] y así sucesivamente.

Trie que puede no ser un Radix Trie:
Ternary Search Trie (también conocido como Ternary Search Tree) 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 dicho á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 una clave 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 del trie (vía R) , no tiene sus características influenciadas por R. Por ejemplo, el error de búsqueda para TST es ln (N)a diferencia de log _R (N) para R-way Trie. Los requisitos de memoria de TST, a diferencia de R-way trie, NO es una función de R también. Así que debemos tener cuidado de llamar a un TST un radix-trie. Personalmente, no creo que debamos llamarlo radix-trie ya que ninguna (hasta donde yo sé) de sus características está influenciada por la radix, R, de sus alfabetos subyacentes.