Trie : l’arbre préfixe, pas à pas

Seize mots sont rangés dans un arbre, à raison d’une lettre par nœud. Ceux qui commencent de la même façon partagent leur début : car, card et cart passent par les mêmes nœuds c, a, r. Un double cercle signale la fin d’un mot. Saisissez un mot, choisissez une opération et suivez son déroulement.

Exemple résolu — Trie : l’arbre préfixe, pas à pas

Trie, recherche de “car” : lettres lues	3, mot présent
Table de hachage sans collision : lettres lues	6
Mots commençant par “car”	6 : car, card, care, careful, cargo, cart
Liste triée : sondages, puis mots lus à la suite	12
Table de hachage : mots lus (tous)	16
L’insertion de “car” ajoute	0 nœuds : 0 octets au trie, 0 à la liste
Nœuds du trie, un par préfixe distinct	30 pour 70 lettres (57,1 % partagées)
Trie à nœuds de 18 octets, racine comprise	558

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Leçon

La théorie — Trie : l’arbre préfixe, pas à pas

Un trie, ou arbre préfixe, représente un ensemble de mots par un arbre dont chaque nœud correspond à un préfixe distinct. La racine représente le préfixe vide. Chaque arête porte une lettre : les lettres du chemin allant de la racine à un nœud forment le préfixe de ce nœud. Celui-ci est marqué lorsque son préfixe constitue un mot stocké. Les mots qui ont un début commun partagent ainsi une partie du chemin. Une recherche suit les lettres du mot à partir de la racine ; une recherche par préfixe rejoint le nœud du préfixe, puis recense les nœuds marqués de son sous-arbre. Edward Fredkin a nommé cette structure en 1960, à partir du mot anglais retrieval. Il souhaitait que trie se prononce comme l’anglais tree.

Ce que signifie chaque symbole

W: le nombre de mots dans la liste
L: le nombre total de lettres de ces mots
N: le nombre de nœuds, un par préfixe distinct, sans compter la racine

Suppose: Lettres minuscules de a à z, un octet par lettre, pointeurs de 64 bits. Aucune des deux structures ne comporte d’octets d’alignement ni de surcoût lié à l’allocateur de mémoire. Pour la recherche dichotomique, chaque paire de lettres comparées est comptée ; la comparaison s’arrête à la première différence. Atteindre la fin d’un mot ne coûte rien. La table de hachage est supposée n’avoir aucune collision : c’est son cas le plus favorable. Avec les nœuds de 18 octets, les fils sont rangés dans l’ordre alphabétique. Leur parcours s’arrête donc dès qu’il dépasse la lettre recherchée.

La recherche dichotomique lit c, a, r quatre fois ; le trie, une seule 🖖

Cliquez sur Chercher car. Le trie suit une lettre par étape et trouve la marque de fin de mot de car : 3 lettres lues. Sur les mêmes seize mots triés, la recherche dichotomique sonde catch, careful, card et car. Tous commencent par ca : chaque comparaison lit donc 3 lettres avant de déterminer la suite de la recherche, soit 12 au total. Une table de hachage lit les 3 lettres pour calculer un emplacement, puis 3 autres pour vérifier le mot qui s’y trouve : 6. Pour rechercher l’ensemble des seize mots stockés, le trie lit 70 lettres, la table de hachage 140 et la recherche dichotomique 169. Les débuts communs qui permettent au trie d’économiser des nœuds allongent les comparaisons de la recherche dichotomique. Stockez les 17 576 chaînes de trois lettres, de aaa à zzz : la recherche dichotomique doit lire en moyenne 26,4 lettres pour en trouver une ; le trie en lit toujours 3.

Une liste triée permet aussi l’autocomplétion. Une table de hachage doit lire tous les mots 🖖

Cliquez sur Mots commençant par car. Le trie suit c, a, r, puis visite les 8 nœuds situés sous car : 11 nœuds au total, dont 6 portent une marque de fin de mot. Ni dog, ni plan, ni les autres branches ne sont parcourus. Une liste triée permet elle aussi de limiter la recherche : les mots commençant par car y sont consécutifs. La recherche dichotomique trouve le premier en 5 sondages. La lecture se poursuit ensuite dans l’ordre, recueille les 6 mots et s’arrête à cat, le premier qui ne convient pas : 12 mots lus. Une table de hachage répartit car, card et cargo dans des emplacements sans rapport entre eux. Elle doit donc lire les 16 mots et les tester chacun. Pour ajouter un mot, le trie prend l’avantage sur la liste triée. Cliquez sur Insérer carpet : le trie ajoute 3 nœuds sans rien déplacer, tandis que la liste triée décale les pointeurs de 11 mots d’une position pour faire de la place.

Même avec 40 lettres partagées sur 70, le trie occupe 2,6 fois la place de la liste 🖖

Les seize mots comptent 70 lettres. Le trie les stocke dans 30 nœuds, car car, card, care et les autres ne stockent qu’une fois leurs lettres communes c, a, r. Mais un nœud occupe plus de place qu’une lettre. Dans la représentation compacte, chaque nœud contient un octet pour sa lettre, un octet pour la marque de fin de mot et deux pointeurs de 8 octets, vers son premier fils et son frère suivant : 18 octets. Avec la racine, les 31 nœuds occupent 558 octets. La simple liste utilise un octet par lettre, plus un octet de fin et un pointeur de 8 octets par mot : 214 octets. Si chaque nœud contient un pointeur pour chaque lettre de l’alphabet, chaque étape se réduit à un accès dans un tableau. Le trie occupe alors 6 479 octets, 30 fois la place de la liste. Avec des mots d’au plus 14 lettres, comme ici, l’ajout d’un mot coûte moins cher au trie seulement s’il ne crée aucun nœud, comme plan dans un trie contenant déjà planet, ou s’il crée un seul nœud et compte au moins 10 lettres. La représentation compacte a aussi un coût en temps : pour trouver chaque lettre, elle parcourt les nœuds frères. La recherche de doorbell exige alors 10 comparaisons, une de plus que la recherche dichotomique.

Problème entièrement résolu

Combien de lettres faudrait-il partager pour que le trie occupe moins de place ? 4 étapes
Cliquez sur Mots longs : 85 lettres tiennent dans 21 nœuds, les trois quarts sont partagées, et le trie à nœuds de 18 octets occupe encore 396 octets, contre 157 pour la liste. Parmi les listes dont tous les mots ont k lettres, celle qui contient tous les mots possibles est la plus favorable au trie. Avec les coûts en octets retenus ici, quelle est la plus petite valeur de k pour laquelle ce trie occupe moins de place que la simple liste ?

Ouvrez ce problème dans l'outil
1. Dans l’exemple : 21 nœuds et la racine, soit 22 × 18 = 396 octets. La liste stocke 85 lettres et, pour chacun de ses 8 mots, un octet de fin et un pointeur de 8 octets : 85 + 9 × 8 = 157.
  
  $22 \times 18 = 396, 85 + 9 \times 8 = 157$
2. L’ensemble des chaînes de k lettres compte 26^k mots de k lettres chacun. La liste occupe donc (k + 9) × 26^k octets.
  
  $list = (k + 9) \cdot 2 6^{k}$
3. Le trie a besoin d’un nœud pour chaque chaîne de 1 à k lettres : 26 + 26² + … + 26^k, soit un peu moins de 26/25 × 26^k. En ajoutant la racine et en multipliant par 18, on obtient un coût légèrement inférieur à 18,72 × 26^k octets.
  
  $N = 26 + 2 6^{2} + \dots + 2 6^{k} = \frac{26}{25} (2 6^{k} - 1), 18 (N + 1) < 18.72 \cdot 2 6^{k}$
4. La liste occupe donc plus de place dès que k + 9 dépasse 18,72, ce qui se produit pour la première fois à k = 10. À k = 9, le trie occupe 4,0 % de plus que la liste ; à k = 10, il occupe 1,5 % de moins.
  
  $k + 9 > 18.72 ⟺ k \geq 10 : \frac{trie}{list} = 1.040 (k = 9), 0.985 (k = 10)$
Réponse

Dix lettres, à condition que la liste contienne les 26¹⁰ mots possibles, soit environ 1,4 × 10¹⁴ mots. Avec des nœuds de 209 octets, le même calcul exige que k + 9 dépasse environ 217 : il faut des mots de 209 lettres.

$k = 10, 2 6^{10} \approx 1.4 \times 1 0^{14} words$

Parcours

Ce qu’une structure de données rend peu coûteux

Références (3)

The name, its origin in "retrieval", and Fredkin's intended pronunciation, quoted in the definition: Paul E. Black, "trie", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., NIST, entry modified 12 February 2019.
The paper that named the structure: Edward Fredkin, "Trie memory," Communications of the ACM 3(9), September 1960, pp. 490–499.
The earlier description of searching on letter-by-letter keys: René de la Briandais, "File searching using variable length keys," Papers presented at the Western Joint Computer Conference, San Francisco, 3–5 March 1959, pp. 295–298.

Par l’équipe 42Math · Vérifié sur des sources publiées. Corrections bienvenues.