此页面用于多媒体技术大作业展示

1. 哈夫曼编码简介

哈夫曼编码通过构建哈夫曼树来生成编码。哈夫曼树是一棵二叉树，其构建过程如下：

  1. 初始化：

    将所有符号作为叶子节点，每个节点的权重为该符号出现的频率。

  2. 构建树：

    重复以下步骤，直到只剩下一个节点：

    • 选择两个权重最小的节点作为子节点，创建一个新节点，其权重为两个子节点权重之和。
    • 将新节点添加到节点集合中，并删除两个子节点。

最终剩下的一个节点即为哈夫曼树的根节点。

2. 构建哈夫曼树

假设有字符集及其频率如下：

字符 频率
A 45
B 13
C 12
D 16
E 9
F 5

步骤1：统计频率

步骤2：构建节点

每个字符作为一个节点。

步骤3：构建哈夫曼树

  1. 按频率排序：F (5), E (9), C (12), B (13), D (16), A (45)
  2. 合并频率最小的两个节点：F 和 E 合并，得到新节点 FE，频率为 14。
  3. 排序并插入新节点：C (12), B (13), FE (14), D (16), A (45)
  4. 重复上述步骤：
    • 合并 C 和 B，得到新节点 CB，频率为 25。
    • 排序并插入新节点：FE (14), D (16), CB (25), A (45)
    • 合并 FE 和 D，得到新节点 FED，频率为 30。
    • 排序并插入新节点：CB (25), FED (30), A (45)
    • 合并 CB 和 FED，得到新节点 CBFED，频率为 55。
    • 排序并插入新节点：CBFED (55), A (45)
    • 最后合并 A 和 CBFED，得到根节点，频率为 100。

构建的哈夫曼树如下图所示：

1
2
3
4
5
6
7
8
9
10
    [100]
   /    \
[45]   [55]
A      /  \
    [25]  [30]
   /  \   /  \
 [12][13][14][16]
  C    B  / \
        [5] [9]
        F    E

步骤4：生成编码

根据哈夫曼树生成编码：

字符 编码
A 0
B 101
C 100
D 111
E 1101
F 1100

3. 哈夫曼编码的最优性证明

3.1 无前缀性

首先，哈夫曼编码是无前缀编码，因为任何字符的编码都不会是其他字符编码的前缀。这是由于哈夫曼树的构造方式决定的，每个叶子节点到根节点的路径唯一。

3.2 最优性

为了证明哈夫曼编码的最优性，我们需要证明它产生的平均编码长度是最小的。假设有另一种无前缀编码方案，平均编码长度为 𝐿′L′。我们要证明哈夫曼编码的平均长度 𝐿≤𝐿′L≤L′。

  • 设字符集为 {𝑥1,𝑥2,…,𝑥𝑛}，每个字符的频率为 𝑝𝑖，编码长度为 𝑙𝑖。
  • 哈夫曼编码的平均长度 𝐿L 为：

$$
L = \sum_{i=1}^{n} p_i l_i
$$

  • 如果存在另一种编码方案，其平均长度为 𝐿′L′，则：

$$
L’ = \sum_{i=1}^{n} p_i l’_i
$$

由于哈夫曼树每次合并的是频率最低的两个节点，并且以贪心方式选择最优合并，因此没有其他合并方案能够产生比哈夫曼编码更短的平均编码长度。

3.3 贪心性质证明

要证明赫夫曼编码为最优前缀码，只需证明最优前缀码问题符合贪心算法的性质即可，即具有最优子结构性质和贪心选择性质。

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
int initHuffmanTree(huffmanTree& HT)
{
	HT = (htNode*)malloc(sizeof(htNode) * (2 * NODENUM));			//给HT分配2 * NODENUM个htNOde大小的htNode类型的数组
	for (int i = 1; i <= 2 * NODENUM - 1; i++)						//下标从1开始到2 * NODENUM
	{
		HT[i].parent = HT[i].lch = HT[i].rch = -1;					//双亲和孩子的值都置为-1
	}
	printf("please input some weight!\n");
	for (int i = 1; i <= NODENUM; i++)								//权值只有1-n个
	{
		scanf("%d",&HT[i].weight);									//给每个结点赋予权值
	}
		char c = getchar();											//这个来接收上面的回车
	printf("please input some data!\n");
	for (int i = 1; i <= NODENUM; i++)
	{
			//scanf("%c ",&HT[i].data);
			char a = getchar();
		if(a == '\n')												//遇到回车就结束
			break;
		else
			HT[i].data = a;											//给每个结点赋予数据
	}
	
	return 1;
}
1.最优子结构性质

最优前缀码问题具有最优子结构性质，即局部最优解就是整体的最优解。

设T是字符集C{a,b,c,d}的最优前缀码，令f(x)=f©+f(d)，证明：T1是字符集C′={a,b,x}的最优前缀码。

证明：假设T1不是字符集C1的最优前缀码，则设字符集C2的最优前缀码为T2，B(T1)>B(T2)。

将字符c、d加入到T2中，作为字符b的子节点，构成的树为T3，则有T3是字符集C的一种编码方案。

由此，B(T)=B(T1)+f©+f(d)，同理有B(T3)=B(T2)+f©+f(d)。

由于B(T1)>B(T2)，所以B(T)>B(T3)。

这说明T不是字符集C的最优前缀码，这与T是字符集C的最优前缀码矛盾，假设不成立，即T1是C1的最优前缀码。

2.贪心选择性质

贪心选择性质决定了存在从最小频率节点开始建树的贪心最优解。

设x、y是C中具有最小频度的两个字符，需证明存在字符集C的一个最优前缀码方案T，使得x、y具有相同的码长，且最后一位编码不同。

如果T中，x、y在最底端同一层，那么T就是贪心选择开始的最优前缀码。

如果T中，x、y不在底端，那么设T中字符b、c是最深的叶子且互为兄弟。

由于x,y是字符集C中频度最小的两个字符，所以有f(x)≤f(b)、f(x)≤f©、f(y)≤f(b)、f(y)≤f©，交换树T中的字符x和字符b得到树T1。

T1:

在树T和T1中，T(x) =T1(b)，T(b) =T1(x)

f(x)-f(b)≤0，T(x) -T(b) ≤0，

故B(T)-B(T1)≥0，B(T)≥B(T1)。

再交换字符y和字符c，得到树T2。

同理可以证明B(T1)≥B(T2)，由此B(T)≥B(T1) ≥B(T2)。

又由于T是字符集C的最优前缀码，所以B(T)≤B(T2)。所以B(T)=B(T2)，即T2中，x、y字符处于最底端同一层，是从贪心选择开始的最优解。

3.4 交换法则证明

通过数学归纳法和交换法则也可以证明哈夫曼编码的最优性：

  1. 对于最小频率的两个符号，最优编码方案一定是把它们合并成一个节点。
  2. 合并后形成的新节点继续应用哈夫曼编码，整体最优。

通过归纳和贪心算法，可以证明哈夫曼编码在每一步都保证了部分最优，最终达到全局最优。

4. 结论

综上所述，通过哈夫曼树的构造过程、无前缀性的保证以及平均编码长度的最优性证明，哈夫曼编码确实是最优的无前缀编码。这种编码方法在数据压缩中广泛应用，能够有效减少存储空间。