Recherche efficace dans l'arbre de Huffman tout en se souvenant du chemin emprunté

Question

Comme question complémentaire liée à ma question sur le moyen efficace de stocker les éléments de huffman tree Je me demandais quel serait le moyen le plus rapide et le plus efficace de rechercher un arbre binaire (basé sur la sortie de codage de Huffman) et de stocker le chemin emprunté vers un nœud particulier.

Voici ce que j'ai actuellement:

• Ajouter un noeud racine à la file d'attente
• tant que la file d'attente n'est pas vide, retirez l'élément de la file d'attente
  • vérifiez si c'est ce que nous cherchons
    • oui: Suivez un pointeur principal sur le nœud racine. Chaque nœud que nous visitons vérifie si c’est à gauche ou à droite et en prend note.
    • sortir de la recherche
  • mettre en file d'attente à gauche et à droite le noeud

Puisqu'il s'agit d'un arbre de Huffman, toutes les entrées que je recherche existeront. Ce qui précède est une première recherche étendue, qui est considérée comme la meilleure pour les arbres de Huffman, car les éléments qui se trouvent dans la source sont plus souvent situés plus haut dans l’arbre pour obtenir une meilleure compression. Cependant, je ne peux pas trouver un bon moyen de garder trace de comment nous sommes arrivés à un noeud particulier sans revenir en arrière en utilisant le pointeur de tête que j'ai mis dans le noeud.

Dans ce cas, tous les chemins droite / gauche sont également affichés dans l'ordre inverse, par exemple, si nous suivons la tête vers la racine et que nous découvrons que, depuis la racine, il se trouve à droite, à gauche, à gauche, nous sommes partis à gauche, à droite, à droite. ou 001 en binaire, lorsque je cherche à obtenir 100 de manière efficace.

Il a également été suggéré de stocker le chemin d'accès de la racine au nœud en tant que valeur distincte à l'intérieur du nœud. Toutefois, cette opération échouerait si nous avions un arbre plus grand que le nombre de bits que la variable que nous avions créée à cette fin pouvait contenir. et à ce moment-là, stocker les données occuperait également une énorme quantité de mémoire.

Answer 1

Créez un dictionnaire de valeur - > chaîne de bits, cela vous donnerait la recherche la plus rapide.

Si les valeurs ont une taille connue, vous pouvez probablement vous contenter d'un tableau de chaînes de bits et rechercher les valeurs par leur index.

Answer 2

Si vous décodez un bit à la fois des données codées Huffman, vos performances seront médiocres. Autant que vous voudriez éviter d'utiliser des tables de recherche, c'est la seule façon de faire si vous vous souciez de la performance. De la manière dont les codes de Huffman sont créés, ils sont uniques de gauche à droite et se prêtent parfaitement à une recherche rapide dans les tableaux.