Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 其它算法 » 

哈夫曼编码

哈夫曼编码(Huffman Coding)是一种非常经典的编码方式,属于可变字长编码(VLC)的一种,通过构造带权路径长度最小的最优二叉树以达到数据压缩的目的。
哈弗曼编码实现起来也非常简单,在实际的笔试面试过程中有可能会遇到,本文主要介绍具体的编码原理,以及使用STL的优先队列进行实现。

一 编码原理

哈夫曼编码是一种可变长的编码,它依据字符出现的概率来决定字符编码的长度,使得出现概率大的字符编码长度短,出现概率小的字符的编码长度长,于是可以减少整体的编码的长度。

哈弗曼编码时首先根据待编码的文本统计出每个字符出现的概率,组成初始的节点。然后每次取出概率最小的两个节点,新建一个节点,使得新建节点的左右儿子为选取的两个节点,并且其概率是两个节点概率之和,把新建的节点再放进所有节点中重新选择最小的两个节点。重复此过程直到只剩一个节点,这个就是哈夫曼树的根节点。

以下以字符串"aaaaaabbbbccddd"为例进行说明,为了方便,以字符出现的频数来代替频率(实际中通常使用的是频率,二者效果上是一样的),经过统计,可以知道每个字符出现的频数为

a b c d
6 4 2 3

具体建树过程如下:

  1. 首先节点权值为6、4、2、3,选择最小的2和3,组成一个根节点为5的组合节点。
  2. 当前节点权值为6、4、5,选择最小的4和5,组成一个根节点为9的组合节点。
  3. 当前节点权值为6、9,选择最小的6和9,组成一个根节点为15的组合节点。
  4. 当前节点权值为15,只有一个节点,哈夫曼树建立完成。

图示如下:

Huffman

要从哈夫曼树得到每个字符的编码,只要在哈夫曼树中从根节点遍历到该字符节点,每次向左走时加一个0,向右走时加一个1,最终得到的字符串即为该字符的编码字符串。

如从上图可以看到,a的编码为0,b的编码为10,c的编码为110,d的编码为111。

当遇到一个新的字符串时,比如说"abcd",要对其编码,只需要把其中的每个字符相应地替换成其编码字符串即可。

当已知一个编码后的字符串,比如说"010110111",要对其解码时,只需从左到右依次扫描该编码串,当读到的串在哈弗曼编码表里有对应的字符时即解码为该字符,然后继续扫描。

在这个例子中,读到第一个0时即可解码为a,读到10时可以解码为b,以此类推,最终得到解码后的结果为abcd。

哈夫曼编码之所以可以这样解码,是因为它是一种前缀编码,任何一个字符的编码都不会是另一个字符编码的前缀。于是给定一个编码后的串,其解码的结果是唯一的。

二 代码实现

这里的哈夫曼树的节点主要包含两个成员:字符及其频率,另外还必须有其左右儿子指针,父亲节点指针可以看情况添加,这里暂时不考虑。

为了方便,还添加了一个构造函数,可以给成员赋默认值。

struct node //哈夫曼树节点
{
	char ch;				//字符
	double freq;			//出现频率
	node *lchild, *rchild;	//左右儿子
	node(char c = 0, double f = 0, node *l = NULL, node *r = NULL) : 
		ch(c), freq(f), lchild(l), rchild(r){}
};

为了提高效率,程序中使用了STL中的优先队列来选择权值最小的节点。队列的成员是节点的指针,为了选择权值最小的节点,需要自己定义比较的规则,以下是定义比较规则的仿函数,实质就是一个重载了括号运算符的类。

注意实现最小的权值优先,仿函数里应该使用的是大于运算。

struct cmp //仿函数,实现最小优先队列
{
	bool operator()(node*& a, node*& b)
	{
		return a->freq > b->freq;
	}
};

然后是具体的建树过程。首先需要统计字符出现的次数,可以非常方便地使用STL的map实现。然后构造初始节点送入优先队列,再循环取出最小的两个节点,生成新的节点放入队列。直到队列只剩一个节点,即为树的根节点。

node* createTree(string str) //对一段文本构建哈夫曼树
{
	//统计字符集及其出现频数
	map<char, int> charSet;
	for (int i = 0; i < str.length(); i++)
		charSet[str[i]]++;

	//查看统计结果
	//for(map<char, int>::iterator p = charSet.begin(); p != charSet.end(); p++)
	//	cout << p->first << " " << p->second << endl;;

	//初始节点进入优先队列
	priority_queue<node*, vector<node*>, cmp> que;
	for(map<char,int>::iterator p = charSet.begin(); p != charSet.end(); p++)
		que.push(new node(p->first, (double)p->second / str.length()));

	//每次取出频率最小的两个节点,生成一个新的节点并重新入队
	while (que.size() > 1)
	{
		node *l = que.top(); que.pop();
		node *r = que.top(); que.pop();
		node *newnode = new node(0, l->freq + r->freq, l, r);
		que.push(newnode);
	}

	return que.top();
}

得到哈夫曼树之后基本就完成了,接下来可以遍历哈夫曼树得到每个字符的编码串。注意每次向左走时加0,向右走时加1,到达叶子节点即为该字符的编码。

这里只是简单打印了编码表的信息,没有保存起来,如果需要可以再次使用STL的map进行保存。

void printInfo(const node *tree, string code) //递归打印编码信息
{
	if (tree->lchild == NULL && tree->rchild == NULL)
	{
		cout << tree->ch << ": " << code << endl;
		return;
	}

	if (tree->lchild != NULL) printInfo(tree->lchild, code + '0');
	if (tree->rchild != NULL) printInfo(tree->rchild, code + '1');
}

解码时可以在遍历编码串的同时沿着哈夫曼树走,到达叶子节点时即得到一个解码字符,同时再次回到根节点继续遍历。最后得到解码的结果。

string decode(const node *tree, string str) //解码
{
	string ret = "";
	const node *p = tree;
	for (int i = 0; i < str.length(); i++)
	{
		p = str[i] == '0' ? p->lchild : p->rchild;	

		if (p->lchild == NULL && p->rchild == NULL) //得到一个字符
			ret += p->ch, p = tree;
	}
	return ret;
}

因为这里的节点都是使用new运算符动态申请得到,不再使用时需要释放掉申请到的资源,以免造成内存泄露。

void deleteTree(node *tree) //释放哈夫曼树申请的节点
{
	if (tree->lchild != NULL) deleteTree(tree->lchild);
	if (tree->rchild != NULL) deleteTree(tree->rchild);
	delete(tree);
}

下面是一个简单的测试例子,看程序是否正常运行。

int main ()
{
	string encodeStr = "aaaaaabbbbccddd";
	node *tree = createTree(encodeStr);
	printInfo(tree, "");

	string decodeStr = "010110111";
	string str = decode(tree, decodeStr);
	cout << decodeStr << ": " << str << endl;

	/*运行结果
	a: 0
	b: 10
	c: 110
	d: 111
	010110111: abcd
	*/
}
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论