Je ne comprends pas cette implémentation de l'algorithme de Huffman

template<class T> 
    void huffman(MinHeap<TreeNode<T>*> heap, int n) 
    { 
     for(int i=0;i<n-1;i++) 
     { 
     TreeNode<T> *first = heap.pop(); 
     TreeNode<T> *second = heap.pop(); 
     TreeNode<T> *bt = new BinaryTreeNode<T>(first, second, first.data, second.data); 
     heap.push(bt); 
     } 
    }

Dans mon manuel Fundamentals of Data Structures in C++, il a donné une définition de 2 page de codage de Huffman, et le code ci-dessus. Pour moi, le livre n'était pas assez détaillé, donc j'ai fait le googling et j'ai appris comment fonctionne le processus de codage Huffman. Le manuel prétend qu'à la fin du code ci-dessus, un arbre Huffman est fait. Mais pour moi, il semble faux, car un arbre Huffman, n'est pas nécessaire un arbre complet, mais le code ci-dessus semble toujours donner un arbre complet à cause de la heap.push(). Alors quelqu'un peut-il m'expliquer comment ce morceau de code n'est pas faux?Je ne comprends pas cette implémentation de l'algorithme de Huffman

Source

2010-07-16 user299648

La structure arborescente du tas ne correspond pas nécessairement à l'arborescence Huffman résultante - plutôt, le tas contient une forêt d'arborescences partielles de Huffman, initialement chacune composée d'un seul nœud de symbole. La boucle prend alors de façon répétée les deux nœuds ayant le moins de poids, les combine en un seul nœud et remet le nœud combiné résultant. À la fin du processus, le tas contient un arbre fini.

Source

2010-07-16 23:47:37

Ensuite, ce que je ne comprends pas, c'est que si le tas n'est pas nécessairement l'arbre de Huffman, comment puis-je traverser ou utiliser le tas pour trouver le nœud feuille correcte. – user299648

Le tas est une structure de données auxiliaire temporaire utilisée pour améliorer l'efficacité de l'opération de recherche des deux nœuds de Huffman avec le moins de poids. A la fin, le tas ne contient qu'un seul élément, un seul 'BinaryTreeNode ', qui peut être déplacé et qui est alors la racine de l'arbre de Huffman fini; le tas peut alors être détruit car il n'est plus nécessaire. –

merci beaucoup! vous étiez vraiment utile. – user299648

Le codage Huffman fonctionne en prenant les deux éléments de valeur la plus faible à chaque étape. Lorsque vous appelez la fonction pour la première fois (puisque votre MinHeap est trié par valeur), les deux éléments de valeur la plus basse sont supprimés et "combinés" dans un nœud de décision qui est ensuite remis dans le tas. Ce noeud est marqué par la somme de ses scores enfants et remis dans le tas. L'insérer de nouveau dans le tas le met au bon endroit en fonction de son score; Si c'est encore plus bas que n'importe quel autre élément, ce sera le premier, sinon ce sera ailleurs. Donc, cet algorithme construit l'arborescence de bas en haut, et au moment où vous videz le tas, vous aurez un arbre complet. Je ne comprends pas à quoi sert le 'n'; la boucle doit être while (heap.size() > 1). Quoiqu'il en soit, l'arbre n'est pas "plein", les différentes branches auront des longueurs différentes en fonction de la façon dont les fréquences des items du tas initial sont notées.

Source

2010-07-16 23:49:02

Je ne comprends pas cette implémentation de l'algorithme de Huffman

Répondre

Questions connexes