structure de données recommandée lors de la conception de quelque chose comme un dictionnaire?

Question

TRIE est la structure de données la plus recommandée lors de la conception de quelque chose comme un dictionnaire pour stocker des mots? Toutes les autres alternatives qui améliorent la performance de temps ou de mémoire? Je pense qu'un hachage peut être bon s'il n'y a pas de collision, mais les exigences de mémoire commencent à être mauvaises pour les mots qui se chevauchent: over, overlap, overlaps, overlapped, overlapping occupent tous un espace de stockage exclusif.

EDIT: Merci @Moron et à vous tous pour les réponses très utiles. Je suis d'accord - la génération de la clé de hachage est O (n) et il en est de même pour la recherche TRIE. Cependant, pour les choses de hachage peut être pire avec enchaînement ajoutant à l'heure tandis que pour TRIE cela ne se produira pas. Mon souci reste que pour chaque noeud dans un TRIE je dois garder un pointeur qui peut être des choses de soufflage si la taille du dictionnaire est petite.

Answer 1

Vous pouvez considérer Directed Acyclic Word graph qui est essentiellement une structure arborescente, mais a une meilleure utilisation de la mémoire, et selon le wiki, pour l'anglais, la consommation de mémoire est beaucoup plus faible qu'une structure arborescente.

Dans le temps, c'est comme un trie et c'est probablement mieux que le hachage.Vous ne savez pas où vous avez obtenu l'heure O (logn) pour le hachage. Il devrait être O (n) pour des hachages raisonnables, où n est la longueur du mot recherché.

Answer 2

A Trie présente les avantages suivants sur une table de hachage:

1. recherche de données dans une structure arborescente est plus rapide dans le pire des cas, O(m) temps, par rapport à une table de hachage imparfaite. Une table de hachage imparfaite peut avoir des collisions de clé. Une collision de clé est le mappage de fonction de hachage de différentes clés à la même position dans une table de hachage. La vitesse de recherche dans le cas le plus défavorable dans une table de hachage imparfaite est O(N) temps, mais beaucoup plus généralement est O(1), avec O(m) temps passé à évaluer le hachage.
2. Il n'y a aucune collision de différentes clés dans un trie.
3. Les compartiments d'une série qui sont analogues aux compartiments de table de hachage qui stockent des collisions de clés ne sont nécessaires que si une seule touche est associée à plusieurs valeurs.
4. Il n'est pas nécessaire de fournir une fonction de hachage ou de modifier les fonctions de hachage car plus de clés sont ajoutées à un trie.
5. Un trie peut fournir un ordre alphabétique des entrées par clé.

Tries présentent les inconvénients suivants:

1. Tries peuvent être plus lents dans certains cas que les tables de hachage pour rechercher des données, en particulier si les données sont directement accessibles sur un disque dur ou un autre stockage secondaire dispositif où le temps d'accès aléatoire est élevé par rapport à la mémoire principale.
2. Il n'est pas facile de représenter toutes les clés comme des chaînes, comme les nombres à virgule flottante. Un codage simple utilisant la chaîne binaire de leur codage conduit à des chaînes longues et des préfixes peu significatifs.

Si les inconvénients sont quelque chose que vous pouvez vivre avec, je suggère d'aller avec le trie.

Source: Wikipedia: Trie#As a replacement of other data structures

Answer 3

Je suppose que c'est la grande question, hein? Peut-être essayer de regarder un filtre Bloom?

http://en.wikipedia.org/wiki/Bloom_filter