Trie

Mise en œuvre de la structure de données Trie dans différents langages de programmation

Implémentation de Trie en Python

class TrieNode : 
    def __init__(self) : self.children = collections.defaultdict(TrieNode) self.is_end = False

Utilisation de la structure de données Trie en Java

class TrieNode { public TrieNode[] children = new TrieNode[26] ; public boolean isEnd ; }

Guide étape par étape pour l'implémentation de Trie en Java

class Trie { TrieNode root ; Trie() { root = new TrieNode() ; } } Étape

void insert(String word) { TrieNode node = root ; for (int i=0 ; iTu suis systématiquement des schémas similaires pour créer d'autres méthodes. Par exemple, la fonction de recherche te demanderait de parcourir le Trie de la même manière que la fonction d'insertion mais renverrait un drapeau "isEnd" une fois que la fin du mot saisi est atteinte ; la fonction startsWith demanderait à nouveau de parcourir le Trie le long des caractères du préfixe saisi et renverrait vrai une fois que la fin du préfixe est atteinte, sans vérifier le drapeau "isEnd".

Remarque : l'index du tableau est déterminé par la valeur ASCII du caractère.
 La complexité temporelle constante des opérations de Trie découle de cette approche : quel que soit le nombre d'entrées d'une Trie, il suffit d'une complexité temporelle de \( O(k) \) pour vérifier si une chaîne de longueur \( k \) se trouve dans la Trie 
.
 Cela rend la triade extrêmement efficace pour certaines opérations. 
 Applications pratiques du Trie en informatique 
Les structures de données Trie ont diverses applications en informatique, en grande partie grâce à leur configuration unique et à leurs capacités de récupération rapide. En utilisant les Tries, on peut rapidement rectifier les questions liées à la recherche de chaînes de caractères, aux fonctions d'autocomplétion et aux mécanismes de vérification de l'orthographe. Les sections suivantes entrent dans les détails de ces applications et démontrent comment Trie simplifie considérablement ces opérations.
 Recherche avec Trie : l'algorithme de recherche de Trie 
L'un des principaux avantages de la structure de données Trie est son efficacité en matière de recherche. L'opération de recherche dans une Trie implique la traversée du nœud racine jusqu'à un nœud spécifique représentant une clé de recherche donnée (une chaîne de caractères). Il est intéressant de noter que les opérations de recherche dans une Trie dépendent de la longueur du mot, et non du nombre de mots stockés dans la Trie. Cela contraste avec d'autres structures de données où la complexité de la recherche dépend du nombre d'entrées dans la structure de données. Une opération de recherche dans une Trie suit la séquence suivante :
 
 Initialise la traversée au nœud racine. 
 Pour chaque caractère de la clé de recherche, 
 
 parcourir le nœud enfant correspondant au caractère actuel 
 
. Si aucun nœud enfant de ce type n'existe, renvoyer un échec ou "non trouvé" 
 
. 
 À la fin de la traversée de la clé de recherche, si le nœud actuel est marqué comme une fin de mot, renvoie un succès ou "trouvé" 
. 
  
 Sinon, si le nœud actuel n'est pas marqué comme une fin de mot, tu renvoies un échec ou "non trouvé" 
.


L'ensemble du processus peut être réalisé en \N( O(n) \N temps, où \N( n \N) est la longueur de la clé de recherche, ce qui représente une situation optimale pour les longues listes d'entrées.
 Un exemple d'algorithme de recherche en Trie 
Considérons une Trie stockant les mots "try", "tried", "tries", et "trie", et tu veux rechercher le mot "tries". Voici une forme concise de ce qui se passe :
function trie_search(root, key) { let level ; let length = key.length ; let index ; let pCrawl = root ; for (level = 0 ; level < length ; level++) { index = key[level] - 'a' ; if (!pCrawl.children[index]) return false ; pCrawl = pCrawl.children[index] ; } if (pCrawl != null && pCrawl.isEndOfWord) return true ; return false ; }
À l'aide de cette fonction, tu peux rechercher une structure Trie où chaque caractère d'un mot sert de clé dans le tableau children[] du nœud. Le processus se termine lorsqu'il rencontre la dernière lettre du mot recherché marquée comme étant la fin d'un mot (isEndOfWord == true) ou lorsqu'il explore tous les caractères sans trouver la clé.
 Utilisation de Trie dans les fonctions d'autocomplétion 
La fonction d'autocomplétion, très répandue dans le monde numérique actuel, est un excellent exemple de l'application pratique de Trie. De la recherche dans les moteurs de recherche sur le Web à la saisie dans les éditeurs de texte, l'autocomplétion permet d'économiser du temps et des efforts en prédisant les compléments de mots possibles en fonction de la saisie de l'utilisateur. L'élément central de la fonctionnalité d'autocomplétion est la structure de données de Trie. Lorsqu'un utilisateur tape certains caractères, le système parcourt la structure jusqu'à ce qu'il atteigne le dernier nœud de caractères tapés. Ce traitement est possible grâce à la propriété "préfixe" de Tries, où tous les descendants d'un nœud partagent un préfixe commun de la chaîne de caractères associée à ce nœud. Cela permet de modifier l'algorithme de recherche de Trie pour les fonctions d'autocomplétion, garantissant ainsi des compléments de mots efficaces et rapides.
 Trie dans les mécanismes de vérification orthographique 
Tout comme l'autocomplétion, les algorithmes de vérification orthographique bénéficient aussi largement des structures de données de Trie. Les correcteurs orthographiques peuvent rapidement détecter les fautes d'orthographe et suggérer des corrections, et une grande partie de cette efficacité provient de l'utilisation des structures de données Trie. Grâce à cette structure, l'existence même d'un mot dans un dictionnaire peut être rapidement validée, ce qui constitue la logique sous-jacente utilisée dans ces fonctions pour déterminer si ton orthographe est correcte ou non. Dans certains systèmes de vérification orthographique avancés, les Tries sont également utilisés pour suggérer des corrections aux mots mal orthographiés. Pour ce faire, ils recherchent dans la Trie les mots qui se trouvent à une certaine "distance" du mot mal orthographié (par exemple, en ajoutant, en supprimant ou en modifiant quelques caractères). Cette "distance" est souvent définie par un algorithme tel que l'algorithme de distance de Levenshtein. Dans un tel contexte, la rapidité et le caractère direct des Tries en font un excellent choix pour faciliter une vérification orthographique et une autocorrection rapides et efficaces.
 Comparaison entre Trie et d'autres structures de données 
Pour comprendre l'importance et le caractère unique de Trie, il s'avère utile de le comparer à d'autres structures de données courantes. Cette section examine Trie par rapport à hashmap et met en lumière la position de Trie en termes d'efficacité.
 Trie vs Hashmap : 
 Une comparaison détaillée 
Trie et Hashmap, deux structures de données puissantes, offrent chacune des avantages significatifs, selon les cas d'utilisation et la nature des données que tu traites. La décision entre les deux dépend notamment de certains paramètres clés, comme nous l'expliquons ci-dessous.
 Comprendre les différences entre Hashmap et Trie 
Hashmap, une collection non ordonnée de paires clé-valeur, offre des opérations de recherche, d'insertion et de suppression efficaces
.
Mais ces opérations dépendent fortement de la qualité de la fonction de hachage et du facteur de charge. Les hashmaps sont extrêmement flexibles, car ils permettent de stocker n'importe quel type de données - nombres, caractères, objets - en tant que clés et valeurs.
Cependant, les
hashmaps ne sont pas aptes à gérer les problèmes liés aux chaînes de caractères, en particulier les utilitaires basés sur les préfixes.
En revanche,
un Trie, également connu sous le nom d'arbre de préfixes, excelle lorsqu'il s'agit de traiter des chaînes de caractères
.
Les Tries stockent les caractères en tant qu'éléments, les chemins allant de la racine à la feuille constituant des chaînes de caractères de la collection. Cela rend les Trie efficaces pour de nombreuses opérations, telles que la recherche de préfixes, que les hashmaps ne possèdent pas de manière inhérente.



Voici une comparaison complète :