哈夫曼编码

发表于
字数统计 639

什么是哈夫曼编码

在数据传送时，信息表现为0和1的二进制形式。为了提高传输的速度，可以采用变长的编码方式，寻找更优的编码方式。同时，必须要保证编码不存在二义性（任意字符编码都不是其它字符编码的前缀）。

哈夫曼编码就是符合上述要求的编码方式，采用自底向上的形式构造哈夫曼树。按照字符的概率分配码长，实现平均码长最短的编码。

如何进行哈夫曼编码

使用需要传送的字符构造字符集C = {c1, c2, … cn}，并根据字符出现的频率构建概率集W = {w1, w2, … wn}。哈夫曼编码的流程如下：

  • 将字符集C作为叶子节点；
  • 将频率集W作为叶子节点的权值；
  • 使用C和W构造哈夫曼树；
  • 对哈夫曼树的所有分支，左子树分支编码为0，右子树分支编码为1；

通过上述流程，即完成了哈夫曼编码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void HuffmanCode(Node *p, const int numLeafs, string *codes) {
	// p为节点数组的指针，codes为string数组的指针 
	// 用于存储每个节点的哈夫曼码

	// parent表示父节点位置
	int parent;

	// 每次对一个叶子节点进行编码
	// i表示当前叶子节点位置
	for (int i=0; i < numLeafs; i++) {

		// j表示当前节点位置，i是不能在下面循环中改变的
		// 使用j来记录节点的移动过程
		int j = i;

		// 当前节点的父节点位置
		parent = p[i].parent;

		// 从当前叶子节点p[i]开始，找到哈夫曼树的根节点
		// 循环结束条件是此时parent为0，即达到哈夫曼树的根节点
		while(parent != -1) {

			// 如果当前节点是父节点的左子树，则此分支编码为0
			if (p[parent].left == j) {
				codes[i].push_back('0');
			}

			// 如果当前节点是父节点的右子树，则编码为1
			else {
				codes[i].push_back('1');
			}
   
			j = parent;
			parent = p[j].parent;
		}
		cout << codes[i] << endl;
	}
}