RLE 压缩算法初探

RLE(run-length encoding)游程编码,是一种无损数据压缩算法;

对于数据来说数据格式不外乎有这么两种序列,如下图 1-1 :


图 1-1

所以就有以下两种的处理方式:


方法1:

核心思想: 不论是什么形式的数据全部使用"【字节数】+ 数据 "这种方式压缩;

以图 1- 1为例 :经过方法1处理的结果是: [3]A[1]B[1]A[1]C,对于这么一串数据的解读 3个A-1个B-1 个A -1 个C

这种的压缩方式存在一个巨大缺点: 当原始的数据都是连续的不重复数据(例如: abcdefg123456),在这种情况下存在这一个巨大的缺陷:在原始数据中,设:重复的字节数为x,不重复的字节数为y ,

当满足: x/y = 255/254这个公式时,实际上该压缩算法没有任何的作用,极限情况下可能使得经过该算法处理后的数据是源数据的两倍。


方法2:

核心思想:使用高2位作为数据是否标记的标志,当高2位均为1时为重复数据 [192 + 个数] + 原始数据, 当不为重复数据时所有的数据原样输出

以图 1-1 为例:经过方法2而处理的结果是:[3]ABAC, 对于这一串数据的解读是 3个A-BAC,

这种压缩方式有一个需要解决的问题是: 我们需要清楚的知道什么时候是连续的数据,什么时候是不连续的数据

 

图 1-2

在这种压缩的规则下:

(1)当高2位为[1][1]时,那么就是 "本字节 + 下字节" 实质上就是一个重复的数据的经过压缩得到。由于在一个字节中使用2位来标记是否重复,那么用于声明多少个字节重复的只有剩下的6位,即申明最大重复个数为64个。

(2)当高2位为[0][0]、[0][1]、[1][0]时, 那么就表示这是一个原始数据(如图 1-2)。

所以, 当读取出一个字节时,若该字节的值大于192,即为重复数据标记字节,下个字节为重复的数据;若该字节的值小于192,即为原始字节。基于此,这种的压缩方式存在这一个巨大的缺点,即原始数据的值是无法大于192 的。

例如 :

[原始数据] AAAAAA  BBB CCCC ABCD   

[压缩后数据][192 + 6 ]A [192 + 3]B [192 + 4]C ABCD

原始数据是17字节,压缩后为  10 个字节

现在还有一个问题: 实际上数据是否重复只是2种状态,但是为什么使用 2 位表示,事实是如果仅仅1位 [0]、[1]即可表示出两种状态,那么究竟是为什么要使用2 位来表示状态呢?

基于上述的方式,假设使用一个位数用于标记,即当最高位为 1 时表示为重复数据,当位 0 时表示不重复数据。那么毫无疑问可以声明的最大重复个数可以有 64-->128, 但是随之而来的问题是可以进行压缩的数据变窄了,有 192 -->128,毫无疑问这个是更加致命的。所以可以变形为下面的方式,即方法3。


方法3:

核心思想:以最高位作为标志位,当为1时表示重复数据"[128 + 重复个数(n)] + 当个数据(1)", 当为0时表示不重复数据"[不重复个数(n)] + 原始数据(n)"。

图 1-3

不论是否重复数据还是不重复数据都在块数据前面添加一个字节用于声明是否重复与该块数据的大小,如 图 1-3这么一来即解决了方式1中的,原始数据的限制(小于192或时小于128),而申明的长度也变为了128个。

例如:

[原始数据] AAAAAA  BBB CCCC ABCD   

[压缩后数据][128 + 6 ]A [128 + 3]B [128 + 4]C [4]ABCD

原始数据是17字节,压缩后为  11 个字节

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。