Trie (informatique)

En informatique, un ou une trie[n 1] (prononcé [ˈtriː] ou [ˈtraɪ][n 2]) ou arbre préfixe, est une structure de données ayant la forme d'un arbre enraciné. Il est utilisé pour stocker une table associative où les clés sont généralement des chaînes de caractères. Contrairement à un arbre binaire de recherche, aucun nœud dans le trie ne stocke la chaîne à laquelle il est associé. C'est la position du nœud dans l'arbre qui détermine la chaîne correspondante.

Ne doit pas être confondu avec Algorithme de tri.

Un trie pour les clés "A", "to", "tea", "ten", "ted", "i", "in", et "inn".

Pour tout nœud, ses descendants ont en commun le même préfixe. La racine est associée à la chaîne vide. Des valeurs ne sont pas attribuées à chaque nœud, mais uniquement aux feuilles et à certains nœuds internes se trouvant à une position qui désigne l'intégralité d'une chaîne correspondant à une clé.

Le terme de trie vient de l'anglais retrieval[1], signifiant extraction, recherche.


Origine

Les tries ont été décrits pour la première fois par l'américain René de la Briandais en 1959[2],[3]. Le terme trie a été inventé deux ans plus tard par Edward Fredkin, qui le prononce [ˈtriː], d’après la deuxième syllabe du mot anglais “retrieval”. Cependant beaucoup d'auteurs anglophones le prononcent [ˈtraɪ] (comme “try”), afin de le distinguer oralement de “tree”.

Applications

Les applications d'un trie sont nombreuses. Cette structure de données peut servir à implémenter un tableau associatif ou un set, à trouver des redondances dans certains algorithmes de compression (par exemple dans les algorithmes de compression par dictionnaire à fenêtre glissante comme LZ77), à implémenter des algorithmes de correction orthographique, de complétion automatique, de recherche préfixe, suffixe ou approximative…

Variantes

Il existe de nombreuses variantes de trie, parmi lesquelles :

  • l'arbre préfixe, qu'on appelle souvent « trie » sans plus de précision ;
  • l'arbre suffixe, qui stocke tout simplement les clefs dans l'autre sens ;
  • l'arbre radix, arbre PATRICIA ou arbre crit-bit qui est plus compact en mémoire en regroupant plusieurs nœuds d'un trie équivalent en un seul.

Notes et références

Notes
  1. Le terme vient de retrievable memory, mais l'usage dans la littérature francophone est d'utiliser le masculin
  2. À l'origine [ˈtriː] comme dans retrievable, mais la plupart du temps [ˈtraɪ][1]

Références
  1. (en) trie, NIST
  2. René de la Briandais (1959). « File searching using variable length keys » dans Proc. Western J. Computer Conf. : 295–298 p.. Cited by Brass.
  3. Peter Brass, Advanced Data Structures, Cambridge University Press,

Bibliographie
  • Portail de l'informatique théorique
  • Portail de la programmation informatique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.