算法系列（八） RLE行程长度压缩算法

算法系列（八） RLE行程长度压缩算法2014-04-30 csdn博客吹泡泡的小猫RLE（Run Length Encoding）行程长度压缩算法（也称游程长度压缩算法），是最早出现、也是最简单的无损数据压缩算法。RLE算法的基本思路是把数据按照线性序列分成两种情况：一种是连续的重复数据块，另一种是连续的不重复数据块。对于第一种情况，对连续的重复数据块进行压缩，压缩方法就是用一个表示块数的属性加上一个数据块代表原来连续的若干块数据。对于第二种情况，RLE算法有两种处理方法，一种处理方法是用和第一种情况一样的方法处理连续的不重复数据块，仅仅是表示块数的属性总是1；另一种处理方法是不对数据进行任何处理，直接将原始数据作为压缩后的数据。

为了更直观的说明RLE算法，下面就用示例数据就对RLE算法进行演示。首先是第一种情况，原始数据有5个连续相同的数据块组成：

[block] [block] [block] [block] [block]

则压缩后的数据就是：

[5] [block]

接着是第二种情况，原始数据由连续的不重复数据块组成：

[block1] [block2] [block3] [block4] [block5]

按照第一种处理方法，最后的压缩数据就如以下情形：

[1][block1] [1][block2] [1][block3] [1][block4] [1] [block5]

如果按照第二种处理方法，最后的数据和原始数据一样：

[block1] [block2] [block3] [block4] [block5]

数据块block的长度可以是任意长度，数据块长度越长则连续重复的概率就越低，压缩的优势就体现不出来，因此，大多数RLE算法的实现都使用一个字节作为数据块长度。

接下来本文就介绍几种RLE算法的实现，首先是最简单的一种算法实现，这种算法实现对连续的不重复字节采用和重复字节一样的处理方法，就是在每个字节前增加一个值是1的连续块数属性（一个字节）。采用这种处理方法的首先好处是压缩和解压缩算法简单，可以用相同的模式处理两种情况的压缩数据，缺点就是当原始数据重复率比较低时，压缩后的数据长度会超过原始数据的长度，起不到压缩的作用，最糟糕的情况就是所有数据块没有连续重复的情况，压缩后的数据反而膨胀一倍。压缩的过程是这样的，线性扫描原始数据，如果某一个字节后面有重复的字节，则增加重复计数，然后继续向后扫描，直到找到一个不重复的字节，然后将块数和这个字节的数据依次写入压缩数据，然后从新的开始字节继续扫描直到原书数据结束。算法中需要注意的一点就是块数属性是用一个字节存储的，因此最大值就是255，当连续的相同数据超过255个字节时，就从第255个字节处断开，将第 256个字节以及256字节后面的数据当成新的数据处理。这种RLE压缩算法的C语言实现如下：

6 int Rle_Encode_N（unsigned char *inbuf, int inSize, unsigned char *outbuf, int onuBufSize） 7 { 8 unsigned char *src = inbuf; 9 int i;10 int encSize = 0;11 12 while（src < （inbuf + inSize））13 {14 if（（encSize + 2） > onuBufSize） /*输出缓冲区空间不够了*/ 15 {16 return -1;17 }18 unsigned char value = *src++;19 i = 1;20 while（（*src == value） && （i < 255））21 {22 src++;23 i++;24 }25 outbuf[encSize++] = i;26 outbuf[encSize++] = value;27 }28 29 return encSize;30 }