数据压缩之范式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的数据,这是不可能的
建议继续学习:
- windows下压缩包在linux解压乱码的解决办法 (阅读:4169)
- 启用memcached压缩注意事项 (阅读:4080)
- php的echo为什么这么慢 (阅读:4054)
- 使用系统命令实现文件的压缩与加密 (阅读:4027)
- MySQL从压缩文件恢复数据 (阅读:3696)
- mod_gzip:Apache的HTTP压缩优化 (阅读:3663)
- 前端性能优化之Html压缩 (阅读:3678)
- 项目中对模板和js,css文件进行压缩的处理类 (阅读:3611)
- 开源压缩算法Zopfli介绍 (阅读:3483)
- 为什么不压缩 HTML (阅读:3474)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:杨镇锋 来源: 我思故我在
- 标签: HUFFMAN 压缩
- 发布时间:2011-01-20 22:27:40
- [55] IOS安全–浅谈关于IOS加固的几种方法
- [53] android 开发入门
- [52] 如何拿下简短的域名
- [52] 图书馆的世界纪录
- [50] Oracle MTS模式下 进程地址与会话信
- [50] Go Reflect 性能
- [48] 【社会化设计】自我(self)部分――欢迎区
- [47] 读书笔记-壹百度:百度十年千倍的29条法则
- [36] 程序员技术练级攻略
- [27] 视觉调整-设计师 vs. 逻辑