哈夫曼编码

介绍

哈夫曼树（HuffManTree）是用来压缩数据的一种数据结构，它适合压缩数据重复率较高的情况。

文本A：123456789，这串文本重复率为0，因为每个字符都是唯一的，没有重复率而言；
文本B：111222334，这串文本重复率明显较A高，适合用哈夫曼树压缩。

问题与分析

现在想把“aaaabbbccdeefffgggg”这个字符串保存到硬盘上，如果直接保存，它会占用多大空间？

回顾一下，每个英文字母都可以用一个ASCII码表示，例如 a=97，b=98，……
而每个ASCII码是 1 byte，所以上面的字符串一共占用 19 byte = 152 bit。

我们站在计算机的角度再来分析一下，对于计算机而言，万物皆为0/1，人类理解的abc，在计算机里就是一串0/1
“aaaabbbccdeefffgggg”在计算机里存储的内容就是

a a a a b b ……

01100001 01100001 01100001 01100001 01100010 01100010 ……

可以发现，对于重复的字符，计算机存储了大量重复的二进制码

所以我们可不可以换种方式，不再直接用ASCII编码的方式，而是根据各字符出现的频率编码，让出现频率高的字符编码短一点，出现频率低的字符编码长一点，这样就可以避免所有字符都是8 bit，从而减少存储空间的消耗。

原理

哈夫曼树正是以上述方式实现的一种解决方式，具体过程如下

1. 统计各字符出现的频率

   a = 4
   b = 3
   c = 2
   d = 1
   e = 2
   f = 3
   g = 4

2. ① 按照频率降序排列；
   ② 取出最后面的两个(不放回)，创建一个新节点，将二者保存，再将新节点放回原序列；
   重复①②，直到只剩一个节点。（每次拿走两个，新增一个，最终一定会只剩一个）

   注意，已经取走的节点不再参与排序，即只排序最顶端的节点

   
   
   
   
   
   
   

3. 从任意节点出发，向左走为0，向右走为1，遍历整棵树，得出各字符对应的0/1序列
   

4. 按照各个字符对应的新二进制编码，保存文件

   a a a a b b ……
   11 11 11 11 001 001 ……

   相比较直接保存，节省了许多空间，当数据量很大时，压缩效果越加明显。