封面画师：ツチヤ封面ID：82028519

本文参考视频：小马哥教育(SEEMYGO) 2019年恋上数据结构与算法（第一季）

源码仓库：mofan212/data-structure-and-algorithm (github.com)

辅助学习网址：数据结构和算法动态可视化

PS：本文只介绍一些概念，不进行编码实现！

1. 需求分析

哈夫曼编码（Huffman Coding），又称为霍夫曼编码，它是现代压缩算法的基础。

需求分析

需求： 假设要把字符串【ABBBCCCCCCCCDDDDDDEE】转成二进制编码进行传输。

为了完成需求，可以把字符串转成ASCII编码（65~69，1000001~1000101），比如：

字符串【ABBB】使用ASCII编码转换后，得到二进制数为：1000001100001010000101000010

但是有点冗长，如果希望编码更短应该怎么做呢？

问题解决

我们可以先约定 5 个字母对应的二进制数，比如：

A -> 0
B -> 1
C -> 10
D -> 11
E -> 100

然后字符串【ABBB】就可以表示为【0111】，自我感觉良好？😂

那如果我们把【0111】传输给别人，别人进行解码呢？

一下子就出问题了，【0111】可以解码成【ABBB】、【ADB】、【ABD】，那到底哪个是对的就不知道了。

造成这种问题的主要原因是：其中一个字母的编码是另外一个字母编码的前缀。比如 B 的编码是 D 的编码的前缀，因此就导致编码【0111】可以表示成多个字符串。

既然如此，那应该怎么办？

其中一个方法就是使用ASCII编码，可前面不是说了吗？这种编码太长了！兜兜转转又回到最初的起点（BGM响起！🎵）？

当然还有另外的办法，我们可以规定另外一套符合要求的编码，比如：

A	B	C	D	E
000	001	010	011	100

这样的编码就没问题了，就不会出现“一个字母的编码是另外一个字母编码前缀”的情况了。

使用这套编码就可以对字符串【ABBBCCCCCCCCDDDDDDEE】进行转换就不会出现问题了：

【000001001001010010010010010010010010011011011011011011100100】

使用我们自己定义的这套编码，一共20个字母，转成了60个二进制位。

但如果我们使用哈夫曼编码，可以压缩至41个二进制位，约为原来长度的 68.3% 。

那哈夫曼编码是什么呢？👇

2. 哈夫曼树

先介绍一个哈夫曼树，那什么是哈夫曼树，或者如何构建哈夫曼树呢？

构建哈夫曼树

我们先计算出每个字母出现的频率（权值，这里可直接用出现次数），【ABBBCCCCCCCCDDDDDDEE】

A	B	C	D	E
1	3	8	6	2

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

假设有 n 个权值：

1、以权值作为根节点构建 n 棵二叉树，组成森林；

2、在森林中选出 2 个根节点最小的树合并，作为一棵新树的左右子树，且新树的根节点为其左右子树根节点之和；

3、从森林中删除刚才选取的 2 棵树，并将新树加入森林；

4、重复 2、3步骤，直到森林只剩一棵树为止，该树即为哈夫曼树。

图示：

构建哈夫曼树

3. 哈夫曼编码

构建哈夫曼编码

有了哈夫曼树，我们就可以构建出哈夫曼编码。

从根节点出发，到权值节点，经过 left 时记为 0 ，经过 right 时记为 1 ，就可以得出这5个字母对应的哈夫曼编码：

比如：

对于 C，从根节点到 C ，经过一次 left，因此 C 的编码是【0】

对于B，从根节点到 B ，先经过两次 right，再经过一次 left，因此 B 的编码是【110】

最终得到如下编码：

A	B	C	D	E
1110	110	0	10	1111

对最开始给出的字符串【ABBBCCCCCCCCDDDDDDEE】，经过哈夫曼编码可得：

【11101101101100000000010101010101011111111】

共41个二进制位，约为原来长度的 68.3% ，压缩 30% 。

尽管我们将字符串使用哈夫曼编码构建成了二进制编码，但是它每个字母的编码长度不相等，那能够解码吗？

其实是可以的，我们可以自己试一下，就不在此叙述了。

那为什么哈夫曼编码可以压缩编码长度呢？

我们发现：出现次数最高的字母的编码最短，而出现次数最少的字母的编码最长，真是因为这个原因，哈夫曼编码才可以压缩编码长度。

总结

1、n 个权值构建出的哈夫曼树拥有 n 个叶子节点

2、每个哈夫曼编码都不是另一个哈夫曼编码的前缀，因为哈夫曼编码是根据路径计算出来的，每个权值节点都是叶子节点，且独一无二的，而路径的长短就是编码长短，根节点到一个叶子节点的路径肯定不是根节点到另一个叶子节点路径的前缀，因此每个哈夫曼编码都不是另一个哈夫曼编码的前缀。

3、哈夫曼树是带权路径长度最短的树，权值较大的节点离根节点越近。

带权路径长度：树中所有的叶子节点的权值乘上其到根节点的路径长度。

哈夫曼树的带权路径长度与哈夫曼树构建出的哈夫曼编码总长度成正比关系。