简单的说RLE压缩就是将一串连续的相同数据转化为特定的格式达到压缩的目的。
下面都对byte流压缩。 如输入数据 LPBTE pByte={1,1,1,1,1,1}; 压缩的数据为6,1 压缩了4个字符。
但是在数据流里面不能直接这么替换,而应该使用特殊的控制字符,否则无法解压。
比如pByte={6,1,0,1,1,1,1,1,1};
这样有两个6,1无法判断是原有的6,1还是{1,1,1,1,1,1}压缩后的代码。
所以应该有控制字符。 (1) 为了达到最大压缩率,可以先扫描源数据流,使用最少出现的字符做控制字符。
如 pByte={6,1,0,1,1,1,1,1,1,...}; 扫描后发现0为最少出现的字符。
我们使用0作为压缩的控制,其他字符代表他本身。源数据里面的0,用0,0来表示。 那么pByte压缩后为 6,1,0,0,0,6,1 ......
解压时 BYTE a,b,c;
a=依次扫描压缩数据,如果输入字符为非控制字符,则直接输出到解压流。
如果为控制字符,b=其下一字符是否也为控制字符,如果是,在输出流输出控制字符的代码。
如果不是c=读压缩流,然后输出b个c到输出流。
注意:该处对于>Ctrlcode 的编码需要自己计算偏移.
如ctrl=2.那么n=3时应该修正为2.
刚才介绍的方法是最大压缩率的,但是因为对每个输入字符需要检查,速度不算快。
(2) 为了增加解压速度,可以采用其他的编码方式。 主要方法是不对每个输入字符进行检查,只检查较少次就达到几乎相同的压缩率。
来看看这个改进的方法。
仔细观察,其实对不重复的字符也可以用控制n+数据的方式表示。这里的n带表n个未压缩数据。
还是刚才的数据。 pByte={6,1,0,1,1,1,1,1,1} 不用扫描选择0为控制
压缩为3,{6,1,0,} 0, 6, 1 n ctrl n m
解压就非常方便了
扫描数据读一个字符, { n=read; if(n) { 字符拷贝n个 } else { n=read(); m=read; write (n个m); }
}
(3)优化
对(1)的优化。 观察得知,1,1,1这样的数据压缩率为0, 所以当n<=3时不用压缩。 而直接写为1,1,1样的格式。
另外如果有多个控制字符连续。也可以压缩。 观察ctrl=0; 0,0,0,0 如果用控制编码为8个0 而压缩编码为0,4,0 所以控制字符连续两个即可压缩。
对(2):
只对压缩编码优化。 例 1,2,3,4,1,1 如果死套公式,为 4,1,2,3,4,0,2,1 反倒增加2个字节。 如果用 6,1,2,3,4,1,1只增加一个字节。

|