data-structures
Trie (Arbre Préfixe / Arbre Radix)

Introduction à Trie

Vous êtes-vous déjà demandé comment fonctionnent les moteurs de recherche? Comment Google aligne-t-il des millions de résultats devant vous en quelques millisecondes? Comment une énorme base de données située à des milliers de kilomètres de vous trouve-t-elle des informations que vous recherchez et vous les renvoie? La raison derrière cela n'est possible qu'en utilisant un Internet plus rapide et des super-ordinateurs. Certains algorithmes de recherche hypnotisants et certaines structures de données fonctionnent derrière. L'un d'eux est Trie .

Trie , également appelé arborescence numérique et parfois arborescence radix ou préfixe (comme ils peuvent être recherchés par des préfixes), est une sorte d'arbre de recherche - une structure de données d'arborescence ordonnée utilisée pour stocker un ensemble dynamique ou un tableau associatif généralement des cordes. C'est l'une de ces structures de données facilement implémentables. Disons que vous avez une énorme base de données de millions de mots. Vous pouvez utiliser trie pour stocker ces informations et la complexité de la recherche de ces mots dépend uniquement de la longueur du mot recherché. Cela signifie qu'il ne dépend pas de la taille de notre base de données. N'est-ce pas incroyable?

Supposons que nous ayons un dictionnaire avec ces mots:

algo
algea
also
tom
to

Nous voulons stocker ce dictionnaire en mémoire de telle manière que nous puissions facilement trouver le mot que nous recherchons. L'une des méthodes impliquerait de trier les mots lexicographiquement - comment les dictionnaires réels stockent les mots. Ensuite, nous pouvons trouver le mot en effectuant une recherche binaire . Une autre méthode consiste à utiliser Prefix Tree ou Trie , en bref. Le mot «Trie» vient du mot Re trie val. Ici, préfixe désigne le préfixe de chaîne qui peut être défini comme ceci: Toutes les sous-chaînes pouvant être créées à partir du début d'une chaîne sont appelées préfixes. Par exemple: 'c', 'ca', 'cat' sont tous le préfixe de la chaîne 'cat'.

Maintenant, revenons à Trie . Comme son nom l'indique, nous allons créer un arbre. Au début, nous avons un arbre vide avec juste la racine:

Nous allons insérer le mot "algo" . Nous allons créer un nouveau noeud et nommer le bord entre ces deux noeuds «a» . A partir du nouveau nœud, nous allons créer un autre bord nommé «l» et le connecter à un autre nœud. De cette façon, nous allons créer deux nouvelles arêtes pour 'g' et 'o' . Notez que nous ne stockons aucune information dans les nœuds. Pour l'instant, nous ne considérerons que créer de nouvelles arêtes à partir de ces noeuds. Désormais, appelons une arête nommée 'x' - edge-x

Maintenant, nous voulons ajouter le mot «algea» . Nous avons besoin d'un edge-a de la racine, que nous avons déjà. Nous n'avons donc pas besoin d'ajouter de nouveaux avantages. De même, nous avons une arête allant de «a» à «l» et «l» à «g» . Cela signifie que "alg" est déjà dans le trie . Nous n'y ajoutons que edge-e et edge-a .

Nous ajouterons le mot «aussi» . Nous avons le préfixe 'al' de la racine. Nous ajouterons seulement «so» avec.

Ajoutons 'tom' . Cette fois, nous créons un nouveau bord à partir de root car nous n’avons aucun préfixe de tom créé auparavant.

Maintenant, comment devrions-nous ajouter «à» ? 'to' est complètement un préfixe de 'tom' , nous n'avons donc pas besoin d'ajouter de bord. Ce que nous pouvons faire, c'est que nous pouvons placer des marques de fin dans certains nœuds. Nous placerons des marques de fin dans les nœuds où au moins un mot est terminé. Le cercle vert indique la marque de fin. Le trie ressemblera à:

Vous pouvez facilement comprendre pourquoi nous avons ajouté les marques de fin. Nous pouvons déterminer les mots stockés dans trie. Les caractères seront sur les bords et les nœuds contiendront les marques de fin.

Maintenant, vous pourriez demander, quel est le but de stocker des mots comme ça? Disons que vous êtes invité à trouver le mot «alice» dans le dictionnaire. Vous traverserez le trie. Vous allez vérifier s'il y a un bord-a de la racine. Puis cochez la case «a» s'il y a un bord-l . Après cela, vous ne trouverez aucun edge-i , vous pouvez donc en conclure que le mot alice n'existe pas dans le dictionnaire.

Si on vous demande de trouver le mot "alg" dans le dictionnaire, vous traverserez root-> a , a-> l , l-> g , mais vous ne trouverez pas de nœud vert à la fin. Le mot n'existe donc pas dans le dictionnaire. Si vous recherchez «tom» , vous vous retrouverez dans un nœud vert, ce qui signifie que le mot existe dans le dictionnaire.

Complexité:

Le nombre maximum d'étapes nécessaires pour rechercher un mot dans un trie correspond à la longueur du mot recherché. La complexité est O (longueur) . La complexité pour l'insertion est la même. La quantité de mémoire nécessaire pour implémenter trie dépend de l'implémentation. Nous verrons une implémentation dans un autre exemple où nous pouvons stocker 10 ⁶ caractères (pas des mots, des lettres) dans un trie .

Utilisation de Trie:

• Pour insérer, supprimer et rechercher un mot dans le dictionnaire.
• Pour savoir si une chaîne est un préfixe d'une autre chaîne.
• Pour savoir combien de chaînes ont un préfixe commun.
• Suggestion de noms de contact dans nos téléphones en fonction du préfixe que nous saisissons.
• Découvrir la plus longue sous-chaîne commune de deux chaînes.
• Déterminer la longueur du «préfixe commun» pour deux mots utilisant «l'ancêtre commun le plus long»

Mise en place de Trie

Avant de lire cet exemple, il est fortement recommandé de lire d'abord Introduction à Trie .

L'une des manières les plus simples d'implémenter Trie consiste à utiliser la liste chaînée.

Nœud:

Les nœuds seront constitués de:

1. Variable pour la marque finale.
2. Pointeur Tableau au nœud suivant.

La variable End-Mark dénotera simplement s'il s'agit d'un point final ou non. Le tableau de pointeurs indiquera tous les bords possibles pouvant être créés. Pour les alphabets anglais, la taille du tableau sera de 26, car 26 bords au maximum peuvent être créés à partir d'un seul nœud. Au tout début, chaque valeur du tableau de pointeurs sera NULL et la variable de fin sera fausse.

Node:
Boolean Endmark
Node *next[26]
Node()
    endmark = false
    for i from 0 to 25
        next[i] := NULL
    endfor
endNode

Chaque élément du tableau suivant [] pointe vers un autre noeud. next [0] pointe sur le bord de partage du noeud -a , le prochain [1] pointe sur le noeud de partage edge-b , etc. Nous avons défini le constructeur de Node pour initialiser Endmark en tant que false et mettre NULL dans toutes les valeurs du tableau suivant [] .

Pour créer Trie , il faut d'abord instancier root . Ensuite, à partir de la racine , nous allons créer d'autres nœuds pour stocker des informations.

Insertion:

Procedure Insert(S, root):    // s is the string that needs to be inserted in our dictionary
curr := root
for i from 1 to S.length
    id := S[i] - 'a'
    if curr -> next[id] == NULL
        curr -> next[id] = Node()
    curr := curr -> next[id]
endfor
curr -> endmark = true

Ici nous travaillons avec az . Donc, pour convertir leurs valeurs ASCII en 0-25 , nous soustrayons la valeur ASCII de «a» . Nous vérifierons si le nœud actuel (curr) a un avantage pour le personnage en question. Si c'est le cas, nous passons au nœud suivant en utilisant ce bord, si ce n'est pas le cas, nous créons un nouveau nœud. À la fin, nous modifions la marque de valeur true.

Recherche:

Procedure Search(S, root)      // S is the string we are searching
curr := root
for i from 1 to S.length
    id := S[i] - 'a'
    if curr -> next[id] == NULL
        Return false
    curr := curr -> id
Return curr -> endmark

Le processus est similaire à insérer. À la fin, nous retournons la marque finale . Donc, si la marque est vraie, cela signifie que le mot existe dans le dictionnaire. Si c'est faux, le mot n'existe pas dans le dictionnaire.

C'était notre principale implémentation. Maintenant, nous pouvons insérer n'importe quel mot dans trie et le rechercher.

Effacement:

Parfois, nous devrons effacer les mots qui ne seront plus utilisés pour économiser de la mémoire. Pour cela, nous devons supprimer les mots non utilisés:

Procedure Delete(curr):       //curr represents the current node to be deleted
for i from 0 to 25
    if curr -> next[i] is not equal to NULL
        delete(curr -> next[i])
    delete(curr)               //free the memory the pointer is pointing to

Cette fonction va à tous les nœuds enfants de curr , les supprime et ensuite curr est supprimé pour libérer la mémoire. Si nous appelons delete (root) , cela supprimera tout le Trie .

Trie peut également être implémenté en utilisant Arrays .