前两天发布那个rsync算法后，想看看数据压缩的算法，知道一个经典的压缩算法Huffman算法。你应该听说过 David Huffman 和他的经典的压缩算法—— Huffman Code，这是一种通过字符出现频率，Priority Queue，和二叉树来进行的一种压缩算法，这种二叉树又叫Huffman二叉树 —— 一种带权重的树。但是网上查了一下，中文社区内好像没有把这个算法说得很清楚的文章，尤其是树的构造，而正好看到一篇国外的文章《A Simple Example of Huffman Code on a String》，其中的例子浅显易懂，相当不错，我就转了过来。注意，我没有对此文完全翻译。

    HUFFMAN主要有两个问题，一是需要扫描两遍输入数据，二是树状结构编解码慢。对于第一个问题，基于统计信息的熵编码都很难解决这个问题，可以设计成自适应的，根据统计数据不停地改变调整码树，这会比较麻烦。对于第二个问题，这跟硬件有关系，二叉树的编码、解码都是O(1)的，复杂度上不能更优了，但是计算机硬件的特性，会使得树状结构遍历过程中CACHE MISS比较严重，如果码树比较小的话，可以都放在一级CACHE，性能会好很多，...