RLE算法详解

1. RLE是什么？

RLE是最简单的无损压缩算法之一，压缩原理很直接：

将连续重复的值（游程）用 [值+重复次数] 的形式表示，减少空间。

常用于位图、简单文本、信号等，尤其适合大量重复内容场景。

2. 基本原理

假设有如下原始数据（字符）：

AAAAABBCCCCDDDDDE

用RLE压缩（伪格式）变成：

5A2B4C5D1E

解释：

• 5A → A重复5次
• 2B → B重复2次
• 4C → C重复4次
• 5D → D重复5次
• 1E → E重复1次

注意: 实际RLE格式很多，比如 (次数,值)、(值,次数)、或特殊控制符等。

3. 具体编码流程

一步步处理输入数据：

示例代码（Python伪代码）

def RLE_encode(data):
encoded = []
count = 1
prev = data[0]
for cur in data[1:]:
if cur == prev:
count += 1
else:
encoded.append( (count, prev) )
count = 1
prev = cur
encoded.append( (count, prev) ) # 最后一个游程
return encoded

# 用例
s = 'AAAABBCCCCDDDE'
print(RLE_encode(s))
# [(4, 'A'), (2, 'B'), (4, 'C'), (3, 'D'), (1, 'E')]

解码只需遍历每组(count, value)，展开为 value*count 即可。

4. 常见RLE存储格式

不同应用可能定义不同格式，下面简单列举：

1. [次数][值]字节对

用二进制保存：

| 0x04 | ‘A’ | 0x02 | ‘B’ | 0x04 | ‘C’ | 0x03 | ‘D’ | 0x01 | ‘E’ |

• 每组2字节：一次次数，一个数据值

2. 控制位型

部分应用还可以用特殊标志位、填充零等方式处理非重复（比如PCX、BMP、TIFF格式都有细微不同）。

5. 优缺点

优点：

• 极其简单
• 编码/解码都很快
• 表现好于其他算法：在长重复数据（黑白图、空白、某些信号等）效果极好

缺点：

• 压缩率极度依赖数据特性
• 不适合随机/变化大的数据（比如自然图片，文本等），甚至变大

6. 典型应用

• 黑白位图（如FAX、PCX格式、BMP 8位图片行内压缩）
• 传感器数据流
• 简单日志
• DNA/RNA分析（重复单位）
• 通信协议中的简单帧等

7. 特殊变种

• 长度字节可以限定最大值（如255），超过需分段记录
• “重复0”或其它常量的特殊编码方式
• 可支持“非重复”块单独表示（如TIFF、PackBits）

举例：PackBits（TIFF/Photoshop里）

• [正号]N，表示接下来的N+1个都是不同数据（原样存储）
• [负号]-N，表示下一个字节重复N+1次

8. 扩展阅读

• Wikipedia: Run Length Encoding
• TIFF: PackBits说明

9、RLE编码的多种实现方式

实际工程中，RLE编码有许多细节变体。以下介绍几种：

9.1. 基本RLE（[次数][值]）

之前讲过，简单的形式就是：

[次数][值][次数][值][次数][值]…
4A2B4C3D1E

适合单字节数据类型。

9.2. 区分“重复段”和“非重复段”

很多应用必须同时处理连续重复内容和连续非重复内容（比如版式文件、图片行数据），常用如下方法：

• 重复式块：[控制字节][数值] 控制字节如高位取反，表示重复多少次；数值是要重复的那个字节。
• 原样块：[控制字节][原样数据序列…] 控制字节高位未取反，表示接下来有多少个原始未压缩字节。

PackBits（TIFF/Photoshop/Apple）格式示例：

• 控制字节 N = 0～127：表示N+1个原始数据，紧接着N+1字节。
• 控制字节 N = -1～-127：表示接下来的1个字节重复(-N)+1次。

举例（PackBits）压缩 AABBCCCCDD：

9.3. Bit/Flag RLE

某些协议用一个比特（或字节）做标志，指示接下来是重复段还是原样段，如

• 标志位为1代表复制，0代表原样
• 否则结合位字段、控制数组/表实现分块

9.4. 多字节数据类型

对于16位、32位等数据，每次游程的“值”可能是多字节，要注意低高字节顺序。

10、RLE解码流程（伪代码）

以TIFF/PackBits为例说明基本解码：

def packbits_decode(data):
i = 0
output = []
while i < len(data):
header = int.from_bytes(data[i], "signed")
i += 1
if header >= 0:
for _ in range(header + 1):
output.append(data[i])
i += 1
elif header != -128: # 特殊闲置符（跳过）
value = data[i]
i += 1
for _ in range(-header + 1):
output.append(value)
return output

11、RLE的实际应用：文件格式举例

11.1 BMP RLE

Windows Bitmap 8位图可配置为RLE8格式，每行采用RLE压缩；RLE编码用([count][value])，并用转义0结束一行或特殊指令。

11.2 TIFF PackBits

如前所述，TIFF采用PackBits方式，支持重复与非重复混合，有特殊控制符。

11.3 Fax 编码

Group 3/4 FAX采用RLE编码行数据，黑白像素长度编码，非常高效。

12、性能优化与注意事项

12.1 分块处理

大数据流序列要分块处理，避免爆RAM，可逐行或逐帧压缩。

12.2 压缩率提升技巧

• 对于非长连串数据，压缩率非常低，可与其它算法（如LZ4、Huffman）配合使用；
• 对“零填充/空白区”，单独优化（如专门零游程编码）。

12.3 溢出问题

比如计数字段一字节（最大255），连续重复超过需分成多个游程。

13、局限性分析

• 最适合长重复，最差于高熵内容
• 某些内容压缩后可能比原始数据大（如一系列完全没有重复的数据）
• 很难压缩图片、视频等复杂多变场景，除非“背景全白/黑”等

14、扩展：结合其它算法

RLE常作为预处理，后续再用其它算法（如DEFLATE、LZ4、Huffman），提升压缩效率——即“管道式”处理。

15. 总结

RLE适合简单场景，实现极为简洁。其思想是用计数消除冗余字节，但实际应用需考虑数据类型是否合适，否则可能适得其反。