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

Question

Est-ce que les essai y radix trie les structures de données, c'est la même chose ?

Si ce n'est pas la même chose, alors quelle est la signification de radix trie (alias Patricia trie) ?

Answer 1

Un arbre radix est une version comprimée d'un trie. Dans un trie, sur chaque arête, on écrit une seule lettre, alors que dans un arbre PATRICIA (ou arbre radix), on stocke des mots entiers.

Maintenant, supposons que vous avez les mots hello , hat y have . Pour les stocker dans un essai ça ressemblerait à ça :

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

Et vous avez besoin de 9 noeuds. J'ai placé les lettres dans les noeuds, mais en fait elles é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, globalement, un arbre radix prend moins de mémoire mais elle est plus difficile à mettre en œuvre. Sinon, le cas d'utilisation des deux est à peu près le même.

Answer 2

Ma question est de savoir si Trie structure des données 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] identiques, alors quelle est la signification de Radix trie (aka 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 radix, mais tous les essais radix ne sont pas des essais PATRICIA.

---

Qu'est-ce qu'un trie ?

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

Ce diagramme, extrait de Wikipedia, semble représenter un tableau avec (au moins) les clés "A", "to", "tea", "ted", "ten", "i", "in" et "inn" insérées :

Si ce tableau devait stocker des éléments pour les clés "t" ou "te", des informations supplémentaires (les chiffres dans le diagramme) devraient être présentes à chaque nœud pour distinguer les nœuds nuls des nœuds ayant 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 des préfixes, comme Ivaylo Strandjev l'a décrit dans sa réponse. Considérons une trie à 256 voies qui indexe les clés "smile", "smiled", "smiles" et "smiling" 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 permet d'accéder à un nœud interne. Cela signifie que pour récupérer smile_item vous devez accéder à sept noeuds. Huit accès à des nœuds correspondent à smiled_item y smiles_item et 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 noeuds). En condensant ces quatre octets pour créer un noeud root qui correspond à ['s']['m']['i']['l'] Les accès à quatre 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 à des octets de suffixe inutiles. Au final, on arrive à un point où l'on ne compare plus que les différences entre la clé de recherche et les clés indexées à des emplacements indexés par le trie . Il s'agit d'une 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 les éléments, chaque nœud a besoin d'une position. Avec une clé de recherche de "sourires" et une position de root.position de 4, nous accédons root["smiles"[4]] qui se trouve être root['e'] . Nous le stockons dans une variable appelée current . current.position est 5, ce qui correspond à l'emplacement de la différence entre "smiled" y "smiles" donc le prochain accès sera root["smiles"[5]] . Ceci 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 test PATRICIA ?

Une trie PATRICIA est une variante des tries radix pour lesquelles il ne devrait jamais y avoir que des n les nœuds utilisés pour contenir n articles. Dans notre pseudocode radix trie grossièrement démontré ci-dessus, il y a cinq nœuds au total : root (qui est un noeud nul ; il ne contient aucune valeur réelle), root['e'] , root['e']['d'] , root['e']['s'] y root['i'] . Dans une épreuve de 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_item est la racine de cet arbre. La différence, mise en gras pour la rendre un peu plus facile à repérer, se trouve dans le dernier octet de "smile" au bit 36. Jusqu'à ce point, tous nos noeuds ont le même préfixe. smiled_node appartient à smile_node[0] . La différence entre "smiled" y "smiles" se produit au bit 43, où "smiles" a un bit '1', donc smiled_node[1] es smiles_node .

Plutôt que d'utiliser NULL comme des branches et/ou des informations internes supplémentaires pour indiquer que lorsqu'une recherche s'achève, les branches renvoient à l'origine. en haut l'arbre quelque part, de sorte qu'une recherche se termine lorsque le décalage à tester diminue plutôt que d'augmenter. Voici un diagramme simple d'un tel arbre (bien que PATRICIA soit en réalité plus un graphe 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 qui le précède) :

En se ramifiant de la sorte, on obtient un certain nombre d'avantages : Chaque nœud contient une valeur. Cela inclut la racine. Par conséquent, 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 k (où k est le nombre de bits de la clé de recherche) sont suivis pour localiser un élément. Les nœuds sont petit car ils ne stockent que deux branches chacun, ce qui les rend assez adaptés à l'optimisation de la localité du cache. Ces propriétés font de PATRICIA mon algorithme préféré jusqu'à présent...

Je vais abréger cette description, 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 "Algorithms in {your-favourite-language}, parts 1-4" de Sedgewick.

Answer 3

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 ", " tamponner ", et " cabine ".

         [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 de feuille, représenté par [ ]. Cette structure est appelée un essai . La décision de branchement à chaque nœud peut être maintenue égale au nombre de symboles uniques de l'alphabet, soit R. Pour les alphabets anglais minuscules a-z, R=26 ; pour les alphabets ASCII étendus, R=256 et pour les chiffres/chaînes binaires, R=2.

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

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

Notez que chacun de 'c', 'a', et 'b' est une arête unique pour son nœud parent correspondant et donc, ils sont conglomérés en une seule arête "cab". De même, 'd' et 'a' sont fusionnés en une seule arête appelée "da".

Radix Trie :
Le terme radix En mathématiques, le terme "base" désigne la base d'un système numérique et indique essentiellement le nombre de symboles uniques nécessaires pour représenter un nombre quelconque dans ce système. Par exemple, le système décimal est de dix radix, et le système binaire de deux radix. 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 marquons le concept avec le terme "radix". Par exemple, "radix sort" pour un certain algorithme de tri. Dans le même ordre d'idées, toutes les variantes de essai dont les caractéristiques (telles que la profondeur, le besoin en mémoire, le temps d'exécution des recherches, etc.) dépendent du radix des alphabets sous-jacents, nous pouvons les appeler des "trie's" radix. Par exemple, une trie non compactée et une trie compactée essai lorsqu'il utilise les alphabets a-z, nous pouvons l'appeler un radix 26 essai . Tout tableau qui n'utilise que deux symboles (traditionnellement '0' et '1') peut être appelé un radix 2. essai . Cependant, de nombreuses publications ont restreint l'utilisation du terme "Radix Trie" uniquement pour les racines compactes. essai .

Prélude à PATRICIA Tree/Trie :
Il serait intéressant de remarquer que même les chaînes de caractères en tant que clés peuvent être représentées à l'aide d'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 sous la forme " 01100100 01100001 01100100 "en écrivant les formes binaires de 'd', 'a', et 'd' séquentiellement. En utilisant ce concept, un essai (avec Radix deux) peut être formé. Nous décrivons ci-dessous ce concept en partant de l'hypothèse simplifiée que les lettres 'a', 'b', 'c' et 'd' proviennent d'un alphabet plus petit au lieu de l'ASCII.

Note pour la Fig-III : Comme mentionné, pour rendre la représentation facile, supposons un alphabet avec seulement 4 lettres {a,b,c,d} et leurs représentations binaires correspondantes sont "00", "01", "10" et "11" respectivement. Ainsi, nos chaînes de caractères "dad", "dab" et "cab" deviennent respectivement "110011", "110001" et "100001". Le tableau pour cela sera comme indiqué ci-dessous dans la Fig-III (les bits sont lus de gauche à droite tout comme les chaînes de caractères 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 on compacte le binaire ci-dessus essai (Fig-III) en utilisant le compactage à arête unique, il aurait beaucoup moins de nœuds que ce qui est montré ci-dessus et pourtant, les nœuds seraient toujours plus nombreux que les 3, le nombre de clés qu'il contient. Donald R. Morrison a trouvé (en 1968) une manière innovante d'utiliser les données binaires. essai pour représenter N clés en utilisant seulement N nœuds et il a nommé cette structure de données PATRICIA . Sa structure trie se débarrasse essentiellement des arêtes simples (branchement à sens unique) et, ce faisant, il se débarrasse également 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, sa trie utilise un concept différent où chaque nœud inclut une indication du nombre de bits d'une clé à sauter pour prendre la décision de branchement. Une autre caractéristique de son tri 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 celles-ci, liste toutes les clés qui correspondent à un préfixe donné mais il est bon pour trouver si une clé existe ou non dans la trie . Néanmoins, le terme Arbre de Patricia ou Trie de Patricia 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é d'une manière subtile dans WIKI] et ainsi de suite.

Trie qui peut ne pas être un Trie Radix :
Trie de recherche ternaire (alias arbre de recherche ternaire) souvent abrégé en TST est une structure de données (proposée par J. Bentley y R. Sedgewick ) qui ressemble beaucoup à un trie avec une ramification à trois voies. Pour un tel arbre, chaque nœud a un alphabet caractéristique "x", de sorte que la décision de branchement est déterminée par le fait qu'un caractère d'une clé est inférieur, égal ou supérieur à "x". Grâce à cette caractéristique de branchement fixe à trois voies, il constitue une alternative efficace en termes de mémoire pour les trie, en particulier lorsque R (radix) est très grand, comme pour les alphabets Unicode. Il est intéressant de noter que la CT, contrairement à (R-way) essai ne voit pas ses caractéristiques influencées par R. Par exemple, le manque de recherche pour TST est le suivant ln(N) comme opposé journal _R (N) pour R-way Trie. Besoins en mémoire de TST, contrairement à R-way essai es PAS une fonction de R également. Il faut donc être prudent pour appeler une CT une radix-trie. Personnellement, je ne pense pas que nous devrions l'appeler une radix-trie car aucune (pour autant que je sache) de ses caractéristiques n'est influencée par le radix, R, de ses alphabets sous-jacents.

Answer 4

Dans tries, la plupart des nœuds ne stockent pas de clés et ne sont que des sauts sur un chemin entre une clé et celles qui la prolongent. La plupart de ces sauts sont nécessaires, mais lorsque nous stockons de longs mots, ils ont tendance à produire de longues chaînes de nœuds internes, chacune avec un seul enfant. C'est la principale raison pour laquelle les essais nécessitent trop d'espace, parfois plus que les BST.

Les essais radix (alias arbres radix, alias arbres Patricia) sont basés sur l'idée que l'on peut d'une manière ou d'une autre compresser le chemin, par exemple après "nœud t intermédiaire", on pourrait avoir "hem" en un nœud, ou "idote" en un nœud.

Voici un graphique pour comparer trie et radix trie :

Le tableau original a 9 nœuds et 8 arêtes, et si nous supposons 9 octets pour une arête, avec une surcharge de 4 octets par nœud, cela signifie que

       9 * 4 + 8 * 9 = 108 bytes.

La triade comprimée de droite comporte 6 nœuds et 5 arêtes, mais dans ce cas, chaque arête porte une chaîne de caractères, et pas seulement un caractère ; cependant, nous pouvons simplifier l'opération en en comptabilisant séparément les références des arêtes et les étiquettes des chaînes. De cette façon, nous pourrions toujours 9 octets par arête (parce que nous inclurions l'octet de fin de chaîne dans le coût de l'arête). coût de l'arête), mais nous pourrions ajouter la somme des longueurs de chaîne comme troisième terme de l'expression finale. Le nombre total d'octets nécessaires est donné par

    6 * 4 + 5 * 9 + 8 * 1 = 77 bytes.

Pour cette simple épreuve, la version compressée nécessite 30% de moins mémoire.