huffman编码

缘起

Huffman编码树要从PFC（prefix-free code 无歧义前缀编码方案） 谈起.

我们考虑只包含5个字符的字符集 {‘A’, ‘E’, ‘G’, ‘M’, ‘S’} 的编码. 如果采用下面的编码方案的话,

字符 编码
A 00
E 01
G 10
M 11
S 111

那么请问如果译码机收到 111xxxx 这种字符串, 到底是将11译为M 还是将111译为S呢? 貌似还要看后面的. 但是译码之事，生死攸关, 怎么容许算法延迟? 所以我们需要提供一种只需要译码机顺序读取密文就可以无歧义的解码的算法. 这就要求编码方案有无歧义的特点. 符合这种特点的编码方案就是 PFC.

分析

其实究其会歧义的原因， 我们就知道根本是因为M是S的前缀导致的. 所以PFC名字由此得来. 我们不难得到PFC的充要条件——编码方案中的每个字符，任何2个字符没有一个是另一个的前缀. 所以不难给出下面一种PFC方案

字符 编码
A 00
E 01
G 10
M 110
S 111

任何一个字符编码不是另一个字符编码的前缀. 所以这是一个合格的PFC方案. 其实如果将0表示左子树（向左走），1表示右子树（向右走），则这两个方案分别表示两棵树. 称为PFC树.

右边的树不是PFC树，因为存在非叶子节点M. 而且你也看到了，如果使用右边的树进行编解码的话，则对’MESSAGE’编码之后的01串’110 01 111111 00 10 01’ 进行译码会存在歧义.

现在我们通过PFC树可以方便的为含有n个字符的字符集生成合格的编码方案. 既然有这么多PFC编码方案，那么我们自然对性能最优的那个格外感兴趣. 那么首先, 我们得定义什么叫做性能最优

考量一种编码方案的优劣的最重要的性能指标就是译码之后的密文长度

显然, 在同等带宽条件下, 生成的密文越短越好. 最短的那个我们不难知道就是一棵完全二叉树. 假设字符集有n个字符, 其中最底层的叶子有x个，则该编码树的节点个数为
$$
(x/2+n-x)2-1+x=2n-1
$$
其中x可以通过
$$
x/2+(n-x)=2^{k-1}
$$
确定，其中, k满足
$$
2^k-1\le2n-1\le2^{k+1}-1
$$
简化之后,k 满足
$$
\log_2n<k\le\log_2n+1
$$
亦即
$$
k = ceil(\log_2n)+1
$$
其中ceil是地板函数. 从而
$$
x = 2(n-2^{ceil(\log_2n)})
$$
拿n=5而言, x=2, 综上,含有n个字符的字符集生成的编码树的节点个数是2n-1. 这棵PFC编码树就叫做Huffman树. 而且不难知道, Huffman树是所有叶子的平均高度最短的PFC树. 貌似我们已经找到了最优编码方案了!

但事实上并非如此, 因为人类语言中各个字母的出现频率不一样. 就英文字母而言, E出现的频率就很高. 但是上述Huffman树却是平均而论的. 所以Huffman树的构建必须要带权重! 即带权Huffman树.

代码

Huffman树的生成算法其实很简——因为已经有n个叶子节点已经给出了. 所以我们要做的事情就是生成那n-1个非叶子节点即可. 而生成的核心思想就是贪心. 即决定第i+1个节点就是选择[1,…,i] 中尚无父节点的权重最小的两个节点作为其左右孩子. 

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include "stdafx.h"
#include <iostream>
#include <stack>
#include <string>

#define LOCAL

using namespace std;
typedef char arrT[100];

struct Node
{
	char data; // 节点数据(只对叶子节点有效)
	int parent; // 父节点在数组中的索引
	int index; // 自己在数组中的索引
	int lc; // 左娃在数组中的索引
	int rc; // 右娃在数组中的索引
	float weight; // 权重
};

// 设定 a[1,...,i) 中尚没有父节点的并且权重最小的2个节点的索引存入 j和k中(j是最小, k是次小), 思想类似于大根堆
void select(Node *a, int i, int& j, int& k)
{
	float f[2];
	int x;
	// 先取头两个没有父节点的两个作为f[0]、f[1]作为初始值
	for (x = 1; x < i; x++)
	{
		if (!a[x].parent)
		{
			f[0] = a[x].weight;
			j = x;
			break;
		}
	}
	for (x++;x<i;x++)
	{
		if (!a[x].parent)
		{
			f[1] = a[x].weight;
			k = x;
			break;
		}
	}
	if (f[0]>f[1])swap(f[0],f[1]); // 保证 f[0]<=f[1]
	// 继续遍历
	for (x++; x <i; x++)
	{
		if (a[x].parent) continue; // 只考察尚无父节点的节点
		if (a[x].weight >= f[1]) continue; // 如果>=f[1]的话, 则肯定比f[0]大, 则一定不会是最小的两个权重之一
		if (a[x].weight < f[0]) // 比最小还小
		{
			f[0] = a[x].weight;
			f[1] = a[k = j].weight; // 最小变次小
			j = x; // 更新最小
		}
		else if(a[x].weight < f[1]) f[1] = a[k = x].weight; // 即 a[x] 的权重  >=f[0] 但是<f[1]，则仅仅更新次小
	}
}

// 生成含有n个节点的Huffman树， 返回Huffman树数组的第0个元素
Node *generateHuffman(int n)
{
    Node *Huffman = new Node[(n<<1)-1]; // 注意, 数组的第0个索引不存数据, 因为我们打算使用parent为0表示尚没有父节点, 堆内存是需要程序员手动释放的
	memset(Huffman, 0, (n<<1)*sizeof(Node)); // 初始化
	// 初始化Huffman树的叶子
	for (int i = 1; i<=n; i++)
	{
		Huffman[i].parent = Huffman[i].lc =Huffman[i].rc = 0;
		getchar(); // 吸收多余换行符
		Huffman[i].data = getchar();
		scanf_s("%f", &Huffman[i].weight);
		Huffman[i].index = i;
	}
	int _min1, _min2; // 1,2,...,i 中最小的两个节点的索引， 所以Huffman树算法本质就是一种贪心
	for (int i = n+1; i<=(n<<1)-1; i++) // 开始生成Huffman树的非叶子节点
	{
		select(Huffman, i, _min1, _min2);
		Huffman[i].lc = _min1;
		Huffman[i].rc = _min2;
		Huffman[_min1].parent = Huffman[_min2].parent = i;
		Huffman[i].weight = Huffman[_min1].weight+Huffman[_min2].weight;
		Huffman[i].index = i;
	}
	// 返回Huffman树的根节点
	return Huffman;
}


// 生成码表, 从叶子出发
arrT* generatecodetable(Node *root, int n)
{
	char (*result)[100] = new char[30][100]; // 因为这个指针是要返回去的, 所以一定要是堆内存, 而不能是栈内存
	for (int i = 1; i<= n; i++)
	{
		Node *p = root+i;
		stack<int> s;
		while(p->parent) // 沿着路径上去
		{
			if (root[p->parent].lc == p->index) // 左边为0, 右边为1  代码在里面运行的时候, p->parent都是有值的
			{
				s.push(0);
			}
			else
			{
				s.push(1);
			}
			p=root+root[p->parent].index;
		}
		int top = 0;
		while(!s.empty())
		{
			result[root[i].data - 'A'][top++] = s.top()+'0';
			s.pop();
		}
		result[root[i].data - 'A'][top++] = 0;
	}
	return result;
}

// 使用码表codetable进行编码
char* encode(arrT* codetable, string message)
{
	char *a = new char[100];
	a[0] = 0;
	for (int i = 0; i< message.length(); i++)
	{
		strcat(a, codetable[message[i]-'A']);
	}
	return a;
}

// 使用Huffman树解码 arr 是Huffman数组的起点, 而root是Huffman树的根节点
char *decode(Node *arr, Node *root,char *str)
{
	int i = 0, j = 0;
	Node *p = root;
	while(str[i])
	{
		if (str[i]=='1')
		{
			p = arr+p->rc; // 向右移动
		}
		else
		{
			p = arr + p->lc; // 向左移动
		}
		i++;
		if (!p->lc && !p->rc) // 如果到了叶子节点
		{
			str[j++] = p->data;
			p = root; // 重回根节点
		}
	}
	str[j++] = 0;
	return str;
}

int main()
{
#ifdef LOCAL
	/*测试数据是
		5
		A 0.623
		E 0.906
		G 0.224
		M 0.099
		S 0.290*/
	freopen("d:\\data.in", "r", stdin);
#endif
	int n;
	printf("请输入字符集包含的字符的个数");
	scanf_s("%d", &n);
	cout << "输入各个节点的字符和相应权重" << endl;
	Node *Huffman = generateHuffman(n); // 因为返回的是指向堆内存的指针, 所以是可行的
	arrT *codetable = generatecodetable(Huffman, n); // 得到码表
	string message = "MESSAGE";
	char *encodemessage = encode(codetable, message); // 密文
	cout << encodemessage << endl; // 编码
	cout << decode(Huffman, Huffman + (2*n-1), encodemessage) << endl; // 解码
	return 0;
}