Huffman编码是一种数据压缩算法，可缩短编码后的二进制长度，以达到节约存储与带宽的目的。
原理
哈夫曼编码首先需要统计每个字符出现的次数(频率)，然后将字符和频率构建出哈夫曼树，进而得到每个字符对应的编码。
需要知道的是哈夫曼编码不是等长编码，那么如果要使得编码后的二进制长度最短，那么出现频率高字符应该是编码最短的。
哈夫曼树
哈夫曼树是一个二叉树。构造哈夫曼树时每个字符对应到二叉树的叶子节点，频率最低字符的路径最长，频率最高字符的路径最短。下面用具体示例演示下怎么构造一个哈夫曼树。
假如现在有字符串 ABAACDC 要进行哈夫曼编码，需要先构造出哈夫曼树，那么先统计每个字符出现的频率：
| 字符 | 出现次数(频率) |
|---|---|
| A | 3 |
| B | 1 |
| C | 2 |
| D | 1 |
取出频率最小两个，分别是B和D，进行合并, 相加的和作为父节点:
graph BT
B["1 (B)"] --- 2
D["1 (D)"] --- 2
再取出剩余字符中频率最小的 C 继续合并:
graph BT
B["1 (B)"] --- 2
D["1 (D)"] --- 2
C["2 (C)"] --- 4
2 --- 4
最后取出字符 A 合并:
graph BT
4 --- 7
B["1 (B)"] --- 2
D["1 (D)"] --- 2
C["2 (C)"] --- 4
2 --- 4
A["3 (A)"] --- 7
这样构造出的就是哈夫曼树。
哈夫曼编码
构造出哈夫曼树之后，二叉树左面的边都标记为0, 右面的边都标记为1。
graph BT
4 --- |0| 7
B["1 (B)"] --- |0| 2
D["1 (D)"] --- |1| 2
C["2 (C)"] --- |0| 4
2 --- |1| 4
A["3 (A)"] --- |1| 7
然后就可以对每个字符进行编码了。编码方式为从根节点到叶子节点经过边上的标记顺序：
1
2
3
4
A 1
C 00
B 010
D 011
哈夫曼编码不是一种固定的编码算法，上面构造哈夫曼树的时候可以将节点放入左边或右边，那么可能会得到不同的编码。
对照上面表格中字符出现的频率，可以看出字符 A 出现的频率最高，对应的编码长度是最短的，而频率最低的 B 和 D 对应的编码长度则是最长的。
现在每个字符都有了编码，我们再对上面的字符串 ABAACDC 依次进行编码，得到的便是霍夫曼编码：
1
1 010 1 1 00 011 00
对比
如果将上面的 ABCD 4个字符进行定长编码，假如按以下编码：
1
2
3
4
A 00
B 01
C 10
D 11
则上面的字符串 “ABAACDC”, 编码后结果为 00 01 00 00 10 11 10 共14位，而上面的霍夫曼编码后得到的是13位，此时共节约了1位。如果字符更多、字符串更长的话，可以节约出更多的空间。