Chinaunix首页 | 论坛 | 博客
  • 博客访问: 832537
  • 博文数量: 330
  • 博客积分: 9641
  • 博客等级: 中将
  • 技术积分: 3181
  • 用 户 组: 普通用户
  • 注册时间: 2007-01-19 14:41
文章分类

全部博文(330)

文章存档

2012年(17)

2011年(135)

2010年(85)

2009年(57)

2008年(36)

我的朋友

分类:

2011-04-06 23:23:09

  首先,对于计算机而言,没有重复冗余的数据无法被压缩,比如:a-z 26个字母组成的一段文字。人工识别为26 alphabet,能节省不少空间,但这个是加入了人工分析的一个字母表的索引,不是压缩,机器解压时也无法识别。

  机器自动分析重复出现的一段文字是可行的方法。可以借鉴lz77和lzw。
  lz77是适用范围广泛。需要一个装入压缩文字匹配区的滑动窗口,紧接着滑动窗口的是一个前向缓冲,存放还没有被处理的文字。压缩时采用(distance, length) 二元组来表示要匹配的最大长度文字的首文字(前向缓冲区头部)与匹配的滑动窗口中的首文字之间的距离,和匹配的文字的长度。如果没有匹配到,就单纯的输出此文字。如何区分是否有匹配到,可以在编码的最开头加一个标签,如果是0,表示有匹配中,之后跟的是二元组,如果是1,表示没有匹配中,之后跟的是一个8bit的文字。
distance的位数可以用 upper_bound( log2(滑动窗口SIZE) )来计算。length由于较长的匹配出现的概率较小,可以采用一种变长的前缀编码,如:huffman,Golomb,γ编码等节省空间的方式实现。
解码时,匹配开头标签,如果1,则输出8bit文字,如果是0,则朝滑动窗口方向寻找距离当前位置distance的文字,输出length的长度。

  如果有较多的大量重复数据,比如gif中的动态变换图片那样,可以使用lzw,lzw的压缩速度比lz77快。
阅读(432) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~