Comment choisir entre une table de hachage et un Trie (arborescence de préfixes)?

134

Donc, si je dois choisir entre une table de hachage ou une arborescence de préfixes, quels sont les facteurs discriminants qui me conduiraient à choisir l'une par rapport à l'autre. De mon propre point de vue naïf, il semble que l'utilisation d'un trie ait une surcharge supplémentaire car il n'est pas stocké sous forme de tableau mais qu'en termes de temps d'exécution (en supposant que la clé la plus longue est le mot anglais le plus long), il peut être essentiellement O (1) (par rapport à la borne supérieure). Peut-être que le mot anglais le plus long est de 50 caractères?

Les tables de hachage sont une recherche instantanée une fois que vous obtenez l'index . Le hachage de la clé pour obtenir l'index semble cependant que cela pourrait facilement prendre près de 50 étapes.

Quelqu'un peut-il me donner une perspective plus expérimentée à ce sujet? Merci!

Justin Bozonier
la source
1
Il est à noter qu'un arbre redix est plus efficace qu'un trie simple car vous n'avez pas besoin d'une nouvelle branche pour chaque octet de chaîne. De plus, les arborescences redix fournissent un support pour les recherches "floues" mieux que les tables de hachage car vous regardez des bits individuels lorsque vous travaillez sur le chemin. Par exemple, il 00110010peut s'agir de l'octet d'entrée, mais vous souhaitez inclure la correspondance 00111010qui n'est supprimée que d'un bit.
Xeoncross

Réponses:

116

Avantages des essais:

Les bases:

  • Temps de recherche prévisible O (k) où k est la taille de la clé
  • La recherche peut prendre moins de k temps si ce n'est pas là
  • Prend en charge la traversée ordonnée
  • Pas besoin de fonction de hachage
  • La suppression est simple

Nouvelles opérations:

  • Vous pouvez rechercher rapidement des préfixes de clés, énumérer toutes les entrées avec un préfixe donné, etc.

Avantages de la structure liée:

  • S'il existe de nombreux préfixes communs, l'espace dont ils ont besoin est partagé.
  • Les essais immuables peuvent partager la structure. Au lieu de mettre à jour un trie en place, vous pouvez en créer un nouveau qui n'est différent que le long d'une branche, pointant ailleurs dans l'ancien trie. Cela peut être utile pour la concurrence, plusieurs versions simultanées d'une table, etc.
  • Un trie immuable est compressible. Autrement dit, il peut également partager la structure sur les suffixes , par hachage.

Avantages des hashtables:

  • Tout le monde connaît les hashtables, non? Votre système aura déjà une belle implémentation bien optimisée, plus rapide que les tentatives dans la plupart des cas.
  • Vos clés ne doivent pas avoir de structure particulière.
  • Plus efficace en espace que la structure de trie liée évidente ( voir les commentaires ci-dessous )
Darius Bacon
la source
27
ne peut pas tout à fait être d'accord avec "Plus efficace en espace que la structure trie liée évidente" - dans une implémentation générale de table de hachage, elle occupe un espace beaucoup plus grand pour contenir des clés, tandis que dans les essais, chaque nœud représente un mot. En ce sens, les essais sont plus efficaces en termes d'espace.
galactica
1
que diriez-vous d'accéder aux données d'une structure par rapport à l'autre? Je pense au cache et à l'emplacement
Horia Toma
8
@galactica, qui contredit mon expérience: par exemple, dans cette réponse de toutes les structures que j'ai mesurées pour l'espace, un trie a fait le pire. Cela a du sens car un pointeur est beaucoup plus grand qu'un octet. Oui, le partage de préfixes aide, mais il doit surmonter beaucoup de frais généraux pour atteindre la parité. Une représentation plus efficace en espace peut beaucoup aider, mais nous ne parlons plus de la structure liée évidente.
Darius Bacon
1
@DariusBacon gérer les plans de numérotation téléphonique semble être un scénario raisonnable pour les essais. Exemple de scénario: correspondance du numéro de téléphone au transporteur incl. numéros portés d'un transporteur à un autre. Pour les dictionnaires habituels, cela peut dépendre de la langue (mandarin vs anglais), vous aurez besoin de n-grammes et / ou d'autres données statistiques. Pour un livre de rimes, un arbre de suffixes semble également une bonne option.
mbx du
La diversité des données à rechercher est très importante. Si un grand pourcentage de vos valeurs de données est unique, la complexité de votre espace augmentera avec le hachage en raison de l'utilisation de pointeurs Null supplémentaires.
Apprentissage des statistiques par exemple le
45

Tout dépend du problème que vous essayez de résoudre. Si tout ce que vous avez à faire est des insertions et des recherches, utilisez une table de hachage. Si vous avez besoin de résoudre des problèmes plus complexes tels que des requêtes liées aux préfixes, alors un trie peut être la meilleure solution.

Adam Rosenfield
la source
8
si la table de hachage et le trie ont la même complexité sur la requête, O (k) pour une chaîne de longueur k pourquoi devrions-nous opter pour le hachage? pourriez-vous s'il vous plaît expliquer?
Sazzad Hissain Khan
29

Tout le monde connaît la table de hachage et ses utilisations, mais ce n'est pas exactement un temps de recherche constant, cela dépend de la taille de la table de hachage, de la complexité de calcul de la fonction de hachage.

La création d'énormes tables de hachage pour une recherche efficace n'est pas une solution élégante dans la plupart des scénarios industriels où même une petite latence / évolutivité est importante (par exemple: trading haute fréquence). Vous devez également vous soucier des structures de données à optimiser pour l'espace qu'elles prennent en mémoire afin de réduire les échecs de cache.

Un très bon exemple où trie répond mieux aux exigences est le middleware de messagerie. Vous avez un million d'abonnés et d'éditeurs de messages dans différentes catégories (en termes JMS - Thèmes ou échanges), dans ce cas, si vous souhaitez filtrer les messages en fonction de sujets (qui sont en fait des chaînes), vous ne voulez certainement pas créer de table de hachage pour le million d'abonnements avec un million de sujets. Une meilleure approche consiste à stocker les sujets dans un tri, donc lorsque le filtrage est effectué en fonction de la correspondance des sujets, sa complexité est indépendante du nombre de sujets / abonnements / éditeurs (ne dépend que de la longueur de la chaîne). Je l'aime parce que vous pouvez être créatif avec cette structure de données pour optimiser les besoins en espace et donc réduire le manque de cache.

user179156
la source
11

Utilisez un arbre:

  1. Si vous avez besoin de la fonction de saisie semi-automatique
  2. Trouvez tous les mots commençant par «a» ou «ax» ainsi de suite.
  3. Un arbre de suffixe est une forme spéciale d'arbre. Les arbres de suffixes ont toute une liste d'avantages que le hachage ne peut pas couvrir.
Dr.Sai
la source
4

Il y a quelque chose que je n'ai vu personne mentionner explicitement et qu'il est important de garder à l'esprit. Les tables de hachage et les essais de différents types auront généralement des O(k)opérations, où kest la longueur de la chaîne en bits (ou de manière équivalente en caractères).

Cela suppose que vous ayez une bonne fonction de hachage. Si vous ne voulez pas que les mots «ferme» et «animaux de la ferme» aient la même valeur, alors la fonction de hachage devra utiliser tous les bits de la clé, et le hachage des «animaux de la ferme» devrait donc prendre environ deux fois plus de temps que "ferme" (sauf si vous êtes dans une sorte de scénario de hachage roulant, mais il existe des scénarios de sauvegarde d'opération quelque peu similaires avec des essais également). Et avec un trie de vanille, il est clair pourquoi l'insertion des «animaux de la ferme» prendra environ deux fois plus de temps que simplement «de la ferme». À long terme, c'est également vrai avec les essais compressés.

user3391564
la source
3

L'insertion et la recherche sur un trie sont linéaires avec la longueur de la chaîne d'entrée O (s).

Un hachage vous donnera un O (1) pour la recherche et l'insertion, mais vous devez d'abord calculer le hachage en fonction de la chaîne d'entrée qui est à nouveau O (s).

En conclusion, la complexité temporelle asymptotique est linéaire dans les deux cas.

Le trie a un peu plus de surcharge du point de vue des données, mais vous pouvez choisir un trie compressé qui vous mettra à nouveau, plus ou moins sur un lien avec la table de hachage.

Pour briser la cravate, posez-vous cette question: Dois-je rechercher uniquement les mots complets? Ou dois-je renvoyer tous les mots correspondant à un préfixe? (Comme dans un système de saisie de texte prédictif). Pour le premier cas, optez pour un hachage. C'est un code plus simple et plus propre. Plus facile à tester et à entretenir. Pour un cas d'utilisation plus détaillé où les préfixes ou les suffixes comptent, optez pour un essai.

Et si vous le faites juste pour le plaisir, la mise en œuvre d'un trie mettrait un dimanche après-midi à une bonne utilisation.

Visiedo
la source
"Un hachage vous donnera un O (1) pour la recherche et l'insertion, mais vous devez d'abord calculer le hachage en fonction de la chaîne d'entrée qui est à nouveau O (s)." Merci d'avoir expliqué cela!
abadawi le
Le calcul de la fonction de hachage n'est pas O (s). C'est en fait O (1). Vous n'avez pas besoin de tous les bits de la chaîne pour la calculer, certains d'entre eux (un nombre constant d'entre eux) suffisent.
Nicola Amadio il y a
2

L' implémentation HashTable est peu encombrante par rapport à l' implémentation de base de Trie . Mais avec les chaînes, la commande est nécessaire dans la plupart des applications pratiques. Mais HashTable perturbe totalement l'ordre lexographique. Maintenant, si votre application effectue des opérations basées sur l'ordre lexographique (comme la recherche partielle, toutes les chaînes avec un préfixe donné, tous les mots dans l'ordre trié), vous devez utiliser Tries. Pour la seule recherche, HashTable doit être utilisé (comme on peut le dire, cela donne un temps de recherche minimum).

PS: En dehors de ceux-ci, les arbres de recherche ternaires (TST) seraient un excellent choix. Son temps de recherche est supérieur à celui de HashTable, mais il est efficace dans toutes les autres opérations. En outre, son plus d'espace que les essais.

Jay Jodiwal
la source
-2

Certaines applications (généralement embarquées, en temps réel) exigent que le temps de traitement soit indépendant des données. Dans ce cas, une table de hachage peut garantir un temps d'exécution connu, tandis qu'un trie varie en fonction des données.

Adam Liss
la source
6
La plupart des tables de hachage ne garantissent pas un temps d'exécution connu - le pire des cas est O (n), si chaque élément entre en collision et est enchaîné
Adam Rosenfield
2
Pour tout ensemble de données, vous pouvez calculer une fonction de hachage parfaite qui garantira les recherches O (1) pour ces données. Bien sûr, calculer le hachage parfait n'est pas gratuit.
George V. Reilly
5
De plus, le chaînage n'est pas le seul moyen de gérer les collisions; il existe toutes sortes de façons intéressantes et intelligentes de gérer cela - le hachage de coucou ( en.wikipedia.org/wiki/Cuckoo_hashing ) pour un - et le meilleur choix dépend des besoins du code client.
Hank Gay
ne savait pas sur le hachage du coucou et sa relation avec le filtre de floraison, fera une lecture intéressante, merci!
Horia Toma
N'oubliez pas le hachage Robin-Hood, qui est supérieur pour le cache et la variance. sebastiansylvan.com/2013/05/08/… codecapsule.com/2013/11/11/robin-hood-hashing
Jarred Nicholls