Quelle est la différence entre les structures de données trie et radix trie?

Les structures de données trie et radix trie sont-elles la même chose?

S'ils sont identiques, alors quelle est la signification de radix trie (AKA Patricia trie)?

Un arbre de base est une version compressée d'un trie. Dans un trie, sur chaque bord, vous écrivez une seule lettre, tandis que dans un arbre PATRICIA (ou arbre de base) vous stockez des mots entiers.

Maintenant, supposez que vous avez les mots hello, hatet have. Pour les stocker dans un trie , cela ressemblerait à:

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

Et vous avez besoin de neuf nœuds. J'ai placé les lettres dans les nœuds, mais en fait, ils étiquettent les bords.

Dans un arbre radix, vous aurez:

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

et vous n'avez besoin que de cinq nœuds. Dans l'image ci-dessus, les nœuds sont les astérisques.

Donc, dans l'ensemble, un arbre de base prend moins de mémoire , mais il est plus difficile à implémenter. Sinon, le cas d'utilisation des deux est à peu près le même.

Ma question est de savoir si la structure de données Trie et Radix Trie sont la même chose?

En bref, non. La catégorie Radix Trie décrit une catégorie particulière de Trie , mais cela ne signifie pas que tous les essais sont des essais radix.

S'ils ne sont [pas] les mêmes, alors quelle est la signification de Radix trie (alias Patricia Trie)?

Je suppose que vous vouliez écrire ne sont pas dans votre question, d'où ma correction.

De même, PATRICIA désigne un type spécifique de trie de base, mais tous les essais de base ne sont pas des essais de PATRICIA.

Qu'est-ce qu'un trie?

"Trie" décrit une structure de données arborescente appropriée pour être utilisée comme un tableau associatif, où les branches ou les arêtes correspondent à des parties d'une clé. La définition des parties est plutôt vague, ici, car différentes implémentations d'essais utilisent des longueurs de bits différentes pour correspondre aux arêtes. Par exemple, un trie binaire a deux arêtes par nœud qui correspondent à un 0 ou un 1, tandis qu'un trie à 16 voies a seize arêtes par nœud qui correspondent à quatre bits (ou un chiffre hexadécimal: de 0x0 à 0xf).

Ce diagramme, récupéré de Wikipedia, semble représenter un trie avec (au moins) les clés 'A', 'to', 'tea', 'ted', 'ten' et 'inn' insérées:

Si ce test devait stocker des éléments pour les clés «t», «te», «i» ou «in», il faudrait des informations supplémentaires présentes à chaque nœud pour faire la distinction entre les nœuds nuls et les nœuds avec des valeurs réelles.

Qu'est-ce qu'un trie radix?

"Radix trie" semble décrire une forme de trie qui condense les parties communes du préfixe, comme Ivaylo Strandjev l'a décrit dans sa réponse. Considérez un trie à 256 voies qui indexe les touches «sourire», «sourire», «sourire» et «sourire» en utilisant les affectations statiques suivantes:

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;

Chaque indice accède à un nœud interne. Cela signifie que pour récupérer smile_item, vous devez accéder à sept nœuds. Huit accès aux nœuds correspondent à smiled_itemet smiles_itemet neuf à smiling_item. Pour ces quatre éléments, il y a quatorze nœuds au total. Cependant, ils ont tous en commun les quatre premiers octets (correspondant aux quatre premiers nœuds). En condensant ces quatre octets pour créer un rootqui correspond à ['s']['m']['i']['l'], quatre accès aux nœuds ont été optimisés. Cela signifie moins de mémoire et moins d'accès aux nœuds, ce qui est une très bonne indication. L'optimisation peut être appliquée de manière récursive pour réduire le besoin d'accéder aux octets de suffixe inutiles. Finalement, vous arrivez à un point où vous ne comparez que les différences entre la clé de recherche et les clés indexées aux emplacements indexés par le trie. Ceci est un trie radix.

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

Pour récupérer des éléments, chaque nœud a besoin d'une position. Avec une clé de recherche de "sourires" et un root.positionde 4, nous accédons root["smiles"[4]], ce qui se trouve être root['e']. Nous stockons cela dans une variable appelée current. current.positionest 5, qui est l'emplacement de la différence entre "smiled"et "smiles", donc le prochain accès sera root["smiles"[5]]. Cela nous amène à smiles_item, et à la fin de notre chaîne. Notre recherche est terminée et l'élément a été récupéré, avec seulement trois accès aux nœuds au lieu de huit.

Qu'est-ce qu'un trie PATRICIA?

Un trie PATRICIA est une variante des essais radix pour lesquels il ne devrait y avoir que des nnœuds utilisés pour contenir des néléments. Dans notre pseudocode arborescente radix grossièrement démontré ci - dessus, il existe cinq nœuds au total: root(qui est un noeud arité, il ne contient pas de valeur réelle), root['e'], root['e']['d'], root['e']['s']et root['i']. Dans un essai PATRICIA, il ne devrait y en avoir que quatre. Voyons comment ces préfixes peuvent différer en les regardant en binaire, puisque PATRICIA est un algorithme binaire.

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 ...

Considérons que les nœuds sont ajoutés dans l'ordre où ils sont présentés ci-dessus. smile_itemest la racine de cet arbre. La différence, en gras pour la rendre légèrement plus facile à repérer, se situe dans le dernier octet de "smile", au bit 36. Jusqu'à ce point, tous nos nœuds ont le même préfixe. smiled_nodeappartient à smile_node[0]. La différence entre "smiled"et "smiles"se produit à peu 43, où "smiles"a un bit « 1 », alors smiled_node[1]est smiles_node.

Plutôt que d'utiliser des NULLbranches et / ou des informations internes supplémentaires pour indiquer quand une recherche se termine, les branches renvoient quelque part dans l'arborescence, de sorte qu'une recherche se termine lorsque le décalage à tester diminue au lieu d'augmenter. Voici un schéma simple d'un tel arbre (bien que PATRICIA soit vraiment plus un graphique cyclique, qu'un arbre, comme vous le verrez), qui a été inclus dans le livre de Sedgewick mentionné ci-dessous:

Un algorithme PATRICIA plus complexe impliquant des clés de longueur variable est possible, bien que certaines des propriétés techniques de PATRICIA soient perdues dans le processus (à savoir que tout nœud contient un préfixe commun avec le nœud précédent):

En créant des branches comme ça, il y a un certain nombre d'avantages: chaque nœud contient une valeur. Cela inclut la racine. En conséquence, la longueur et la complexité du code deviennent beaucoup plus courtes et probablement un peu plus rapides en réalité. Au moins une branche et au plus des kbranches (où kest le nombre de bits dans la clé de recherche) sont suivies pour localiser un élément. Les nœuds sont minuscules , car ils ne stockent que deux branches chacun, ce qui les rend assez adaptés à l'optimisation de la localisation du cache. Ces propriétés font de PATRICIA mon algorithme préféré jusqu'à présent ...

Je vais abréger cette description ici, afin de réduire la gravité de mon arthrite imminente, mais si vous voulez en savoir plus sur PATRICIA, vous pouvez consulter des livres tels que "The Art of Computer Programming, Volume 3" de Donald Knuth , ou l'un des "Algorithmes en {your-favorite-language}, parties 1-4" de Sedgewick.

TRIE:
Nous pouvons avoir un schéma de recherche où au lieu de comparer une clé de recherche entière avec toutes les clés existantes (comme un schéma de hachage), nous pourrions également comparer chaque caractère de la clé de recherche. En suivant cette idée, nous pouvons construire une structure (comme indiqué ci-dessous) qui a trois clés existantes - « papa », « dab » et « cab ».

         [root]
     ...// | \\...
           |  \
           c   d
           |    \
          [*]    [*]
      ...//|\.  ./|\\...        Fig-I
        a       a
       /       /
     [*]      [*]
 ...//|\..  ../|\\...
    /        /   \
   B        b     d
  /        /       \
 []       []       []

(cab)   (dab)     (dad)

Il s'agit essentiellement d'un arbre M-aire avec un nœud interne, représenté par [*] et un nœud feuille, représenté par []. Cette structure s'appelle un trie . La décision de branchement à chaque nœud peut être maintenue égale au nombre de symboles uniques de l'alphabet, disons R. Pour les alphabets anglais minuscules az, R = 26; pour les alphabets ASCII étendus, R = 256 et pour les chiffres / chaînes binaires R = 2.

Compact TRIE:
En règle générale, un nœud dans un trie utilise un tableau de taille = R et entraîne ainsi un gaspillage de mémoire lorsque chaque nœud a moins d'arêtes. Pour contourner le souci de mémoire, diverses propositions ont été faites. Sur la base de ces variations, les tries sont également appelés « trie compact » et « trie comprimé ». Bien qu'une nomenclature cohérente soit rare, une version la plus courante d'un trie compact est formée en regroupant toutes les arêtes lorsque les nœuds ont une seule arête. En utilisant ce concept, le trie ci-dessus (Fig-I) avec les touches «papa», «dab» et «cab» peut prendre la forme ci-dessous.

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

Notez que chacun des 'c', 'a' et 'b' est le seul bord pour son nœud parent correspondant et par conséquent, ils sont agglomérés en un seul bord «cab». De même, «d» et a »sont fusionnés en une seule arête étiquetée« da ».

Radix Trie:
Le terme radix , en mathématiques, signifie la base d'un système de nombres, et il indique essentiellement le nombre de symboles uniques nécessaires pour représenter n'importe quel nombre dans ce système. Par exemple, le système décimal est la base dix et le système binaire la base deux. En utilisant le même concept, lorsque nous souhaitons caractériser une structure de données ou un algorithme par le nombre de symboles uniques du système de représentation sous-jacent, nous étiquetons le concept avec le terme «radix». Par exemple, «tri de base» pour certains algorithmes de tri. Dans la même logique, toutes les variantes de triedont les caractéristiques (telles que la profondeur, le besoin de mémoire, le temps d'exécution de la recherche manquée / réussie, etc.) dépendent de la base des alphabets sous-jacents, nous pouvons les appeler radix «trie». Par exemple, un trie non compacté ainsi qu'un trie compacté lorsqu'il utilise des alphabets az, nous pouvons l'appeler un trie radix 26 . Tout trie qui n'utilise que deux symboles (traditionnellement «0» et «1») peut être appelé un trie de base 2 . Cependant, de nombreuses littératures ont limité l'utilisation du terme «Radix Trie» uniquement pour le trie compacté .

Prélude de PATRICIA Tree / Trie:
Il serait intéressant de noter que même les chaînes en tant que clés peuvent être représentées en utilisant des alphabets binaires. Si nous supposons un codage ASCII, alors une clé «papa» peut être écrite sous forme binaire en écrivant la représentation binaire de chaque caractère en séquence, par exemple « 01100100 01100001 01100100 » en écrivant des formes binaires de «d», «a» et 'd' séquentiellement. En utilisant ce concept, un trie (avec Radix Two) peut être formé. Ci-dessous, nous décrivons ce concept en utilisant une hypothèse simplifiée selon laquelle les lettres «a», «b», «c» et'd »proviennent d'un alphabet plus petit au lieu de ASCII.

Remarque pour la Fig-III: Comme mentionné, pour faciliter la représentation, supposons un alphabet avec seulement 4 lettres {a, b, c, d} et leurs représentations binaires correspondantes sont «00», «01», «10» et «11» respectivement. Avec cela, nos touches de chaîne «papa», «dab» et «cab» deviennent respectivement «110011», «110001» et «100001». Le trie pour cela sera comme indiqué ci-dessous sur la figure III (les bits sont lus de gauche à droite, tout comme les chaînes sont lues de gauche à droite).

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

PATRICIA Trie / Tree:
Si nous compactons le trie binaire ci-dessus (Fig-III) en utilisant un compactage à un seul bord, il aurait beaucoup moins de nœuds que ci-dessus et pourtant, les nœuds seraient toujours plus que les 3, le nombre de clés qu'il contient . Donald R. Morrison a trouvé (en 1968) une manière innovante d'utiliser le trie binaire pour représenter N clés en utilisant uniquement N nœuds et il a nommé cette structure de données PATRICIA. Sa structure trie s'est essentiellement débarrassée des arêtes simples (ramification à sens unique); et ce faisant, il s'est également débarrassé de la notion de deux types de nœuds - les nœuds internes (qui ne représentent aucune clé) et les nœuds feuilles (qui représentent des clés). Contrairement à la logique de compactage expliquée ci-dessus, son trie utilise un concept différent où chaque nœud comprend une indication du nombre de bits d'une clé à sauter pour prendre une décision de branchement. Encore une autre caractéristique de son trie PATRICIA est qu'il ne stocke pas les clés - ce qui signifie qu'une telle structure de données ne sera pas adaptée pour répondre à des questions comme, lister toutes les clés qui correspondent à un préfixe donné , mais est bonne pour trouver si une clé existe ou pas dans le trie. Néanmoins, le terme Patricia Tree ou Patricia Trie a, depuis lors, été utilisé dans de nombreux sens différents mais similaires, tels que, pour indiquer un trie compact [NIST], ou pour indiquer un trie radix avec radix deux [comme indiqué dans un subtil manière dans WIKI] et ainsi de suite.

Trie qui n'est peut-être pas un Radix Trie:
Ternary Search Trie (alias Ternary Search Tree) souvent abrégé en TST est une structure de données (proposée par J.Bentley et R. Sedgewick ) qui ressemble beaucoup à un trie avec branchement à trois voies. Pour un tel arbre, chaque nœud a un alphabet caractéristique «x» de sorte que la décision de branchement dépend du fait qu'un caractère d'une clé est inférieur, égal ou supérieur à «x». En raison de cette fonction de branchement à 3 voies fixe, il fournit une alternative efficace en mémoire pour trie, en particulier lorsque R (base) est très grand, comme pour les alphabets Unicode. Fait intéressant, le TST, contrairement au trie (R-way) , n'a pas ses caractéristiques influencées par R. Par exemple, la recherche manquée pour TST est ln (N)par opposition au log _R (N) pour R-way Trie. Les besoins en mémoire de TST, contrairement au trie R-way, ne sont PAS également fonction de R. Nous devons donc faire attention à appeler un TST un radix-trie. Personnellement, je ne pense pas que nous devrions l'appeler un radix-trie car aucune (autant que je sache) de ses caractéristiques n'est influencée par la racine, R, de ses alphabets sous-jacents.