---

---

Préface

Le codage Huffman est basé sur la proportion de membres d'un segment de données,Pour le coder,Les codes des membres à haute fréquence doivent être aussi courts que possible,De cette façon, l'ensemble prend moins de mémoire que le codage de longueur fixe.

Lettres	A	B	C	D	E
Code commun	000	001	010	011	100

Donc une longueur deNLa chaîne de,Uniquement parABCDEComposition,Codage,Alors occupe - toi.3NTaille de l'espace bit.

---

---

Huffman Tree

Si une longueur est26Dans la chaîne de,AOui.2- Oui.,BOui.3- Oui.,COui.6- Oui.,DOui.7- Oui.,EOui.8- Oui..
（1）Trouvez d'abord le plus petit,C'est - à - dire:AEtB,Les utiliser comme un nouveau noeudABLes enfants de gauche et de droite,Fréquence plus faible comme enfant de gauche,L'aîné en tant qu'enfant droit.Nouveau noeudABContientAEtB,La fréquence d'occurrence est5.

（2）La fréquence la plus basse estABEtC,Ils forment un autre sous - arbre,Nouveau noeudABCFréquence de11.

（3）Les fréquences des sections actuelles sont respectivement deABC（11）、D（7）、E（8）,Donc,DEtEFormer un nouveau sous - arbre,Nouveau noeudDEFréquence de15.

（4）EnfinABCEtDEPour former l'arbre Huffman,ABCPour le Sous - arbre gauche,DEPour le Sous - arbre droit.

（5）Définissez le poids de la branche gauche de l'arbre à0,Le poids de la branche droite est fixé à1.

---

---

Code Huffman

Nous allons coder les feuilles par le chemin qui passe de la racine de l'arbre Huffman à la feuille .

Lettres	A	B	C	D	E
Code Huffman	000	001	01	10	11

Taille de l'espace utilisé pour le codage normal ：3 $\times$ 26 = 78.

Taille de l'espace utilisé par le codage Huffman ：3 $\times$ 2 + 3 $\times$ 3 + 2 $\times$ 6 + 2 $\times$ 7 + 2 $\times$ 8 = 57.

Réduit27%Taille de l'espace de stockage pour.

---

Création de l'arbre Huffman

Idées：

（1） Création de l'arbre d'abord , Il faut d'abord définir les noeuds de l'arbre ;
（2） Les membres du noeud incluent le poids de ce noeud weight,Initialiser comme0; Et les enfants de gauche et de droite de ce noeud , Ceci est représenté par la position du noeud dans le tableau , Peut également être représenté par un pointeur ,Initialiser comme-1;
（3） Pour faciliter la traversée de la feuille à la racine , Vous devez donc accéder à son noeud parent , Cela inclut parentMembres,Initialiser comme-1.

class Node
{
    
  public:
    int lchild = -1, rchild = -1;
    int parent = -1;
    int weight = 0;
};

---

Ensuite, nous entrons les poids du clavier ：

void InitWeight(Node *p, int num)
{
    
    for (int i = 0; i < num; i++)
    {
    
        int weight;
        cout << i << " Weight: " ;
        cin >> weight;
        p[i].weight = weight;
    }
    cout << "---------------Finish !------------------" << endl;
}

---

Trouver les deux plus petits noeuds , Fusionner les noeuds
À la fin du tableau des noeuds foliaires ajouter N-1 Noeud de fusion de bits , Chaque fois que dans un noeud sans noeud parent ,Trouver les deux noeuds avec les poids les plus faibles,Fusionner.

Idées：
（1） Trouvez d'abord le premier noeud racine （Pas de noeud parent,parent = -1）, Pour l'instant, son poids est le minimum
（2） Traverser tous les noeuds racine ,Par comparaison, Trouver le noeud le moins pondéré ,min1 égal à sa position dans le tableau .

（3） Trouver le deuxième noeud racine （Pas égal àmin1）, Prenez temporairement son poids comme deuxième décimale ;
（4） Division transversale min1 Tous les noeuds racinaires sauf , Trouver le noeud le moins pondéré ,min2 égal à sa position dans le tableau .

void SearchMin(const Node *p, int num, int &min1, int &min2)
{
    
    for (int i = 0; i < num; i++) // Trouver le premier noeud racine 
    {
    
        if (p[i].parent == -1)
        {
    
            min1 = i;
            break;
        }
    }

    for (int i = 0; i < num; i++) // Traverser tous les noeuds racine , Trouver le noeud racine avec le plus petit poids 
    {
    
        if ((p[i].parent == -1) && (p[i].weight < p[min1].weight))
        {
    
            min1 = i;
        }
    }

    for (int i = 0; i < num; i++) // Trouver le deuxième noeud racine 
    {
    
        if ((p[i].parent == -1) && (i != min1))
        {
    
            min2 = i;
            break;
        }
    }

    for (int i = 0; i < num; i++) // Traverser tous les noeuds racine , Trouver le noeud racinaire avec le deuxième plus petit poids 
    {
    
        if ((p[i].parent == -1) && (p[i].weight < p[min2].weight) && (i != min1))
        {
    
            min2 = i;
        }
    }
}

---

Créer un arbre Huffman
Idées：
（1）AvantnumLeafs + i Trouver le noeud le moins pondéré parmi les noeuds ,numLeafs + i Est le nombre actuel de noeuds foliaires et de noeuds de fusion .
（2） Les deux noeuds qui seront trouvés , Fusionner les noeuds , Le nouveau noeud est le parent de ces deux noeuds .

void CreateHuffman(Node *p, int numLeafs)
{
    
    int PosMin1, PosMin2;
    InitWeight(p, numLeafs);

    for (int i = 0; i < numLeafs - 1; i++)
    {
    
        SearchMin(p, numLeafs + i, PosMin1, PosMin2); //Les deux noeuds les moins pondérésPosMin1EtPosMin2

		// Fusionner les noeuds 
        p[numLeafs + i].weight = p[PosMin1].weight + p[PosMin2].weight;
        p[numLeafs + i].lchild = PosMin1;
        p[numLeafs + i].rchild = PosMin2;
        p[PosMin1].parent = numLeafs + i;
        p[PosMin2].parent = numLeafs + i;
    }
}

---

---

Conversion de code

Idées：
De chaque noeud foliaire au noeud racine , Donc C'est une traversée de bas en haut , Donc si c'est la branche gauche , Insérer à l'extrémité avant de la chaîne d'encodage 0, Si c'est la branche droite ,Insérer1.

void HuffmanCode(Node *p, const int num, string *codes)
{
    
    int parent;

    for (int i = 0; i < num; i++)
    {
    
        int j = i;
        while (p[j].parent != -1) //  A partir de tous les noeuds foliaires ,Traverser le noeud racine
        {
    
            parent = p[j].parent;

            if (p[parent].lchild == j) //  Si la branche gauche ,Danscodes[i] Insérer en haut de la chaîne 0
            {
    
                codes[i].insert(codes[i].begin(),'0');
            }
            else //  Si la branche droite ,Insérer1
            {
    
                codes[i].insert(codes[i].begin(),'1');
            }

            j = parent;

        }
    }
}

---

Fonction principale

#include <iostream>
#include <iomanip>
#include <string.h>
using namespace std;

#define NUM (5)
int main(void)
{
    
    Node N[2*NUM - 1]; // Définir un tableau de noeuds 

    CreateHuffman(N, NUM); //Construire un arbre Huffman

    string codes[NUM]; // Définir un tableau de chaînes d'encodage 
    HuffmanCode(N, NUM, codes); //Code Huffman
    
    cout << "Code Huffman：" << endl;
    for (int i = 0; i < NUM; i++) //Imprimer le Code Huffman
    {
    
        cout << N[i].weight << setw(8) << codes[i] << endl;
    }

    return 0;
}

---

Produits：

0 Weight: 6
1 Weight: 7
2 Weight: 3
3 Weight: 2
4 Weight: 8
---------------Finish !------------------
Code Huffman：
6      01
7      10
3     001
2     000
8      11