1.what‘s problem we faced?

/**
*    Q: what‘s problem we faced?
*
*    A: Data compression is still a problem, even now. we want to compress
*        the space of data. This desire is more and more stronger when we
*        need to deal with some operation about data transmission. Before
*        we start this article, it may be helpful if you try to provide a valid way
*        to compress data . I tried, but failed obviously. That why I write this
*        article. ^_^
*/

2. How can I solve it?

/**
*    Q: How can I solve it?
*
*    A: Where have problem is where have an answer, although it not always
*        the best one. In 1951, a algorithm was introduced by David A. Huffman.
*        It is different from the normal code and is a variable length code, which
*        have different length of code for different symbol. Now, there are two
*        problems:
*
*        No.1: is  variable length code possible? How can we know the length
*                of current symbol?
*
*                The answer is prefix code. Think about this, a tree like following:
*
*                                        
*                                         O
*                                   1 /     \ 0
*                                    O       O
*                               1 /    \ 0   c
*                                O      O
*                                a       b
*
*                This is a simple binary tree. There are three leaf node: a, b ,and c.we
*                label all of left branch as 1, and all of right branch as 0. So if we want
*                to arrive the leaf node a, the path is 11. In a similar way, we can get
*                all of nodes:
*                        a : 11
*                        b : 10
*                        c : 0
*
*                By accident, we get a variable length code.
*
*
*        No.2: How can we use variable length code to compress a series of symbol?

*
*                Now that we have a ability about variable length code. Some funny thing
*                will happen. Image this, In a data, which consist of a series of symbols,
*                some of symbols have occur at high proportion. some of symbols has occur
*                at low proportion. If we use some shorter code to indicate those symbols
*                which have a high proportion, the space of data will smaller than ever.
*                That is what we want.
*
*        Now, we have been know that we could compress a data by use variable length
*        code. However, the next problem is what kind of variable length code is what we
*        want. what kind of code is optimal ?
*/

3. What is HuffmanCoding ?

/**
*    Q: What is HuffmanCoding ?

*
*    A:Now,the problem is how can I create a optimal tree ? Do you have any idea?

*        Huffman was introduced a algorithm. It is looks like greedy algorithm. It is may
*        be simple, but the result is valid( this will be demonstrated below). The simplest
*        construction algorithm use a priority queue where the node with lowest probability
*        is given highest priority, the steps as following:
*
*        1. create a leaf node for each symbol, and add it to the priority queue.
*        2. while there is more than one node in the queue:
*            1. remove two nodes that have the highest priority.
*            2. create a new node as the parent node of the two nodes above. the
*                probability of this one is equal to the sum of the two nodes‘ probabilities.
*            3. add the new node to the queue.
*        3. the remaining node is the root of this tree. Read it‘s code as we do above.
*
*/

4. is it optimal ?

/**
*    Q: is it optimal ?
*
*    A: Hard to say. I haven‘t a valid method to measure this. About this issue, it is necessary to hear
*        about other people‘s advice. I believe there must be some exciting advice. By the way, this article
*        is just talk about compress of independent symbol, another important issue is about related symbol.
*        That maybe a serious problem.
*
*/

5. source code

/***    Here is an simple example*/#include <stdio.h>#include <iostream>/***    In a Huffman tree, some of nodes is valid symbol, and other is a combine node, which*    haven't a valid symbol. we need to label it in our nodes.*/enum ELEM_TYPE {        ET_VALID,        ET_INVALID,        ET_MAX,};typedef int    INDEX;/***    this is a container, we push all of element to it, and pop element by a priority. It is*    a class template since we don't know the type of data element.*/template <class ELEM>class Container {        public:                Container( int capacity);                ~Container( );                /*            *    push a element to this container.            */                bool push( ELEM item);                /*            *    pop a element from this container, the smallest one have the most priority.            *    Of course, the element must have provide a reload function for operator '<'.            */                bool pop( ELEM &item );		        private:                bool _find_idle( INDEX &num);                bool _set_elem( INDEX num, ELEM &elem);                bool _get_elem( INDEX num, ELEM &elem);		                ELEM                *ele;                ELEM_TYPE    *stat;                int                        cap;};template <class ELEM>Container<ELEM>::Container(  int capacity){        this->ele = new ELEM[capacity] ;        this->stat = new ELEM_TYPE[capacity];        int        i;        for( i=0; i<capacity; i++)                this->stat[i] = ET_INVALID;        this->cap = capacity ;}template <class ELEM>Container<ELEM>::~Container(  ){        if( this->ele!=NULL )                delete []this->ele;        if( this->stat!=NULL )                delete []this->stat;        this->cap = 0;}template <class ELEM>bool Container<ELEM>::push( ELEM item){        INDEX        num = -1;        if( (!this->_find_idle( num))                ||(!this->_set_elem( num, item)))                return false;        return true;}template <class ELEM>bool Container<ELEM>::pop( ELEM &item ){        INDEX    i = 0;        INDEX    Min;        /*       *    find the first valid element.       */        while( (this->stat[i]!=ET_VALID)                        &&( i<this->cap))                            i++;        for( Min = i ; i<this->cap; i++)        {                if(  ( this->stat[i]==ET_VALID)                      &&( this->ele[i]<this->ele[Min]))                    {                            Min = i;                    }        }        return this->_get_elem( Min, item);}template <class ELEM>bool Container<ELEM>::_find_idle( INDEX &num){        INDEX        i;        for( i=0; i<this->cap; i++)        {                if( this->stat[i]==ET_INVALID )                {                        num = i;                        return true;                }        }        return false;}template <class ELEM>bool Container<ELEM>::_set_elem( INDEX num, ELEM &elem){        if( (num>=this->cap)                ||(num<0) )                    return false;        this->stat[num] = ET_VALID;        this->ele[num] = elem;        return true;}template <class ELEM>bool Container<ELEM>::_get_elem( INDEX num, ELEM &elem){        if( (num<0)                ||(num>=this->cap))                    return false;        this->stat[num] = ET_INVALID;        elem =  this->ele[num];        return true;}/***    define a type of symbol. It will be used to record all information about a symbol.*/typedef char SYMINDEX;typedef int SYMFRE;class Symbol {        public:                /*            *    In the Huffman tree, we need to compute the sum of two child symbol.            *    For convenience,build a reload function is necessary.            */                Symbol operator + ( Symbol &s);                SYMINDEX        sym;                SYMFRE            freq;};Symbol Symbol::operator +( Symbol &s){        Symbol        ret;        ret.sym = '\0';        ret.freq = this->freq + s.freq;        return ret;}/***    define a node of binary tree. It will be used to create a Huffman tree.*/class HTreeNode {        public:                /*            *    In the container, we need compare two nodes. So this node must            *    provide a reload function about '<'.            */                bool operator< ( HTreeNode &n);                HTreeNode        *lchild;                HTreeNode        *rchild;                Symbol                sym;};bool HTreeNode::operator < ( HTreeNode &n){        return this->sym.freq<n.sym.freq?
 true: false;}/***    This is the core structure. It will build a Huffman coding based on our input symbol.*/class HuffmanCoding {        public:                HuffmanCoding( );                ~HuffmanCoding( );                bool Set( Symbol s[], int num);                bool Work( void);	private:                /*            *    create a Huffman tree.            */                bool CreateTree(Symbol s[], int num );                bool DestroyTree( );                /*            *    read Huffman coding from a Huffman tree.            */                bool ReadCoding( );                bool TravelTree( HTreeNode *parent, char *buf, INDEX cur);                Symbol                *sym ;                int                        sym_num ;                HTreeNode        *root ;};HuffmanCoding::HuffmanCoding( ){        this->sym = NULL;        this->sym_num = 0;        this->root = NULL;}HuffmanCoding::~HuffmanCoding( ){        if( this->sym!=NULL)                delete []this->sym;        this->sym_num = 0;        this->DestroyTree( );}/***    receive data from outside. Actually, this function is not necessary.But for make the *    algorithm looks like more concise,maybe this function is  necessary.*/bool HuffmanCoding::Set( Symbol s [ ], int num){        this->DestroyTree( );        this->sym = new Symbol[num];        for( int i=0; i<num; i++)                this->sym[i] = s[i];        if( NULL!=this->sym)        {                this->sym_num = num;                return true;        }        else        {                this->sym_num = 0;                return false;        }}/***    The core function. In this function, we create a Huffman tree , then read it.*/bool HuffmanCoding::Work( void){	        //Create a Huffman tree	        if( !this->CreateTree( this->sym, this->sym_num))                return false;        //read Huffman coding        if( !this->ReadCoding( ))                return false;        return true;}bool HuffmanCoding::CreateTree( Symbol s[], int num){         /*       *    create a priority tank. It always pop the element of the highest priority in the tank.       */        Container<HTreeNode>	tank(num);        for( int i=0; i<this->sym_num; i++)        {                HTreeNode        node;                node.lchild = NULL;                node.rchild = NULL;                node.sym = s[i];                tank.push( node);        }        /*       *    always pop two nodes, if fail, that's means there is only one node remain and it       *    is the root node of this Huffman tree.       */        HTreeNode        node1;        HTreeNode        node2;        while(  tank.pop( node1)                        && tank.pop( node2) )        {                HTreeNode        parent;                parent.lchild = new HTreeNode;                parent.rchild = new HTreeNode;                *parent.lchild = node1;                *parent.rchild = node2;                parent.sym = node1.sym + node2.sym;                /*            *    push new node to the tank.            */                tank.push( parent);        }        this->root = new HTreeNode(node1);        return true;}bool HuffmanCoding::DestroyTree( ){        return false;}bool HuffmanCoding::ReadCoding( ){        char        *code;        code = new char[this->sym_num + 1];        /*       *    travel the Huffman tree and print the code of all valid symbols.       */        this->TravelTree( this->root, code, 0);        delete []code;        return true;}#define        LCHAR    '1'#define        RCHAR    '0'bool HuffmanCoding::TravelTree( HTreeNode *parent, char *buf, INDEX cur){        buf[cur] = '\0';        if( (parent->lchild==NULL)                &&(parent->rchild==NULL) )                {//end node                        printf("[ %c] : %s\n", parent->sym.sym, buf);	        }        if( parent->lchild!=NULL )        {                buf[cur] = LCHAR;                this->TravelTree( parent->lchild, buf, cur + 1);        }        if( parent->rchild!=NULL )        {                buf[cur] = RCHAR;                this->TravelTree( parent->rchild, buf, cur + 1);        }        return true;}static Symbol	sArr[ ] = {        { '0', 0},        { '1', 1},        { '2', 2},        { '3', 3},        { '4', 4},        { '5', 5},        { '6', 6},        { '7', 7},        { '8', 8},        { '9', 9},};int main(){        HuffmanCoding    hcoding;        hcoding.Set( sArr, 10);        hcoding.Work( );        return 0;}