数据压缩之范式HUFFMAN

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. 启用memcached压缩注意事项    (阅读:3541)
  2. windows下压缩包在linux解压乱码的解决办法    (阅读:3489)
  3. php的echo为什么这么慢    (阅读:3414)
  4. 使用系统命令实现文件的压缩与加密    (阅读:3303)
  5. 前端性能优化之Html压缩    (阅读:3158)
  6. mod_gzip:Apache的HTTP压缩优化    (阅读:3130)
  7. MySQL从压缩文件恢复数据    (阅读:3095)
  8. 项目中对模板和js,css文件进行压缩的处理类    (阅读:3009)
  9. 为什么不压缩 HTML    (阅读:2926)
  10. 开源压缩算法Zopfli介绍    (阅读:2917)

QQ技术交流群:445447336,欢迎加入!

扫一扫订阅我的微信号:IT技术博客大学习

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章