数据结构(霍夫曼树)

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

很容易发现，上述字串中，虽然每个字母只用了一个字节来编码，但是每个字节的前面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

此时，字串的编码只有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