Huffman Tree (1) Basic Concept and C - language Implementation

Ce chapitre présente l'arbre haffman.Comme toujours,Cet article commence par une brève introduction à la théorie de l'arbre haffman,Et donneCMise en œuvre de la langue.Ensuite, donner séparémentC++EtJavaMise en œuvre de la version;La langue de mise en œuvre est différente,Mais le principe est le même,Sélectionnez l'un d'eux pour en savoir plus.S'il y a des erreurs ou des lacunes dans l'article,Veuillez indiquer！

Table des matières

1. Introduction à l'arbre Huffman
2. Analyse graphique et textuelle de l'arbre haffman
3. Fonctionnement de base de l'arbre haffman
4. Source complète de l'arbre haffman

---

Veuillez indiquer la source de la réimpression.：Si le ciel ne meurt pas - La blogosphère

Plus de détails：Structure des données et série d'algorithmes Table des matières

Introduction à l'arbre Huffman

Huffman Tree, Le nom chinois est Huffman Tree ou Huffman Tree , C'est le meilleur Arbre binaire . L'origine est principalement la transmission codée de l'information , Principalement utilisé dans le domaine du codage de l'information et de la compression numérique , C'est aussi la base des algorithmes de compression modernes .

Définition：Compte tenu denPoids commenNoeuds foliaires,Construire un arbre binaire, Si la longueur du chemin pondéré de l'arbre atteint un minimum , Alors cet arbre s'appelle l'arbre haffman . Cette définition implique plusieurs concepts étranges , En dessous, il y a un arbre Huffman , Regardons les diagrammes et les solutions .

 

(01) Chemin et longueur du chemin

Définition：Dans un arbre,L'accès entre les noeuds d'un enfant ou d'un petit - enfant qui peut être atteint à partir d'un noeud,Appelé chemin.Le nombre de branches dans un chemin est appelé la longueur du chemin.Si le nombre de couches du noeud racinaire spécifié est1,Du noeud racine auLLa longueur du chemin du noeud de couche estL-1.
Exemple：100Et80 La longueur du chemin est 1,50Et30 La longueur du chemin est 2,20Et10 La longueur du chemin est 3.

(02) Poids du noeud et longueur du chemin pondéré

Définition：Si vous attribuez un noeud dans un arbre à une valeur qui a un sens,Cette valeur est appelée le poids du noeud.La longueur du chemin pondéré du noeud est：Produit de la longueur du chemin entre le noeud racine et le noeud et du poids du noeud.
Exemple：Noeud20 La longueur du chemin est 3, Sa longueur de chemin pondérée = Longueur du chemin * Droits = 3 * 20 = 60.

(03) Longueur du chemin pondéré de l'arbre

Définition：La longueur pondérée du chemin de l'arbre est définie comme la somme des longueurs pondérées du chemin de tous les noeuds foliaires.,Notez comme suit:WPL.
Exemple：Dans l'exemple,ArbreWPL= 1*100 + 2*80 + 3*20 + 3*10 = 100 + 160 + 60 + 30 = 350.

Comparez les deux arbres ci - dessous

 

Les deux arbres ci - dessus sont {10, 20, 50, 100} Arbre pour noeuds foliaires .

Arbre à gauche WPL=2*10 + 2*20 + 2*50 + 2*100 = 360
L'arbre de droite WPL=350

Arbre à gauche WPL > L'arbre de droite WPL. Vous pouvez également calculer les cas autres que les deux exemples ci - dessus , Mais en fait, l'arbre de droite est {10,20,50,100} L'arbre Huffman correspondant .Jusqu'ici., Le concept d'arbre Huffman qui devrait être empilé a une certaine compréhension , Voici comment construire un arbre Huffman .

Analyse graphique et textuelle de l'arbre haffman

Supposons qu'il y aitnPoids,L'arbre Huffman construit anNoeuds foliaires. nLes poids sont fixés à w1、w2、…、wn,La règle de construction de l'arbre Huffman est：

1. Oui.w1、w2、…,wnOn dirait.n Une forêt d'arbres(Un seul noeud par arbre);
2. Les deux arbres dont le poids du noeud racinaire est le plus faible sont choisis dans la forêt pour être combinés,À gauche d'un nouvel arbre、Sous - arbre droit,Et le poids du noeud racine du nouvel arbre est à sa gauche、Somme des poids des noeuds racinaires du sous - arbre droit;
3. Retirer les deux arbres sélectionnés de la forêt,Et ajouter de nouveaux arbres à la forêt;
4. Je répète.(02)、(03)Pas,Jusqu'à ce qu'il ne reste plus qu'un arbre dans la forêt,L'arbre est l'arbre Huffman obtenu.

Par{5,6,7,8,15}Par exemple,Pour construire un arbre Huffman.

 

No1Pas：Créer une forêt,La forêt comprend5Arbre,Voilà.5Les poids des arbres sont respectivement5,6,7,8,15.
No2Pas：Dans la forêt, Sélectionnez les deux arbres dont le poids du noeud racine est le plus faible (5Et6)Pour fusionner, Les enfants de gauche et de droite qui les considèrent comme un nouvel arbre ( Peu importe qui est à gauche ou à droite ,Ici., Nous avons choisi le plus petit comme enfant de gauche ), Et le poids du nouvel arbre est la somme des poids des enfants de gauche et de droite .C'est - à - dire:, Le poids du nouvel arbre est 11. Et puis,Oui."Arbre5"Et"Arbre6"Retirer de la forêt, Et un nouvel arbre (Arbre11)Ajouter à la forêt.
No3Pas：Dans la forêt, Sélectionnez les deux arbres dont le poids du noeud racine est le plus faible (7Et8)Pour fusionner. Le poids du nouvel arbre obtenu est 15. Et puis,Oui."Arbre7"Et"Arbre8"Retirer de la forêt, Et un nouvel arbre (Arbre15)Ajouter à la forêt.
No4Pas：Dans la forêt, Sélectionnez les deux arbres dont le poids du noeud racine est le plus faible (11Et15)Pour fusionner. Le poids du nouvel arbre obtenu est 26. Et puis,Oui."Arbre11"Et"Arbre15"Retirer de la forêt, Et un nouvel arbre (Arbre26)Ajouter à la forêt.
No5Pas：Dans la forêt, Sélectionnez les deux arbres dont le poids du noeud racine est le plus faible (15Et26)Pour fusionner. Le poids du nouvel arbre obtenu est 41. Et puis,Oui."Arbre15"Et"Arbre26"Retirer de la forêt, Et un nouvel arbre (Arbre41)Ajouter à la forêt.
En ce moment, Il n'y a qu'un seul arbre dans la forêt (Arbre41). Cet arbre est l'arbre Huffman dont nous avons besoin ！

Fonctionnement de base de l'arbre haffman

L'arbre haffman se concentre sur la façon de construire l'arbre haffman.Quand cet article construit haffman, En utilisant ce qui a été décrit précédemment "(Pile binaire)Pile minimale".Voici une explication de l'arbre haffman.

1. Définitions de base

typedef int Type;

typedef struct _HuffmanNode {
    Type key;                     // Poids
    struct _HuffmanNode *left;    // Enfant de gauche
    struct _HuffmanNode *right;   // Enfant droit
    struct _HuffmanNode *parent;  // Noeud parent
} HuffmanNode, *HuffmanTree;

HuffmanNode C'est la classe de noeuds de l'arbre Huffman .

2. Construire l'arbre Huffman

/*
 * CréationHuffmanArbre
 *
 * Description des paramètres：
 *     a Tableau des poids
 *     size Taille du tableau
 *
 * Valeur de retour：
 *     HuffmanLa racine de l'arbre
 */
HuffmanNode* create_huffman(Type a[], int size)
{
    int i;
    HuffmanNode *left, *right, *parent;

    // Créer un tableauaPile minimale correspondante
    create_minheap(a, size);

    for(i=0; i<size-1; i++)
    {   
        left = dump_from_minheap();  // Le noeud le plus petit est l'enfant gauche
        right = dump_from_minheap(); // Ensuite, l'enfant droit

        // NouveauparentNoeud,Les enfants de gauche et de droite sontleft/right;
        // parentLa taille est la somme des enfants de gauche et de droite
        parent = huffman_create_node(left->key+right->key, left, right, NULL);
        left->parent = parent;
        right->parent = parent;


        // Oui.parentCopie des données du noeud à"Pile minimale"Moyenne
        if (dump_to_minheap(parent)!=0)
        {
            printf("L'insertion a échoué!\nFin du programme\n");
            destroy_huffman(parent);
            parent = NULL;
            break;
        }
    }   

    // Détruire le plus petit tas
    destroy_minheap();

    return parent;
}

D'abord parcreate_huffman(a, size) Un petit tas . Une fois la construction minimale du tas terminée ,EntréeforCycle.

À chaque cycle：

(01) Tout d'abord,, Copier le plus petit noeud dans le plus petit tas et assigner une valeur à left, Et ensuite remodeler le plus petit tas ( Changez la position du noeud le plus petit et du noeud suivant ,Et puis..." Le plus petit noeud après l'échange de position " Tous les éléments précédents ont été reconstruits en tas minimal );
(02) Et voilà., Copiez le plus petit noeud dans le plus petit tas et attribuez - le right, Et ensuite remodeler à nouveau le plus petit tas ;
(03) Et puis,Nouveau noeudparent,Et l'utiliser commeleftEtrightParent de;
(04) Et voilà.,Oui.parent Les données sont copiées au noeud spécifié dans le plus petit tas .

InPile binaire Le tas a été décrit dans , Le Code du tas n'est plus décrit ici .En cas de doute, Référence directe au code source suivant . Autres codes pertinents ,- Oui.Please RTFSC(Read The Fucking Source Code)！

Source complète de l'arbre haffman

Le code source de l'arbre haffman comprend 4Fichiers.

1.  Fichier d'en - tête de l'arbre haffman (huffman.h)

2.  Fichier d'implémentation de l'arbre haffman (huffman.c)

3.  Le plus petit tas correspondant à l'arbre haffman (minheap.c)

4.  Le Programme d'essai de l'arbre Huffman (huffman_test.c)