La structure de données Trie (arborescence de préfixes)

Un Trie, (également connu sous le nom d'arborescence de préfixes) est un type d'arbre spécial utilisé pour stocker des structures de données associatives

Un trie (prononcé try) tire son nom de re trie val - sa structure en fait un algorithme de correspondance stellaire.

Le contexte

Write your own shuffle method to randomly shuffle characters in a string. 
Use the words text file, located at /usr/share/dict/words, and your shuffle method to create an anagram generator that only produces real words.
Given a string as a command line argument, print one of its anagrams. 

Ce défi m'a été présenté cette semaine à la Product Academy de Make School.

Les mots du fichier texte sont séparés par de nouvelles lignes. Son formatage facilite grandement la mise en place des mots dans une structure de données. Pour l'instant, je les stocke dans une liste - chaque élément étant un seul mot du fichier.

Une approche à ce défi consiste à:

  • mélanger au hasard les caractères de la chaîne
  • ensuite, comparez-le à tous les mots qui se trouvaient dans / usr / share / dict / words pour vérifier que c'est un vrai mot.

Cependant, cette approche nécessite que je vérifie que les caractères mélangés au hasard dans la nouvelle chaîne correspondent à l'un des 235 887 mots de ce fichier - cela signifie 235 887 opérations pour chaque chaîne que je souhaite vérifier comme un mot réel.

C'était une solution inacceptable pour moi. J'ai d'abord recherché des bibliothèques qui avaient déjà été implémentées pour vérifier si des mots existaient dans une langue, et j'ai trouvé pyenchant. J'ai d'abord relevé le défi en utilisant la bibliothèque, en quelques lignes de code.

def generateAnagram(string, language="en_US"): languageDict = enchant.Dict(language) numOfPossibleCombinationsForString = math.factorial(len(string)) for i in range(0, numOfPossibleCombinationsForString): wordWithShuffledCharacters = shuffleCharactersOf(string)
 if languageDict.check(wordWithShuffledCharacters): return wordWithShuffledCharacters return "There is no anagram in %s for %s." % (language, string)

L'utilisation de quelques fonctions de bibliothèque dans mon code était une solution rapide et facile. Cependant, je n'ai pas beaucoup appris en trouvant une bibliothèque pour résoudre le problème à ma place.

J'étais convaincu que la bibliothèque n'utilisait pas l'approche que j'ai mentionnée plus tôt. J'étais curieux et fouillé dans le code source - j'ai trouvé un trie.

Trie

Un trie stocke les données par «étapes». Chaque étape est un nœud dans le trie.

Le stockage de mots est un cas d'utilisation parfait pour ce type d'arbre, car il existe un nombre fini de lettres qui peuvent être assemblées pour former une chaîne.

Chaque étape, ou nœud, dans un tri de langue représentera une lettre d'un mot. Les étapes commencent à bifurquer lorsque l'ordre des lettres diffère des autres mots du trie ou lorsqu'un mot se termine.

J'ai créé un trie à partir de répertoires sur mon bureau pour visualiser la descente à travers les nœuds. Ceci est un trie qui contient deux mots: pomme et application.

Notez que la fin d'un mot est indiquée par un '$'. J'utilise «$» car c'est un caractère unique qui ne sera présent dans aucun mot ni dans aucune langue.

Si je devais ajouter le mot «ouverture» à ce trie, je bouclerais sur les lettres du mot «ouverture» tout en abaissant simultanément les nœuds du trie. Si la lettre existe en tant qu'enfant du nœud actuel, descendez-y. Si la lettre n'existe pas en tant qu'enfant du nœud actuel, créez-la, puis descendez-y. Pour visualiser ces étapes à l'aide de mes répertoires:

En descendant le trie, les deux premières lettres «d'ouverture» sont déjà présentes dans le trie, alors je descends dans ces nœuds.

La troisième lettre, «e», cependant, n'est pas un enfant du nœud «p». Un nouveau nœud est créé pour représenter la lettre «e», en partant des autres mots du trie. De nouveaux nœuds pour les lettres qui suivent sont également créés.

Pour générer un trie à partir d'un fichier de mots, ce processus se produira pour chaque mot, jusqu'à ce que toutes les combinaisons pour chaque mot soient stockées.

Vous pensez peut-être: «Attendez, cela ne prendra-t-il pas vraiment longtemps pour générer le trie à partir de ce fichier texte contenant 235 887 mots? Quel est l'intérêt de boucler sur chaque caractère de chaque mot? "

Oui, itérer sur chaque caractère de chaque mot pour générer un tri prend un certain temps. Cependant, le temps nécessaire pour créer le trie en vaut la peine - car pour vérifier si un mot existe dans le fichier texte, il faut au plus autant d'opérations que la longueur du mot lui-même . Bien mieux que les 235 887 opérations qu'il allait entreprendre auparavant.

J'ai écrit la version la plus simple d'un trie, en utilisant des dictionnaires imbriqués. Ce n'est pas la manière la plus efficace d'en implémenter un, mais c'est un bon exercice pour comprendre la logique derrière un trie.

endOfWord = "$"
def generateTrieFromWordsArray(words): root = {} for word in words: currentDict = root for letter in word: currentDict = currentDict.setdefault(letter, {}) currentDict[endOfWord] = endOfWord return root
def isWordPresentInTrie(trie, word): currentDict = trie for letter in word: if letter in currentDict: currentDict = currentDict[letter] else: return False return endOfWord in currentDict

Vous pouvez voir ma solution pour le générateur d'anagrammes sur mon Github. Depuis que j'ai exploré cet algorithme, j'ai décidé de faire de ce blog l'un des nombreux articles - chaque article couvrant un algorithme ou une structure de données. Le code est disponible sur mon dépôt d'algorithmes et de structures de données - mettez-le en vedette pour rester à jour!

Prochaines étapes

Je suggère de vérifier le repo trie de Ray Wenderlich. Bien qu'écrit en Swift, c'est une source précieuse pour les explications de divers algorithmes.

Semblable au trie (mais plus efficace en mémoire) est un arbre de suffixes, ou radix. En bref, au lieu de stocker des caractères uniques à chaque nœud, la fin d'un mot, son suffixe, est stockée et les chemins sont créés de manière relative.

Cependant, un radix est plus compliqué à mettre en œuvre qu'un trie. Je suggère de jeter un œil au repo radix de Ray Wenderlich si vous êtes intéressé.

Ceci est le premier article de ma série d'algorithmes et de structures de données. Dans chaque article, je présenterai un problème qui peut être mieux résolu avec un algorithme ou une structure de données pour illustrer l'algorithme / la structure de données elle-même.

Démarrez mon repo d'algorithmes sur Github et suivez-moi sur Twitter si vous souhaitez suivre!

Avez-vous gagné de la valeur en lisant cet article? Cliquez ici pour le partager sur Twitter! Si vous souhaitez voir du contenu comme celui-ci plus souvent, suivez-moi sur Medium et abonnez-vous à ma newsletter une fois par mois ci-dessous. N'hésitez pas à m'acheter un café aussi.