Il existe plusieurs façons de représenter les tries, correspondant à différents compromis entre l’utilisation de la mémoire et la vitesse des opérations. La forme de base est celle d’un ensemble lié de nœuds, où chaque nœud contient un tableau de pointeurs enfants, un pour chaque symbole de l’alphabet (ainsi pour l’alphabet anglais, on stockerait 26 pointeurs enfants et pour l’alphabet des octets, 256 pointeurs). C’est simple mais coûteux en termes de mémoire : en utilisant l’alphabet des octets (taille 256) et des pointeurs de quatre octets, chaque nœud nécessite un kilooctet de stockage, et lorsqu’il y a peu de chevauchement dans les préfixes des chaînes de caractères, le nombre de nœuds requis est approximativement la longueur combinée des chaînes de caractères stockées.:341 Dit autrement, les nœuds proches du bas de l’arbre ont tendance à avoir peu d’enfants et ils sont nombreux, donc la structure gaspille de l’espace en stockant des pointeurs nuls.
Le problème de stockage peut être atténué par une technique d’implémentation appelée réduction d’alphabet, par laquelle les chaînes originales sont réinterprétées comme des chaînes plus longues sur un alphabet plus petit. Par exemple, une chaîne de n octets peut alternativement être considérée comme une chaîne de 2n unités de quatre bits et stockée dans un trie avec seize pointeurs par nœud. Les recherches doivent visiter deux fois plus de nœuds dans le pire des cas, mais les besoins en stockage diminuent d’un facteur huit.:347-352
Une implémentation alternative représente un nœud comme un triple (symbole, enfant, suivant) et lie les enfants d’un nœud ensemble comme une liste singulièrement liée : enfant pointe vers le premier enfant du nœud, suivant vers l’enfant suivant du nœud parent. L’ensemble des enfants peut également être représenté comme un arbre de recherche binaire ; une instance de cette idée est l’arbre de recherche ternaire développé par Bentley et Sedgewick.:353
Une autre alternative afin d’éviter l’utilisation d’un tableau de 256 pointeurs (ASCII), comme suggéré précédemment, est de stocker le tableau d’alphabet comme un bitmap de 256 bits représentant l’alphabet ASCII, réduisant considérablement la taille des nœuds.
Essais binairesEdit
Les essais par bit sont à peu près les mêmes qu’un essai normal basé sur les caractères, sauf que les bits individuels sont utilisés pour traverser ce qui devient effectivement une forme d’arbre binaire. En général, les implémentations utilisent une instruction spéciale du CPU pour trouver très rapidement le premier bit activé dans une clé de longueur fixe (par exemple, l’intrinsèque __builtin_clz() de GCC). Cette valeur est ensuite utilisée pour indexer une table de 32 ou 64 entrées qui pointe vers le premier élément de la trie bit à bit avec ce nombre de bits zéro de tête. La recherche se poursuit ensuite en testant chaque bit suivant dans la clé et en choisissant child ou child de manière appropriée jusqu’à ce que l’élément soit trouvé.
Bien que ce processus puisse sembler lent, il est très localisé dans le cache et hautement parallélisable en raison de l’absence de dépendances de registre et donc, en fait, a d’excellentes performances sur les CPU modernes à exécution hors ordre. Un arbre rouge-noir, par exemple, est bien plus performant sur le papier, mais il n’est pas du tout adapté au cache et provoque de multiples blocages du pipeline et de la TLB sur les CPU modernes, ce qui fait que cet algorithme est lié à la latence de la mémoire plutôt qu’à la vitesse du CPU. En comparaison, un tri binaire accède rarement à la mémoire, et lorsqu’il le fait, il le fait uniquement en lecture, évitant ainsi les surcharges de cohérence du cache SMP. Par conséquent, il devient de plus en plus l’algorithme de choix pour le code qui effectue de nombreuses insertions et suppressions rapides, comme les allocateurs de mémoire (par exemple, les versions récentes du célèbre allocateur de Doug Lea (dlmalloc) et ses descendants). Le pire cas d’étapes pour la recherche est le même que les bits utilisés pour indexer les emplacements dans l’arbre.
Alternativement, le terme « trie bitwise » peut plus généralement se référer à une structure d’arbre binaire contenant des valeurs entières, les triant par leur préfixe binaire. Un exemple est le trie x-fast.
Compression des essaisEdit
Compresser le trie et fusionner les branches communes peut parfois produire des gains de performance importants. Cela fonctionne mieux dans les conditions suivantes :
- Le trie est (principalement) statique, de sorte qu’aucune insertion ou suppression de clé n’est nécessaire (par exemple, après la création en masse du trie).
- Seules des recherches sont nécessaires.
- Les nœuds du trie ne sont pas clés par des données spécifiques aux nœuds, ou les données des nœuds sont communes.
- L’ensemble total des clés stockées est très clairsemé dans leur espace de représentation (la compression est donc payante).
Par exemple, il peut être utilisé pour représenter des ensembles de bits clairsemés ; c’est-à-dire des sous-ensembles d’un ensemble énumérable fixe beaucoup plus grand. Dans ce cas, le tableau est codé par la position de l’élément binaire dans l’ensemble complet. La clé est créée à partir de la chaîne de bits nécessaire pour coder la position intégrale de chaque élément. De tels essais ont une forme très dégénérée avec de nombreuses branches manquantes. Après avoir détecté la répétition de motifs communs ou comblé les lacunes inutilisées, les nœuds feuilles uniques (chaînes de bits) peuvent être stockés et compressés facilement, ce qui réduit la taille globale du trie.
Cette compression est également utilisée dans la mise en œuvre des diverses tables de consultation rapide pour récupérer les propriétés des caractères Unicode. Il peut s’agir de tables de correspondance de casse (par exemple, pour la lettre grecque pi, de Π à π), ou de tables de consultation normalisant la combinaison des caractères de base et de combinaison (comme le a-umlaut en allemand, ä, ou le dalet-patah-dagesh-ole en hébreu biblique, דַּ֫). Pour de telles applications, la représentation s’apparente à la transformation d’une très grande table unidimensionnelle et éparse (par exemple, les points de code Unicode) en une matrice multidimensionnelle de leurs combinaisons, puis à l’utilisation des coordonnées dans l’hyper-matrice comme clé de chaîne d’une trie non compressée pour représenter le caractère résultant. La compression consistera alors à détecter et à fusionner les colonnes communes au sein de l’hyper-matrice pour comprimer la dernière dimension de la clé. Par exemple, pour éviter de stocker le point de code Unicode complet, à plusieurs octets, de chaque élément formant une colonne de la matrice, on peut exploiter les regroupements de points de code similaires. Chaque dimension de l’hyper-matrice stocke la position de départ de la dimension suivante, de sorte que seul le décalage (généralement un seul octet) doit être stocké. Le vecteur résultant est lui-même compressible lorsqu’il est également clairsemé, de sorte que chaque dimension (associée à un niveau de couche dans le trie) peut être compressée séparément.
Certaines implémentations prennent en charge une telle compression de données dans les essais dynamiques clairsemés et permettent les insertions et les suppressions dans les essais compressés. Cependant, cela a généralement un coût important lorsque les segments compressés doivent être divisés ou fusionnés. Un compromis doit être fait entre la compression des données et la vitesse de mise à jour. Une stratégie typique consiste à limiter la portée des recherches globales pour comparer les branches communes dans le trie clairsemé.
Le résultat d’une telle compression peut ressembler à une tentative de transformation du trie en un graphe acyclique dirigé (DAG), car la transformation inverse d’un DAG en un trie est évidente et toujours possible. Cependant, la forme du DAG est déterminée par la forme de la clé choisie pour indexer les nœuds, ce qui contraint à son tour la compression possible.
Une autre stratégie de compression consiste à « démêler » la structure de données en un tableau d’un seul octet.Cette approche élimine le besoin de pointeurs de nœuds, ce qui réduit considérablement les besoins en mémoire. Cela permet à son tour le mappage de la mémoire et l’utilisation de la mémoire virtuelle pour charger efficacement les données à partir du disque.
Une autre approche consiste à « emballer » le trie. Liang décrit une implémentation efficace en termes d’espace d’un trie empaqueté clairsemé appliqué à la césure automatique, dans lequel les descendants de chaque nœud peuvent être intercalés en mémoire.
Tentatives de mémoire externeEdit
Plusieurs variantes de trie conviennent pour maintenir des ensembles de chaînes de caractères en mémoire externe, y compris les arbres de suffixes. Une combinaison de trie et d’arbre B, appelée B-trie a également été suggérée pour cette tâche ; par rapport aux arbres de suffixes, ils sont limités dans les opérations prises en charge mais aussi plus compacts, tout en effectuant plus rapidement les opérations de mise à jour.