哈夫曼编码

哈夫曼编码，又称为霍夫曼编码，它是现代压缩算法的基础。假如我们需要将字符串ABBBCCCCCCCCDDDDDDEE通过二进制编码进行传输，那应该怎么将字符转换为二进制码？

方法一：转换为ASCII码

直接将字母转换为对应的ASCII码数字，再将ASCII码转换为对应的二进制码

字母	ASCII码	二进制码
A	65	100 0001
B	66	100 0010
C	67	100 0011
D	68	100 0100
E	69	100 0101

显然这样的方式使得二进制码变得很长。

方法二：事先约定5个字母对应的二进制码

字母	ASCII码	二进制码
A	0	0
B	1	1
C	2	10
D	3	11
E	4	100

此时ABBBCC的二进制编码为：01111010，但是我们并不能对其进行解码，这是因为：对于二进制码的第一位0，我们可以立刻判断出是字母A，但对于之后的1111，可以解码为BBBB，也可以解码为DD，也可以…，在此无法进行解码的原因是：存在某个字母的编码是其他字母的前缀，甚至有字母的编码是由其他字母的编码组成。

字母	ASCII码	二进制码
A	0	000
B	1	001
C	2	010
D	3	011
E	4	100

对此我们可以约定每三个二进制位代表一个字母，那么就不存在编码的前缀关系了，解码的问题也可以顺利解决。原字符串的二进制编码为：000001001001010010010010010010010010011011011011011011100100，可以预见的是，方法二的编码一定比方法一短了很多。

方法三：哈夫曼编码

如果使用哈夫曼编码，该字符串可以压缩至41个二进制位，约为原来长度的68.3%。
在构建哈夫曼编码时，我们首先要统计字符串中每个字母的出现频率（这是为了将短的二进制码分配给频率高的字母，以达到缩短二进制码长度的目的）,在这里直接通过出现次数进行比较。

A	B	C	D	E
1	3	8	6	2

利用这些权值，我们就可以构建一棵哈夫曼树（又称为霍夫曼树、最优二叉树）。

构建哈夫曼树

假设我们有n个不同的字母，对应n个权值。

1. 构建n棵只有根节点的二叉树构成森林，根节点的值为n个字母与权值

2. 在森林里选出两棵根节点值最小的树进行合并，合并方式为生成一棵新树，根节点值为两棵树根节点值权值之和，且让两棵树作为新树的左右子树。将两棵树从森林删除，新树加入森林。

3. 重复 2 的操作，直到森林只剩一棵树为止，该树即为哈夫曼树

构建哈夫曼编码

此时哈夫曼树构建完成了，下面我们要对各个字母进行编码，编码原则是，从哈夫曼树的根节点开始，进入左子树则编码号加0，进入右子树则编码号加1，就可以得到对应字母的二进制编码。

各个字母的编码如下：

A	B	C	D	E
1110	110	0	10	1111

此时字符串：ABBBCCCCCCCCDDDDDDEE的哈夫曼编码是1110110110110000000001010101010101111，显然比方法二中的编码短了。

总结

1. 那么为什么通过哈夫曼编码后得到的二进制码不会有前缀的问题呢？

这是因为在哈夫曼树中，每个字母对应的节点都是叶子节点，而他们对应的二进制码是由根节点到各自节点的路径所决定的，正因为是叶子节点，每个节点的路径不可能和其他节点有前缀的关系。

2. 为什么通过哈夫曼编码获得的二进制码短呢？

因为哈夫曼树是带权路径长度最短的树，权值较大的节点离根节点较近。而带权路径长度是指：树中所有的叶子节点的权值乘上其到根节点的路径长度，这与最终的哈夫曼编码总长度成正比关系的。对于第二种方式的编码，我们也可以按0左1右的规则构成一棵二叉树，但显然他没有按权值高的节点离根节点近的原则去构建二叉树，带权路径长度更长，二进制码也更长。