Huffman 编码树

像SCAII这样即那个每个字符表示为一个7为二进制的序列的编码方式称为定长编码,它们采用同样数目的二进制位表示消息中的一个字符.与之相对应的是变长编码,即用可变的二进制位数表示不同的字符.

一般而言,如果在我们的消息中,某写符号出现得比较频繁,而另一些比较少见,那么就可以通过为这些出现比较频繁的字符指定比较短的二进制位编码来达到节省空间的目的.

但是采用二进制编码有一个困难,它需要在读二进制序列是判断合适到达了一个字符的结束.解决这一问题的方法可以在每个字母后面用一个特殊分隔符(莫尔编码). 另一种解决方式是设计编码方式,是得其中每个字符的完整编码都不是另一个字符编码的开始一段.这中编码方式称为前缀编码.一般而言能够通过变长前缀码去利用编码消息中符号出现的相对频度,就能节省空间.完成这一特定时间的方式称为Huffman编码.一个Huffman编码可以表示为一个二叉树,其中的树叶是被编码的符号.树中的每个每个非叶子节点代表一个集合,其中包含饿这一节点之下的所有书上的符号.每个位于书上的符号被赋予一个权重,也就是它的相对频度.非叶子节点所包含的权重位是位于它之下的所有叶子节点的权重之和.这种权重在编码和解码中国并不使用.

下图是一颗Huffman编码树

在用Huffman树做一个序列解码时,我们从树根开始,通过位序列中的0或者1确定是向左移动还是向右移动.每当达到一个叶子节点时就生成出一个符号,然后再从新从树根开始去确定下一个符号,直到解码完给定的的二进制序列为止.

列如,如果有一个序列10001010 .从数根开始,序列的第一位是1, 所以我们向右分支移动,第二位是0,所以我们向左移动,第三位是0 ,所以向左移动.这是已经到达Bde叶,所以被解码消息中的第一个符号是B.接着再从树根开始重复上述过程,最后可以确定整个消息是BAC.

生成Huffman树

给定了符号的 符号表和它们的相对频度,怎么才能构造出最好的编码?(也就是怎样的树能是消息编码的位数最少).Huffman给出了完成这一事件的一个算法,并且证明给了对于符号所出现的相对频度与构造树的消息符号的消息而言,这样产生的编码是最好的边长编码.

生成Huffman树的算法非常简单,就是安排这棵树,使得那些带有最低平度的符号出现在离树根最远的地方.这一构造过程从叶节点的集合开始,这种节点中包含包含各个符号和他们出现的频度,这就是开始构造编码数的初始数据.现在要找出连个具有最低权重的叶,并归并它们,产生出一个以这两个节点为左右分支的节点.新节点的权重就是这两个叶节点的权重之和.然后继续重复这一过程当集合只剩下一个节点时停止,而这个节点就是根节点.

这一算法不总能描述一棵唯一的树,这是因为每步选择出的最小权重节点可能不唯一,在左归并是,两个节点的顺序也是任意的,也就是说,随便哪个都可以作为左分支,或者右分支.

=====================================================

代码来自*

//以下為C++程式碼，在GCC下編譯通過
//僅用於示範如何根據權值構建霍夫曼樹，
//沒有經過性能上的優化及加上完善的異常處理。
#include <cstdlib>
#include <iostream>
#include <deque>
#include <algorithm>
 
using namespace std;
 
const int size=10;
struct node                                 //霍夫曼樹節點結構
{
    unsigned key;                           //保存權值
    node* lchild;                           //左孩子指針
    node* rchild;                           //右孩子指針
};
deque<node*> forest;
deque<bool> code;                           //此處也可使用bitset
node* ptr;                   
int frequency[size]={0};
 
void printCode(deque<bool> ptr);            //用於輸出霍夫曼編碼
 
bool compare( node* a, node* b)
{
return a->key < b->key;
}
int main(int argc, char *argv[])
{
    for(int i=0;i<size;i++)
    {
        cin>>frequency[i];                  //輸入10個權值
        ptr=new node;
        ptr->key=frequency[i];
        ptr->lchild=NULL;
        ptr->rchild=NULL;
        forest.push_back(ptr);
    }//形成森林，森林中的每一棵樹都是一個節點
 
    //從森林構建霍夫曼樹
    for(int i=0;i<size-1;i++)
    {
		sort(forest.begin(),forest.end(),compare);
		ptr=new node;
                //以下代碼使用下標索引隊列元素，具有潛在危險，使用時請注意
		ptr->key=forest[0]->key+forest[1]->key;
		ptr->lchild=forest[0];
		ptr->rchild=forest[1];
		forest.pop_front();
		forest.pop_front();
		forest.push_back(ptr);
	}
    ptr=forest.front();//ptr是一個指向根的指針
    system("PAUSE");
    return EXIT_SUCCESS;
}
 
void printCode(deque<bool> ptr)
{
	//deque<bool>
	for (int i=0;i<ptr.size();i++)
	{
		if(ptr[i])
			cout<<"1";
		else
			cout<<"0";
	}
}

*连接:http://zh.wikipedia.org/wiki/霍夫曼编码

Huffman 编码树