首先，对于计算机而言，没有重复冗余的数据无法被压缩，比如：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快。
阅读(1507) | 评论(0) | 转发(0) |
