Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Trie (informatique)
Résumé
thumb|250px|Un trie pour les clés "A", "to", "tea", "ten", "ted", "i", "in", et "inn".
En informatique, un ou une trie (prononcé ou ) 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, signifiant extraction, recherche.
Les tries ont été décrits pour la première fois par l'américain René de la Briandais en 1959. Le terme trie a été inventé deux ans plus tard par Edward Fredkin, qui le prononce , d’après la deuxième syllabe du mot anglais “retrieval”. Cependant beaucoup d'auteurs anglophones le prononcent (comme “try”), afin de le distinguer oralement de “tree”.
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...
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Cours associés (1)
CS-250: Algorithms I
The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma
Séances de cours associées (7)
Compression: Inégalité de Kraft
Explique la compression et l'inégalité Kraft dans les codes et les séquences.
Algorithmes récursifs : Induction et tri
Couvre l'induction, la récursion, les algorithmes de tri, et la complexité du tri de fusion en informatique.
Récupération d'information: Indexation et récupération
Couvre les techniques d'indexation, les algorithmes de récupération distribués et les défis dans l'indexation web à grande échelle.
Publications associées (11)
Concepts associés (10)
Arbre (théorie des graphes)
En théorie des graphes, un arbre est un graphe acyclique et connexe. Sa forme évoque en effet la ramification des branches d'un arbre. Par opposition aux arbres simples, arbres binaires, ou arbres généraux de l'analyse d'algorithme ou de la combinatoire analytique, qui sont des plongements particuliers d'arbres (graphes) dans le plan, on appelle parfois les arbres (graphes) arbres de Cayley, car ils sont comptés par la formule de Cayley. Un ensemble d'arbres est appelé une forêt.
Substring
In formal language theory and computer science, a substring is a contiguous sequence of characters within a string. For instance, "the best of" is a substring of "It was the best of times". In contrast, "Itwastimes" is a subsequence of "It was the best of times", but not a substring. Prefixes and suffixes are special cases of substrings. A prefix of a string is a substring of that occurs at the beginning of ; likewise, a suffix of a string is a substring that occurs at the end of .
Algorithme de recherche de sous-chaîne
vignette|Illustration de la recherche de la sous-chaîne "long des" dans la première strophe du poème Chanson d'automne de Paul Verlaine. En algorithmique du texte, un algorithme de recherche de sous-chaîne est un type d'algorithme de recherche qui a pour objectif de trouver une chaîne de caractères dans un texte. Le problème de recherche d'une sous-chaîne intervient dans beaucoup d'applications.