HUFFMAN主要有两个问题，一是需要扫描两遍输入数据，二是树状结构编解码慢。对于第一个问题，基于统计信息的熵编码都很难解决这个问题，可以设计成自适应的，根据统计数据不停地改变调整码树，这会比较麻烦。对于第二个问题，这跟硬件有关系，二叉树的编码、解码都是O(1)的，复杂度上不能更优了，但是计算机硬件的特性，会使得树状结构遍历过程中CACHE MISS比较严重，如果码树比较小的话，可以都放在一级CACHE，性能会好很多，但是编码、解码一般都只是模块流程的一部分，所以码树经常会挤出CACHE，就算留在CACHE里，树状结构if else也会造成分枝预测错误，导致流水线中断。

    范式HUFFMAN是一种，压缩率与普通HUFFMAN相同，但是不用树状结构，而是用普通数组来存储，使得编解码比较快。HUFFMAN的特点是：（1）每个字符的编码不是另一个字符编码的前缀，确保解码无二义；（2）出现次数多的字符编码短。

    现在要构造一种方法使得，解码无二义，并且每个字符的编码长度与普通HUFFMAN算出来的长度相等。

    假设现在已经算出每个字符编码的长度，把这些字符按编码长度从短到长排列；长度相等的，按字典序排，长度相等情况下怎么排无所谓了，只要有序就行了。然后从最后一个字符开始编码，假设其长度为L0，则它的编码为L0个0。对于第I个字符，它的编码是第I+1字符编码加1，比如I+1是0001，则它为0010，并作截取，比如它的长度为4，则取0010，但是如果它的长度为3，则截取出001。对于I-1个字符，对001作加1操作，就是010了。

    下面通过构造法证明这个构造是正确的（这话比较别扭）

    对普通的HUFFMAN树，比较同一层的任两个节点，如果左边的是叶子结点，而右边的是中间节点，则交互这两棵子树（意思是说，把右边的节点及它的儿子、孙子、曾孙子……节点都移过去）。调整完毕后，明显从左往右看，叶子节点的长度递减。现在规定左分枝编码0，右路分枝编码1。明显可以看到是，这棵树还是一棵HUFFMAN树，难点是证明这棵树的编码正好跟上面构造出来的编码一致的。

    这真不容易说清楚，自己手工画一下就行了……

    下面讨论一下编码、解码

    编码比较简单，用HASH表查一下行了。

    解码，比较复杂。前面已经把字符排序了，把这些字符的编码的头几位提取出来，不足的以0补充，可以发现一个特点，提取出来的数是非递增的。所以解码的时候，需要把所长度的最小的一个编码提取出来作为数组A，每提取一个BIT的时候，就跟这些编码比较一下，逐步判定。不用每个BIT都判断整个数组A，因为数组A是非递增的，而多读取一个BIT之后，值也是非递增的，所以最多把数组A遍历一遍就能找到解码方法。

    据说这种HUFFMAN的解码效率与算术编码相当

    这个算法还有一个问题没解决，就是可能某些码的长度会很长，超过64位，这样在程序实现的时候会比较麻烦。不过这种树很少的。如果编码正好是0，10，110，1110，11110，……这种，码会比较长，但是出现这种情况是，每个字符出现的次数占了整棵子树的一半，连续出现64次这种情况，那得有2^64的数据，这是不可能的

建议继续学习：

1. windows下压缩包在linux解压乱码的解决办法    (阅读：4148)
2. 启用memcached压缩注意事项    (阅读：4063)
3. php的echo为什么这么慢    (阅读：4033)
4. 使用系统命令实现文件的压缩与加密    (阅读：4002)
5. MySQL从压缩文件恢复数据    (阅读：3677)
6. 前端性能优化之Html压缩    (阅读：3661)
7. mod_gzip：Apache的HTTP压缩优化    (阅读：3632)
8. 项目中对模板和js，css文件进行压缩的处理类    (阅读：3581)
9. 为什么不压缩 HTML    (阅读：3461)
10. 开源压缩算法Zopfli介绍    (阅读：3461)