行程编码 (RLE)

RLE

1. 什么是 RLE
说来很简单。把相同的东西做成 N*String。
比如,AAABBBBCCCCC,编码出来就是 A3B4C5 或者 3A4B5C。基本思路就是如此。
2. 有啥优点呢?
2.1. 简单粗暴,容易理解,编码解码速度快。
2.2. 对于那种重复的很多的数据,编码起来很有效。
2.3. 好写。
2.4. 不丢失数据啊。
3. 有啥缺点呢?
对于下面这组数据:
A-B-C-D-A-B-C-D
编码结果是
1-A-1-B-1-C-1-D-1-A-1-B-1-C-1-D
反而比以前长了……编码后体积膨胀了。
我的理解是,行程编码没有字典……但是课上老师一直在把我们向 “字典” 方向引导,不知道是什么意思。
4. 改进?
4.1. 可以一次多位嘛……
A-B-C-D-A-B-C-D
2-A-B-C-D
4.2. 我们可以规定一下:
我们分别统计 “这个数字描述的是要重复出现的东西还是不重复的东西”。
如果描述的是 “要重复的东西”,那么这个数字表示后面字节的重复次数,这个数字的特征标志是 “第一位为 1”。
如果描述的是 “不重复的东西”,那么这个数字表示后面不重复字节的长度,这个数字的特征标志是 “第一位为 0”。
举个栗子:
A-A-A-A-B-B-C-C-C-C-C-C-A-B-C-A-B-C
编码后:
132-A-2-B-6-134-C-6-A-B-C-A-B-C
其中 132=128+4,134=128+6
4.3. 上面再加上优化:
8 位,占用一位作为标志位,剩下 7 位了,最大范围是 127。太少了……
那么就再规定一下:如果前面一直是 “极限”,就继续往下面读,累加,直到一个 “不是极限” 的数字为止。这样就能安全地越过 127 这个坎儿了。
举例:
255-255-128-A
(255-128)+(255-128)+(128-128)=254
也就是 254 个 A。
4.3. 评价:
能部分解决数据膨胀的问题……只是部分解决……
5. 代码实现
5.0. 说明
课上要求不限语言。于是我就用了 Python。完全当作练习 Python 的文件读写了。一边查语法一边写的……
课上的要求是 “用 RLE 将 20 个 sql 文件合并成一个文件”。涉及到多文件,不得不规定一下文件格式了。否则合并出来如何解出来啊?
对于合并后的文件规定如下:

对于每一个文件的数据,如上所述
5.1.1 编码部分之文件读写部分

5.1.2. 编码部分之最朴素的编码方案

5.1.3. 编码部分之第二次改进后的编码方案

5.2.0. 解码方案之文件读写部分

5.2.1. 解码部分之最朴素的方案

5.2.2. 解码方案之第二次改进后的方案

5.3. 备注
在改进的编码方案中,我定义了一个规则:如果重复次数为 2,则认为它是不重复的。理由是,A-A 编码成了 2-A,长度并没有减少,所以这样做编码无意义。
只能对整个文件夹里面的所有文件进行编码。不得有子文件夹。总长度不得大于 2147483647 字节。
6. 测试
6.1. 使用朴素 RLE 编码:
6.1.1. 编码给定的 20 个 sql 文件。编码前大小 123kb。编码后大小 120kb。
6.2. 使用第二次改进的编码方案编码:
6.2.1. 编码给定的 20 个 sql 文件。编码前大小 123kb。编码后大小 120kb。
6.2.2. 编码一张白色底的 580*271 的 bmp 图片。编码前大小 460kb。编码后大小 34kb。
7. 参考资料
维基百科
RLE 行程长度编码压缩算法

发表评论

电子邮件地址不会被公开。 必填项已用*标注