最近研究 http2.0，在看到请求头压缩这一块内容时，说到应用了静态哈夫曼编码对标头进行了压缩。哈夫曼编码大一时就已经学过，时隔多年，除了记忆中还存留着老师那几页模糊的 PPT 的印象，具体的内容早已忘得一干二净。
在继续 http2.0 的学习之前，先重温下 huffman 编码吧。
简介
哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman 于 1952 年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做 Huffman 编码（有时也称为霍夫曼编码)。- 百度词条
编码原理
总的来说，huffman 编码分为以下几步。
- 统计每个字符出现的次数（或者概率），每一个字符当做一个节点，节点值为其概率，放到一个列表中。
- 按照节点概率的大小从大到小进行排列。
- 将最小概率的 2 个节点挂载到一个新的节点上，新节点的概率值为 2 个子节点相加，较大的节点放新节点的左侧，权值为 “0”，较小的放右侧，权值为 “1”。，从列表中移除 2 个节点并添加新的节点。如果新节点的概率大于或等于列表前面的节点概率，则新节点往前冒泡。
- 如果列表长度大于 1，回到第 3 步骤继续。
- 最后结果会生成一个二叉树。从根节点到每个字符所对应节点的路径上遇到的权值拼接后就是这个字符的 huffman 编码。
上面的文字描述可能有点绕，还是通过例子来的走一遍。
比如有一个字符串 aabbcccdddddeee。
统计可知出现的概率如下
- a - 2/15
- b - 2/15
- c - 3/15
- d - 5/15
- e - 3/15
首先将其从大到小排列
按照上面的第 2 步，将 a，b 挂到新的父节点，新节点大于 c,e，所以移到前面，并在二叉树枝干上打上权值 1 和 0。
重复第 2 步，将 c，e 挂到新的父节点。c 和 e 的新父节点大于之前的 ab，所以继续移到 ab 之前。
重复第 2 步，将 ce，ab 挂到新的父节点，同理移到 d 的前面。
重复第 2 步，将 ceab 和 d 挂到新的父节点。现在列表中只剩一个节点了。我们得到了一个包含所有节点的二叉树。
转换
从上面的二叉树中，我们从根节点遍历，可以得到每个字符所在节点的路径。
- a 010
- b 011
- c 10
- d 00
- e 11
我们知道一个字符至少占用 1 个字节也就是 8bit，而上面经过 huffman 编码后的二进制长度少于 8bit1。如果我们把所有字符用新的二进制表示，则可以减少字符串的长度2。
我们遍历原字符串，通过得到的二进制来存储，得到 0100100110111010100000000000111111
解码
huffman 解码的过程很简单。
遍历得到的二进制，从树的根节点开始遍历，匹配到某个字符的路径后，回到树的根节点继续遍历，直到结束。
那么这里会有个问题 “遍历二进制时不会走到错误的节点吗？”
答案是不会的，因为在生成的二叉树中，所有字符所在叶子节点都是尽头节点，也就是说每一个字符所在节点的路径都是唯一的，不会出现路径互相覆盖的情况。
代码实现
打不开请翻墙
备注
- huffman 编码值可能大于 8bit，这和字符的概率有相关。
- 这里没有考虑存储树信息的长度。