黑马程序员技术交流社区

标题: RLE压缩算法 [打印本页]

作者: 光年之外 时间: 2018-11-29 17:43
标题: RLE压缩算法
RLE压缩算法（下简称RLE算法）的基本思路是把数据按照线性序列分成两种情况：一种是连续的重复数据块，另一种是连续的不重复数据块。

RLE算法的原理就是用一个表示块数的属性加上一个数据块代表原来连续的若干块数据，从而达到节省存储空间的目的。一般RLE算法都选择数据块的长度为 1 字节，表示块数的诚性也用1字节表示，对于颜色数小于 256 色的图像文件或文本文件，块长度选择 1 字节是比较合适的。
连续重复数据的处理
RLE 算法有很多优化和改进的变种算法，这些算法对连续重复数据的处理方式基本上都是一样的。对于连续重复出现的数据，RLE算法一般用两字节表示原来连续的多字节重复数据。我们用一个例子更直观地说明 RLE 算法对这种情况的处理，假如原始数据有 5 字节的连续数据：
[data] [data] [data] [data] [data]
则压缩后的数据就包含块数和 [data] 两字节，其中 [data] 只存储了一次，节省了存储空间：
[5] [data]
需要注意的是，一般 RLE 算法都采用插入一个长度属性字节存储连续数据的重复次数，因此能够表达的扱大值就是 255 字节，如果连续的相同数据超过 255 字节时，就从第 255 字节处断开，将第 256 字节以及 256 字节后面的数裾当成新的数椐处理。

随着 RLE 算法采用的优化方式不同，这个长度属性字节所表达的意义也不同，对于本节给出的这种优化算法，长度属性字节的最高位被用来做一个标志位，只有 7 位用来表示长度。
连续非重复数据的处理
对于连续的非重复数据，RLE 算法有两种处理方法：
一种处理方法是将每个不重复的数据当作只重复一次的连续重复数据处理，在算法实现上就和处理连续重复数据一样；
另一种处理方法是不对数据进行任何处理，直接将原始数据作为压缩后的数据存储。

假如有以下 5 字节的连续非重复数据：
[datal] [data2] [data3] [data4] [data5]
按照第一种处理方法，最后的压缩数据就如下所示：
[1][datal] [1][data2] [1][data3] [1][data4] [1][data5]
如果按照第二种处理方法，最后的数据和原始数据一样：
[data1] [data2] [data3] [data4] [data5]
如果采用第一种方式处理连续非重复数据，则存在一个致命的问题，对连续出现的不重复数据，会因为插入太多块数属性字节而膨胀一倍，如果原始数据主要是随机的非重复数据，则采用这种方式不仅不能起到压缩数据的目的，反而起到恶化的作用。多数经过优化的 RLE 算法都会选择使用第二种方式处理连续非重复数据，但是这就引入了新问题，在 RLE 算法解码的时候，如何区分连续重复和非重复数据？

前面己经提到，如果把非重复数据当作独立的单次重复数据处理，反而会造成数据膨胀，但是如果把连续非重复数据也当成一组数据整理考虑呢？这是一个优化的思路，首先，给连续重复数据和连续非重复数据都附加一个表示长度的属性字节，并利用这个长度属性字节的最高位来区分两种情况。

长度属性字节的最高位如果是 1，则表示后面紧跟的是个重复数据，需要重复的次数由长度属性字节的低 7 位（最大值是 127）表示。长度属性字节的最高位如果是 0，则表示后面紧跟的是非重复数据，长度也由长度属性字节的低 7 位表示。

采用这种优化方式，压缩后的数据非常有规律，两种类型的数据都从长度属性字节开始，除了标志位的不同，后跟的数据也不同。第一种情况后跟一个字节的重复数据，第二种情况后跟的是若干个字节的连续非重复数据。

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2