1. Huffman编码
1.1 问题起源
假设在数据通信中，有一字串"ABABBCBBA"需要传送，一般会将这些字符进行编码，然后按编码后的二进制位进行传输，例如这些字母的ASCII码取值为：
A(65): 0100 0001
B(66): 0100 0010
C(67): 0100 0011
因此最“简单”的方式，就是将上述字串直接使用字符编码方式转换成如下01序列进行传输（总共72位）：
01000001 01000010 01000001 01000010 01000010 01000011 01000010 01000010 01000001
1
很容易发现，上述字串中，虽然每个字母只用了一个字节来编码，但是每个字节的前面6位都是"0100 00"，因此完全可以将这无效编码去掉，变成：
A: 01
B: 10
C: 11
这样一来，字串"ABABBCBBA"编码后就变成了：
0110 0110 1011 1010 01
整个编码长度缩减为18位。但这并未达到压缩的极致，仔细观察上述ABC三个字符的编码，会发现其实把A的编码从01换成0也可以，这又省掉了一位。字串"ABABBCBBA"编码后就变成了：
0100 1010 1110 100
二进制编码进一步缩短为15位。这里有一点要着重注意，将A的编码从01换成0是可以的，但是不能换成1，因为B和C的编码都是从1开始的，如果A的编码是1的话，在译码阶段就会出现二义性，比如当出现"11011…"时，就无法区分第一个1究竟是A还是跟后面的1结合形成C。
经过观察又会发现，字串中B出现的概率比A多，因此我们完全可以将性价比更高（即更短）的编码给B，变成：
A: 10
B: 0
C: 11
这样一来，字串"ABABBCBBA"编码后就进一步变成了：
1001 0001 1001 0
1
此时，字串的编码只有13位。并且注意到，由于做了谨慎的处理，逐个读取二进制位译码时，不会发生二义性。
1.2 Huffman编码
在上面的分析中，那种基于字符出现的频次，按频次给不同给不同字符分配长短不一的编码方式，就是Huffman编码的基本思路：
- 找出字串中各个字符的出现频次，如：[A3,B5,C1][A3,B5,C1]。
- 以频次作为叶子节点的权值，构造一棵Huffman树。
- 将Huffman树中所有的左子树的边标记为0，右子树的边标记为1，则每一个叶子节点的路径就是Huffman编码的数值。
以上述字串"ABABBCBBA"为例，这三个节点的频次构成的Huffman树是：
在此Huffman树中，按照上述编码的思路，将左子树路径标记为0，右子树路径标记为1：
那么[A3,B5,C1][A3,B5,C1]的路径分别是：
A3A3: 10
B5B5: 0
C1C1: 11
这刚好就是上述描述的最优长短编码。下面，来看Huffman树是怎么构建的。
2. Huffman树
2.1 基本概念
Huffman树一般称为霍夫曼树，又称为最优二叉树，为什么是最优呢？以下面的二叉树为例，先弄清几个概念：
- 权
有时会用一个数值来表征一个节点，比如上述每个节点中的数字。这些权值具体到实际应用当中可以表达一种程度、某个标值等，比如Huffman编码中会提到的某个字符出现的频率。 - 路径及路径的长度
从根节点开始，到叶子节点的一条通路，比如上图中红色虚线所示的路径：3、2、8、13、2、8、1
路径所包含的边的数目，称为路径的长度，比如上述从根节点3到叶子节点1的路径中，包含了3条边，因此该路径的长度为3。 - 带权的路径长度
如果在计算路径长度时，考虑到达某个节点所经过的边数目，将这些数据累加起来作为路径长度的话，这样的路径长度称为带权的路径长度。
比如上述路径3、2、8、13、2、8、1，其带权路径是：
3∗0+2∗1+8∗2+1∗3=2+16+3=213∗0+2∗1+8∗2+1∗3=2+16+3=21
- 树的带权路径长度
容易理解，树的带权路径长度就是所有的叶子节点的带权路径长度之和，称为WPL（即Weighted Path Length）。还是以上述二叉树为例，此处WPL应等于：
(1∗2+2∗6)+(1∗2+2∗8+3∗1)+(1∗5)=14+21+5=41(1∗2+2∗6)+(1∗2+2∗8+3∗1)+(1∗5)=14+21+5=41
很明显，如果变换一下各个带权节点的位置，则可以改变整棵树的带权路径的长度，例如做如下变换，让权值大的节点尽量往根部靠近（以减少路径长度）：
此时树的带权路径长度为：
(1∗6+2∗1)+(1∗5+2∗2)+(1∗5+2∗3)=8+9+11=28(1∗6+2∗1)+(1∗5+2∗2)+(1∗5+2∗3)=8+9+11=28
2.2 Huffman树的定义
给定N个权值为N的叶子节点，构建一棵树，如果这棵树的WPL达到最小值，就称这样的树为最优树，或霍夫曼树。
如果构建的树是二叉树，那么这样的二叉树称为最优二叉树。
2.3 Huffman树的节点数量
抛出这么一个问题：当待编码的字符有m个时，最终构建出来的霍夫曼树的节点数总共有几个？
当一棵霍夫曼树的叶子节点数 n0=3n0=3 （此处的n0n0就是上述代码中的m）时，整棵霍夫曼树的节点树是多少呢？答案是5。下面是简单的推导过程：
- 假设二叉树节点总数为nn，度为0的节点数为n0n0，度为1的节点数为n1n1，度为2的节点数为n2n2，那么显然有：
n=n0+n1+n2n=n0+n1+n2
- 从另一个角度考察，二叉树的节点总数也等于所有节点的子节点个数之和：n0n0节点的子节点的总数是0∗n00∗n0，n1n1节点的子节点总数是1∗n11∗n1，n2n2节点的子节点总数是2∗n22∗n2，又由于根节点不是任何节点的子节点，因此有：
n=0∗n0+1∗n1+2∗n2+1=n1+2∗n2+1n=0∗n0+1∗n1+2∗n2+1=n1+2∗n2+1
- 结合上述两个式子得到：
n2=n0−1n2=n0−1
- 霍夫曼树中，所有的权值节点均是叶子结点，且不存在度为1的节点，即n1=0n1=0，因此有：
n=n0+n1+n2=n0+n0−1=2∗n0−1n=n0+n1+n2=n0+n0−1=2∗n0−1
结论：
当权值节点数量为n0n0时，霍夫曼树的节点总数为2∗n0−12∗n0−1
2.4 Huffman树构建的基本思路
从以上带权路径最小化基本思路出发，可以构建一棵Huffman树。仍然以字串"ABABBCBBA"为例，基本思路是：
- 计算各个字符所出现的频次：
“ABABBCBBA”
A:出现3次
B:出现5次
C:出现1次
不同字符的数量是：3
- 将这些频次作为节点的权值，放在一个数组中：
int m = 3; // 3是子串所出现不同的字符数量[A, B, C]
int huffmanTree[2*m-1] = {3, 5, 1, 0, 0}; // 此处伪代码，不可编译
这些权值节点就是霍夫曼树的叶子节点，如下图所示：
权值节点
- 从这些叶子节点出发，逐步构建整棵霍夫曼树：在已知的叶子中找到两个最小且无父节点的叶子，接他们权值相加并将和放入后续数组中，比如找到3和1之后，生长出节点4：
huffmanTree[] = {3, 5, 1, 4, 0};
在上述操作过程中，关键是要标注节点之间的关系，必须指明3和1是4的子节点，4是它们的父节点，这样，在下一轮构建中3和1将不再参与，最终构建出霍夫曼树：
huffmanTree[] = {3, 5, 1, 4, 9};
- 从叶子节点出发，向上寻找根节点，将沿途经历过的路径加以编码（比如左路径为0、右路径为1），再反转，得到的就是改节点的霍夫曼编码，比如：从节点3开始，到根节点9，其经过的路径编码是：01，因此权值为3的节点A霍夫曼编码就是10。最终得到：
[A3,B5,C1][A3,B5,C1]的路径分别是：
A3A3: 10
B5B5: 0
C1C1: 11
2.5 Huffman树的构建步骤
- 【步骤1】准备一个存储空间为 2∗m−12∗m−1 （即2∗n0−12∗n0−1）的数组来存储霍夫曼树：
// 霍夫曼树节点
typedef struct
{
char ch; // 字符
int weight; // 权重，即字符出现的频次
int parent; // 父节点位置
int lchild; // 左子树位置
int rchild; // 右子树位置
}huffmanTreeNode;
// 统计字符串s中的各个字符
void initHuffmanTree(const char *s, huffmanTreeNode **ht, int *pm)
{
// 统计s中不同字符的个数，放入*pm中
// 以及各个字符出现的频次，放入alphabet中
*pm = 0;
int alphabet[26] = {[0 ... 25]=0};
for(int i=0; s[i]!='\0'; i++)
alphabet[s[i]-'A']++;
for(int i=0; i<26; i++)
{
if(alphabet[i] != 0)
(*pm)++;
}
// 存储各个字符出现的频次
// 所需的霍夫曼节点总数n = 2*m - 1
// [a1, a2, a3, ..., am, 0, 0, ... , 0]
// | <-- m个字符 --> |
*ht = calloc((*pm)*2-1, sizeof(huffmanTreeNode));
for(int i=0,k=0; i<26; i++)
{
if(alphabet[i] != 0)
{
(*ht)[k].ch = 'A' + i;
(*ht)[k].weight = alphabet[i];
k++;
}
}
}
- 【步骤2】根据权值节点数组，构建霍夫曼树：
// 函数功能：在数组ht中找到两个最小值，分别用p1和p2标识其下标
// 参数解析:
// ht：霍夫曼树数组
// end：数组边界下标
// p1与p2：最小值位置下标
void find(huffmanTreeNode *ht, int end, int *p1, int *p2)
{
int min1 = 0;
int min2 = 0;
for(int i=0; i<=end; i++)
{
if(ht[i].parent != 0)
continue;
if(min1 == 0)
{
min1 = ht[i].weight;
*p1 = i;
continue;
}
else if(min2 == 0)
{
if(min1 < ht[i].weight)
{
min2 = ht[i].weight;
*p2 = i;
}
else
{
min2 = min1;
min1 = ht[i].weight;
*p2 = *p1;
*p1 = i;
}
continue;
}
if(ht[i].weight < min1)
{
min1 = ht[i].weight;
*p2 = *p1;
*p1 = i;
}
else if(ht[i].weight < min2)
{
min2 = ht[i].weight;
*p2 = i;
}
}
}
void createHuffmanTree(huffmanTreeNode *ht, int m)
{
// 从叶子开始，构建霍夫曼树
int p1, p2;
for(int i=m; i<2*m-1; i++)
{
// 在ht中找到两个最小且未有父节点的节点
// 并将其用p1与p2标识出来
find(ht, i-1, &p1, &p2);
ht[p1].parent = i;
ht[p2].parent = i;
ht[i].weight = ht[*p1].weight + ht[*p2].weight;
ht[i].lchild = *p1;
ht[i].rchild = *p2;
}
}
至此，一棵Huffman树ht就创建完毕了，有了ht之后，可以设计一个函数来展示从外部命令行输入的字串对应的编码：
2.6 Huffman码表
由上述1.2小节知道，如果有了一棵Huffman树，那么叶子节点的编码就是从叶子到根的路径的翻转，比如下图：
上图中，如果约定左子树为0，右子树为1，那么叶子节点3到根的路径就是01，那么最终叶子节点3的编码就是10。
下述代码，实现输出ht中第i个节点的Huffman编码值：
void huffmanCode(huffmanTreeNode *ht, int i)
{
char hcode[20];
int k;
for(k=0; ht[i].parent != 0; k++)
{
if(ht[ht[i].parent].lchild == i)
hcode[k] = '0';
else if(ht[ht[i].parent].rchild == i)
hcode[k] = '1';
i = ht[i].parent;
}
for(int m=k-1; m>=0; m--)
printf("%c", hcode[m]);
printf("\n");
}
将以上各个代码模块整合起来，可以得到Huffman编码的Demo程序：
int main(int argc, char const *argv[])
{
int m;
huffmanTreeNode *ht;
// 初始化一棵霍夫曼树，将已统计的频次作为叶子
// 放入树的前m项中：[3, 5, 1, 0, 0, ... , 0]
initHuffmanTree(argv[1], &ht, &m);
// 从叶子开始，构建霍夫曼树
createHuffmanTree(ht, m);
// 根据已构建的霍夫曼树，生成霍夫曼编码表
printf("霍夫曼编码表:\n");
for(int i=0; i<m; i++)
{
printf("%c:", ht[i].ch);
huffmanCode(ht, i);
}
return 0;
}
执行效果：
gec@ubuntu:~$ ./huffmanCode ABABBCBBA
霍夫曼编码表:
A:01
B:1
C:00