Trie (informatique)
Ne doit pas être confondu avec Algorithme de tri.
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.
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
[modifier | modifier le code]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
[modifier | modifier le code]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).
Les structures de données de type trie sont très souvent utilisé pour la saisie prédictive ou l'auto-complétion de texte, et plus généralement, dans beaucoup d'algorithmes de recherche approximative[4]. Les tries rendent les recherches plus rapides, occupent moins d'espaces, spécialement quand l'ensemble des données est composés de chaines de caractères courtes, ce qui est le cas pour un correcteur orthographique ou syntaxique, pour faire des césures dans un éditeur de texte, ou encore, pour les algorithmes de recherche de préfixe long dans les routeurs [5],[6]:358.
Cependant, si le stockage des mots du dictionnaire est tout ce qui est requis (càd. qu'il n'est pas nécessaire de stocker de métadonnées associées à chaque mot), un automate à états finis acyclique déterministe minimal (DAFSA) (en) ou un arbre radix utilise moins d'espace de stockage qu'un trie. En effet, les DAFSA et les arbres radix peuvent compresser des branches identiques du trie qui correspondent aux mêmes suffixes (ou parties) de différents mots stockés. Les dictionnaires de chaînes sont également utilisés dans le traitement du langage naturel, comme la recherche du lexique d'un corpus[7]:73.
Variantes
[modifier | modifier le code]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
[modifier | modifier le code]Notes
[modifier | modifier le code]Références
[modifier | modifier le code]- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Trie » (voir la liste des auteurs).
- (en) trie, NIST
- René de la Briandais « File searching using variable length keys » ()
—Proc. Western J. Computer Conf. Cited by Brass. - Peter Brass, Advanced Data Structures, Cambridge University Press,
- Alfred V. Aho et Margaret J. Corasick, « Efficient String Matching: An Aid to Bibliographic Search », Communications of the ACM, vol. 18, no 6, , p. 333–340 (DOI 10.1145/360825.360855
, S2CID 207735784)
- Franklin Mark Liang, Word Hy-phen-a-tion By Com-put-er (thèse), Stanford University, (lire en ligne [archive du ])
- Reema Thareja, Data Structures Using C, Oxford University Press, , 2e éd. (ISBN 9780198099307, lire en ligne
), « Hashing and Collision »
- Miguel A. Martinez-Prieto, Nieves Brisaboa, Rodrigo Canovas, Francisco Claude et Gonzalo Navarro, « Practical compressed string dictionaries », Elsevier, vol. 56, , p. 73–108 (ISSN 0306-4379, DOI 10.1016/j.is.2015.08.008, lire en ligne)
Bibliographie
[modifier | modifier le code]- (en) Edward Fredkin (en), « Trie Memory », dans Communications of the ACM, vol. 3, n° 9, , p. 490-499
- Alexandre Guidet, Programmation Objet en langage C++, Éditions Ellipses, (ISBN 978-2-7298-3693-1), 364 pages
- Bjarne Stroustrup, Le langage C++ - 4e édition, Éditions Pearson Education France, 2003, (ISBN 978-2-7440-7003-7), 1098 pages
- Article sur les arbres sur developpez.com
