En fonction de ce que vous voulez faire, il existe de nombreuses bonnes structures de données.
Si vous voulez simplement stocker les mots et demander "ce mot est-il ici ou non ?", une table de hachage standard sans autre machinerie fantaisiste est une approche raisonnable. Si ce mot est une liste fixée à l'avance, envisagez d'utiliser une table de hachage parfaite pour obtenir des performances et une utilisation de l'espace excellentes.
Si vous souhaitez être en mesure de vérifier si un préfixe donné existe tout en supportant des recherches rapides, un fichier essai est une bonne option, bien qu'elle puisse être un peu inefficace en termes d'espace. Elle prend également en charge les insertions et les suppressions rapides. Il permet également l'itération par ordre alphabétique, ce que le hachage n'offre pas. Il s'agit essentiellement de la structure que vous avez décrite dans votre réponse, mais selon le cas d'utilisation, d'autres représentations des essais pourraient être meilleures.
Si, en plus de ce qui précède, vous savez avec certitude que la liste de mots est fixe, envisagez d'utiliser un système de gestion des mots. DAWG (graphe de mots acyclique dirigé), qui est essentiellement un DFA à état minimal pour le langage. Il est beaucoup plus compact que le trie, mais supporte beaucoup des mêmes opérations.
Si vous voulez un comportement de type trie mais ne voulez pas payer une pénalité d'espace énorme, la fonction arbre de recherche ternaire est une autre option viable, tout comme le arbre radix . Ce sont des structures très différentes, mais qui peuvent être bien meilleures que le trie dans des circonstances différentes.
Si l'espace est un problème mais que vous voulez un trie, regardez dans les rapport succinct qui a des recherches plus lentes mais une utilisation de l'espace à peu près optimale en théorie. Le lien explique comment elle est utilisée en JavaScript comme moyen facile de transmettre une énorme quantité de données. Une autre représentation compacte est le trie à double tableau mais je dois admettre que je n'y connais pas grand-chose.
Si vous souhaitez utiliser le dictionnaire pour des opérations telles que la vérification orthographique, où vous devez trouver des mots similaires à d'autres mots, la commande Arbre BK est une excellente structure de données à considérer.
J'espère que cela vous aidera !
