哈夫曼树
通常的编码方法有固定长度和不等长度编码两种。
最优编码方案的目的是使总码长度最短。利用字符的使用频率来编码，是不等长编码方法，使得经常使用的字符编码较短，不常使用的字符编码较长。如果采用等长的编码方案，假设所有字符的编码都等长，则表示n个不同的字符需要位。例如三个不同的字符a,b,c，至少需要2位二进制数表示：a:00，b:01，c:10。如果每个字符的使用频率相等的话，固定长度编码是空间效率最高的方法。
不等长编码方法需要解决两个关键问题：
- 编码尽可能的短。使用频率高的字符编码较短，使用频率低的编码较长，可提高压缩率，节省空间，也能提高运算和通信速度。即频率越高，编码越短。
- 不能有二义性。解决的办法是：任何一个字符的编码不能是另一个字符编码的前缀，即前缀码特性。
设二叉树具有n个带权值的叶节点，那么从根节点到各个节点的路径长度与相应节点权值的乘积的和，叫做二叉树的带权路径长度WPL(Weighted Path Length)
$$WPL = \sum_{i=1}^nW_il_i$$
具有最小带权路径的二叉树称为哈夫曼树（也称最优树）
哈夫曼算法采取的贪心策略是每次从树的集合中取出没有双亲且权值最小的两棵树作为左右子树，构造一棵新树，新树根节点的权值为其左右孩子结点权值之和，将新树插入到树的集合中。
构造哈夫曼树的原则
权值越大的叶节点越靠近根节点
权值越小的叶节点越远离根节点
构造哈夫曼树的过程
给定n个权值${W_1,W_2,…,W_n}$构造n棵树只有一个叶节点的二叉树，从而得到一个二叉树的集合$F={T_1,T_2,…,T_3}$
在F中选取根节点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这可二叉树根节点的权值作为其左、右子树根节点权值之和
在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中
哈夫曼编码
规定哈夫曼树中的左分支为0，右分支为1，则从根节点到每个叶节点锁经过的分支对应的0和1组成序列便为该节点对应字符的编码。这样的编码称为哈夫曼编码。
哈夫曼编码的特点：权值越大的字符编码越短，反之越长
在一组字符的哈夫曼编码中，不可能出现一个字符的哈夫曼编码是另一个哈夫曼编码的前缀。
例如 $100,001,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
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
| #include <stdio.h>
#include <stdlib.h>
#define MAXVALUE 10000
#define MAXBIT 100
#define MAXLEAF 30
#define MAXNODE MAXLEAF*2-1
typedef struct HuffmanNode {
char value;
int weight;
int parent;
int left;
int right;
} HuffmanNode, *PtrHuffmanNode;
typedef struct HuffmanCode {
int bit[MAXBIT];
int start;
} HuffmanCode, *PtrHuffmanCode;
void createNode(PtrHuffmanNode node, int weight, char value) {
node->value = value;
node->weight = weight;
node->parent = -1;
node->left = -1;
node->right = -1;
}
void initialHuffmanTree(PtrHuffmanNode huffmanNode, int n) {
int i, j, m1, m2, x1, x2;
for(i = 0; i < n-1; i ++) {
m1 = m2 = MAXVALUE;
x1 = x2 = 0;
for(j = 0; j < n+i; j ++) {
if(huffmanNode[j].weight < m1 && huffmanNode[j].parent == -1) {
m2 = m1;
x2 = x1;
m1 = huffmanNode[j].weight;
x1 = j;
} else if(huffmanNode[j].weight < m2 && huffmanNode[j].parent == -1) {
m2 = huffmanNode[j].weight;
x2 = j;
}
}
huffmanNode[x1].parent = n+i;
huffmanNode[x2].parent = n+i;
huffmanNode[n+i].weight = m1+m2;
huffmanNode[n+i].left = x1;
huffmanNode[n+i].right = x2;
printf ("x1.weight and x2.weight in round %d: %d, %d\n", i+1, huffmanNode[x1].weight, huffmanNode[x2].weight);
}
}
void huffmanDecode(PtrHuffmanNode huffNode, PtrHuffmanCode huffCode, int n) {
HuffmanCode cd;
int i, j, c, p;
for(i = 0; i < n; i ++) {
cd.start = n-1;
c = i;
p = huffNode[c].parent;
while(p != -1) {
if(huffNode[p].left == c) cd.bit[cd.start] = 0;
else cd.bit[cd.start] = 1;
cd.start --;
c = p;
p = huffNode[c].parent;
}
for(j = cd.start+1; j < n; j ++) {
huffCode[i].bit[j] = cd.bit[j];
}
huffCode[i].start = cd.start;
}
}
int main(int argc, char *argv[])
{
HuffmanNode node[100];
HuffmanCode code[100];
int n = 8;
for (int i=0; i<2*n-1; i++)
{
node[i].weight=0;
node[i].parent=-1;
node[i].left=-1;
node[i].right=-1;
}
createNode(&node[0], 3, 'A');
createNode(&node[1], 5, 'B');
createNode(&node[2], 11, 'C');
createNode(&node[3], 23, 'D');
createNode(&node[4], 29, 'E');
createNode(&node[5], 14, 'F');
createNode(&node[6], 7, 'G');
createNode(&node[7], 8, 'H');
initialHuffmanTree(node, n);
huffmanDecode(node, code, n);
for(int i = 0; i < n; i ++) {
printf("%c:huffman code is:", node[i].value);
for(int j = code[i].start+1; j < n; j ++) {
printf("%d", code[i].bit[j]);
}
printf("\n");
}
return 0;
}
|
