Huffman algorithm constructs code

Definition 1.

Huffman coding is mainly used for data compression.

Huffman code is a variable-length code. The encoding will appear high frequency of characters, using short encoding; Will appear low frequency characters, using long encoding.

The main problem with variable-length encodings is that you must implement non-prefix encodings, meaning that in one character set, the encodings of any character are not prefixes for the encodings of another character. For example, 0 and 10 are non-prefix codes, while 0 and 01 are not.

2. Structure of Huffman tree

According to the frequency of the characters, always select the current two nodes with a small frequency, combine them into a new node, and loop until only one node is left.

For the five characters A, B, C, D and E, the frequencies are represented by 1, 5, 7, 9 and 6 respectively, then the process of constructing the tree is as follows:

< img border = 0 SRC = "/ / files.jb51.net/file_images/article/201312/20131223160830944.png" >

The Huffman tree corresponding to the above process is:

< img border = 0 SRC = "/ / files.jb51.net/file_images/article/201312/20131223160918834.png" >

Suppose the left side is 0 and the right side is 1, then the variable length code is:

A 1:01 0

5:01 1 B

At 7:10 C

D dwells

E 6:00

Huffman constructs code

#include <iostream>
#include <string.h>
using namespace std;
struct Node{
    char c;
    int value;
    int par;
    char tag;    //Tag ='0', left; Tag ='1', on the right hand side
    bool isUsed;    //So let's see if this point has been used
    Node(){
        par=-1;
        isUsed=false;
    }
};
int input(Node*,int);   //Input node information
int buildedTree(Node*,int); //Build Huffman trees
int getMin(Node*,int);  //Look for unused nodes with minimum frequency values
int outCoding(Node*,int);   //Output Huffman coding
int main ()
{
    int n;
    cin>>n;
    Node *nodes=new Node[2*n-1];
    input(nodes,n);
    buildedTree(nodes,n);
    outCoding(nodes,n);
    delete(nodes);
    return 0;
}
int input(Node* nodes,int n){
    for(int i=0;i<n;i++){
        cin>>(nodes+i)->c;
        cin>>(nodes+i)->value;
    }
    return 0;
}
int buildedTree(Node* nodes,int n){
    int last=2*n-1;
    int t1,t2;
    for(int i=n;i<last;i++){
        t1=getMin(nodes,i);
        t2=getMin(nodes,i);
        (nodes+t1)->par=i; (nodes+t1)->tag='0';
        (nodes+t2)->par=i; (nodes+t2)->tag='1';
        (nodes+i)->value=(nodes+t1)->value+(nodes+t2)->value;
    }
    return 0;
}
int getMin(Node* nodes,int n){
    int minValue=10000000;
    int pos=0;
    for(int i=0;i<n;i++)
    {
        if((nodes+i)->isUsed == false && (nodes+i)->value<minValue){
            minValue=(nodes+i)->value;
            pos=i;
        }
    }
    (nodes+pos)->isUsed=true;
    return pos;
}
int outCoding(Node* nodes,int n){
    char a[100];
    int pos,k,j;
    char tmp;
    for(int i=0;i<n;i++){
        k=0;
        pos=i;
        memset(a,'0',sizeof(a));
        while((nodes+pos)->par!=-1){
            a[k++]=(nodes+pos)->tag;
            pos=(nodes+pos)->par;
        }
        strrev(a);    //Flip string
        cout<<(nodes+i)->c<<" "<<(nodes+i)->value<<":"<<a<<endl;
    }
    return 0;
}

Execution example:

< img border = 0 SRC = "/ / files.jb51.net/file_images/article/201312/20131223161119274.png" >