Huffman 编码压缩算法
前两天发布那个rsync算法后，想看看数据压缩的算法，知道一个经典的压缩算法Huffman算法。相信大家应该听说过 David Huffman 和他的压缩算法—— Huffman Code，一种通过字符出现频率，Priority Queue，和二叉树来进行的一种压缩算法，这种二叉树又叫Huffman二叉树 —— 一种带权重的树。从学校毕业很长时间的我忘了这个算法，但是网上查了一下，中文社区内好像没有把这个算法说得很清楚的文章，尤其是树的构造，而正好看到一篇国外的文章《A Simple Example of Huffman Code on a String》，其中的例子浅显易懂，相当不错，我就转了过来。注意，我没有对此文完全翻译。
我们直接来看示例，如果我们需要来压缩下面的字符串：
“beep boop beer!”
首先，我们先计算出每个字符出现的次数，我们得到下面这样一张表 :
字符
次数
‘b’
3
‘e’
4
...
