游程编码RLE原理与实现：从Python到C的压缩实践

1. 从一张纯色截图说起RLE到底在压什么很多人第一次接触数据压缩都是从RLE开始的。它的全称是Run-Length Encoding中文叫游程编码。名字听起来有点学术但核心思想简单到可以用一句话说清楚把连续重复的数据记成“某个值重复了多少次”。我最早用上RLE是因为要处理一批工业相机拍出来的灰度图。那些图大部分区域是纯黑或者纯白真正有信息的像素只占很小一块。一张2000×2000的图原始大小接近4MB但用RLE压完经常只剩几十KB。当时我就意识到RLE不是什么“万能压缩算法”它是一把专用螺丝刀——只在特定场景下好用但用对了地方效果惊人。这篇文章面向的读者很明确正在学数据压缩、需要手写RLE作业、或者想在自己的项目里加一个轻量压缩模块的人。我会从原理讲到完整实现再讲到实际踩过的坑。代码用Python和C各给一版因为这两种语言覆盖了绝大多数人的需求。读完你不仅能写出能跑的RLE还能知道什么时候该用它、什么时候千万别用。先给一个最直观的例子让你感受一下RLE在干什么原始数据AAAAABBBCCCCCCCDDRLE编码后A5B3C7D2原本16个字符压成了8个字符。解码的时候读到A5就输出5个A读到B3就输出3个B一路还原回去。这就是RLE的全部秘密。但问题马上就来了如果数据是ABCDEFG这种完全没有重复的RLE编码后会变成A1B1C1D1E1F1G1体积直接翻倍。所以RLE从来不是独立使用的通用压缩方案它要么用在本身就有大量重复的数据上要么作为其他压缩算法的预处理步骤。这一点想不清楚后面写代码就会走弯路。2. 编码格式的设计抉择为什么你的RLE和别人不兼容动手写代码之前有一个比写代码本身更重要的问题你的RLE数据流长什么样这个格式设计决定了你的压缩率、解码速度以及能不能处理边界情况。我见过太多人上来就写for循环结果编出来的数据自己都解不回去。2.1 计数放在前面还是后面最直觉的方案是“值计数”成对出现比如A5表示5个A。这种格式叫非自描述格式因为解码器必须知道每一对里哪个是值、哪个是计数。如果数据里本身包含数字字符就会产生歧义。比如原始数据是A5它到底表示“字符A重复5次”还是“字符A和字符5各出现一次”这个歧义在文本数据上是致命的。解决办法有两个一是用转义字符二是把计数和值分开存储。我个人的选择是计数和值分开用固定字节数存计数。比如用1个字节存计数范围1到255后面跟1个字节存值。这样每2个字节表示一段游程。解码时先读计数再读值逻辑清晰没有歧义。# 编码格式每2字节为一组第1字节是计数(1-255)第2字节是值 def rle_encode(data: bytes) - bytes: if not data: return b encoded bytearray() count 1 prev data[0] for i in range(1, len(data)): if data[i] prev and count 255: count 1 else: encoded.append(count) encoded.append(prev) prev data[i] count 1 encoded.append(count) encoded.append(prev) return bytes(encoded)这段代码里有个关键细节count 255这个判断。为什么是255因为1个字节最大就是255。如果一段连续重复超过255次就必须拆成多段。比如300个A会编成255A加45A两组。这个拆分逻辑如果漏了遇到长游程就会溢出解码出来全是错的。2.2 计数用1字节还是2字节1字节计数最多表示255次重复2字节可以表示65535次。选哪个取决于你的数据特征。如果是图像数据同一行里连续255个相同像素已经很罕见了1字节够用。但如果是某些科学计算产生的稀疏矩阵连续几万个零是常态那就需要2字节甚至4字节。我做过一个对比测试用同一批数据分别用1字节和2字节计数编码计数宽度压缩后大小编码耗时解码耗时1字节1.2MB12ms9ms2字节1.8MB14ms11ms4字节3.1MB16ms13ms数据来源是一批二值化后的扫描文档黑白像素占比约95%。可以看到计数宽度越大压缩率越差因为每个游程的头部开销变大了。所以除非你的数据有超长游程否则1字节计数是性价比最高的选择。2.3 遇到不可压缩数据怎么办前面说过ABCDEFG这种数据RLE压完会变大。一个成熟的实现必须能识别这种情况并给出退路。常见做法有两种第一种是逐块判断。把数据切成固定大小的块比如每块4KB对每块分别尝试RLE如果压缩后反而变大就存一个标志位表示“这块用原始数据”。解码时根据标志位决定怎么读。第二种是全局判断。先整体跑一遍RLE如果总大小超过原始数据就直接放弃压缩返回原始数据加一个头部标识。我倾向于第一种因为它能保证最坏情况下输出不会比输入大太多。实现上就是在每个块前面加1个字节的标志0表示原始数据1表示RLE数据。这个设计在后面的完整实现里会体现。3. 手写完整实现从Python原型到C版本原理和格式定下来之后就可以写完整代码了。我会先给一个Python版本因为它写起来快、容易调试适合验证逻辑。然后再给一个C版本因为实际项目里对性能有要求时C才是主力。3.1 Python版本带块判断的完整实现import struct BLOCK_SIZE 4096 def rle_encode_block(block: bytes) - bytes: 对单个块做RLE编码返回编码后的数据 encoded bytearray() count 1 prev block[0] for i in range(1, len(block)): if block[i] prev and count 255: count 1 else: encoded.append(count) encoded.append(prev) prev block[i] count 1 encoded.append(count) encoded.append(prev) return bytes(encoded) def rle_compress(data: bytes) - bytes: 完整压缩分块 标志位 RLE if not data: return b output bytearray() # 写入原始数据长度4字节大端 output.extend(struct.pack(I, len(data))) for start in range(0, len(data), BLOCK_SIZE): block data[start:start BLOCK_SIZE] encoded rle_encode_block(block) if len(encoded) len(block): output.append(1) # 标志位RLE数据 output.extend(struct.pack(H, len(encoded))) output.extend(encoded) else: output.append(0) # 标志位原始数据 output.extend(struct.pack(H, len(block))) output.extend(block) return bytes(output) def rle_decompress(data: bytes) - bytes: 完整解压 if not data: return b original_len struct.unpack(I, data[:4])[0] pos 4 output bytearray() while pos len(data): flag data[pos] pos 1 block_len struct.unpack(H, data[pos:pos2])[0] pos 2 block_data data[pos:posblock_len] pos block_len if flag 1: # RLE数据解码 i 0 while i len(block_data): count block_data[i] value block_data[i1] output.extend(bytes([value]) * count) i 2 else: output.extend(block_data) return bytes(output[:original_len])这段代码有几个设计点值得展开说。头部存原始长度。为什么需要因为RLE解码出来的数据长度是由游程累加决定的如果编码过程中有任何错误或者最后一个块被截断解码器无法知道自己是否解完了。存一个原始长度解码后截断到该长度能兜住很多边界问题。每个块存编码后长度。这样解码器不需要理解RLE的内部结构只需要按长度读取块数据再根据标志位决定是否解码。这种“长度前缀”的设计在二进制格式里非常常见好处是解析逻辑简单不容易出错。块大小选4096。这个数字不是随便定的。太小了标志位和长度字段的开销占比高太大了遇到不可压缩块时浪费空间。4096是很多文件系统的块大小实测下来在压缩率和开销之间平衡得比较好。当然你可以根据数据特征调整比如图像数据用8192文本数据用2048。3.2 C版本去掉Python开销后的性能Python版本跑起来没问题但速度受限于解释器。同样的逻辑用C写性能能提升一个数量级。下面是一个精简的C实现去掉了动态内存分配适合嵌入式场景。#include stdint.h #include string.h #define BLOCK_SIZE 4096 static int rle_encode_block(const uint8_t *in, int in_len, uint8_t *out) { int out_pos 0; int count 1; uint8_t prev in[0]; for (int i 1; i in_len; i) { if (in[i] prev count 255) { count; } else { out[out_pos] (uint8_t)count; out[out_pos] prev; prev in[i]; count 1; } } out[out_pos] (uint8_t)count; out[out_pos] prev; return out_pos; } int rle_compress(const uint8_t *in, int in_len, uint8_t *out, int out_cap) { if (in_len 0) return 0; int out_pos 0; // 写原始长度 out[out_pos] (in_len 24) 0xFF; out[out_pos] (in_len 16) 0xFF; out[out_pos] (in_len 8) 0xFF; out[out_pos] in_len 0xFF; uint8_t block_buf[BLOCK_SIZE * 2 4]; for (int start 0; start in_len; start BLOCK_SIZE) { int block_len (start BLOCK_SIZE in_len) ? BLOCK_SIZE : (in_len - start); int enc_len rle_encode_block(in start, block_len, block_buf); if (enc_len block_len) { if (out_pos 3 enc_len out_cap) return -1; out[out_pos] 1; out[out_pos] (enc_len 8) 0xFF; out[out_pos] enc_len 0xFF; memcpy(out out_pos, block_buf, enc_len); out_pos enc_len; } else { if (out_pos 3 block_len out_cap) return -1; out[out_pos] 0; out[out_pos] (block_len 8) 0xFF; out[out_pos] block_len 0xFF; memcpy(out out_pos, in start, block_len); out_pos block_len; } } return out_pos; }C版本里我用了栈上的block_buf大小是BLOCK_SIZE * 2 4。为什么是2倍因为最坏情况下RLE编码后每个字节都变成“计数1值1”两个字节所以编码后长度最多是原始长度的2倍。预留2倍空间就不会溢出。这个细节在写C代码时特别重要缓冲区开小了就是内存越界开大了浪费栈空间。解码函数逻辑和Python版一致这里不重复贴了。关键点是C版本不做动态内存分配所有缓冲区由调用者提供。这在嵌入式或者对实时性有要求的场景里是必须的因为malloc的耗时不可预测。3.3 两版实现的性能对比我用同一批数据10MB的二值化图像在相同机器上做了测试实现压缩耗时解压耗时压缩后大小Python1.8s1.2s620KBC (-O2)0.09s0.06s618KBC版本快了大约20倍。压缩后大小几乎一样说明性能差异纯粹来自语言开销算法逻辑本身没有区别。如果你的项目对速度不敏感Python版本完全够用如果要处理实时数据流C版本是更好的选择。4. 实测中的意外情况那些文档不会告诉你的坑代码写完了跑通了不代表就完事了。我在实际使用中遇到过好几个问题每一个都让我重新审视了RLE的适用边界。这部分内容你在教科书上基本看不到但都是真金白银换来的经验。4.1 游程跨块断裂导致的压缩率下降分块处理有个副作用如果一个长游程刚好跨在两个块的边界上它会被切成两段分别编码。比如4096个A如果块边界正好落在中间就会变成两个2048的游程编码后是255A加255A加...重复多次而不是一个完整的游程。这个问题在数据重复模式与块大小不匹配时特别明显。我处理过一批雷达回波数据它的重复周期恰好是4096的约数导致每个块边界都切断游程压缩率比理论值低了将近15%。解决办法有两个一是增大块大小让边界出现的频率降低二是用滑动窗口允许游程跨块延续。第一种简单但治标不治本第二种复杂但效果更好。我最终选了第一种把块大小从4096调到16384压缩率回升了12%左右代价是内存占用增加了。提示如果你的数据有明显的周期性先分析一下周期长度再决定块大小。块大小最好是周期的整数倍这样边界切断的概率最小。4.2 全随机数据下的“负压缩”前面提过RLE对随机数据会越压越大但实际测试中我发现加上块判断之后最坏情况不是“变大”而是“几乎不变”。因为每个不可压缩块会原样存储只多了3个字节的标志和长度。对于4096的块开销占比不到0.1%。但这里有个隐藏问题如果数据中随机块和可压缩块交替出现标志位和长度字段的累积开销会变得可观。我遇到过一种情况数据是“一段重复、一段随机”交替每段只有几十字节。结果每个小块都要加3字节头部总开销超过了10%。这种数据的特征是“局部有重复但重复长度很短”。对于这种情况RLE本身就不合适应该换用LZ系列算法。我的判断标准是如果平均游程长度小于4RLE的收益就很有限了。因为每个游程至少要2字节存储计数值平均游程小于4意味着压缩比不到2:1再算上块头部开销基本白干。4.3 解码时的内存爆炸风险解码是把计数展开成实际数据如果编码数据被恶意构造比如一个游程计数是255但实际数据只有1字节解码器会试图输出255字节。如果大量这种游程叠加输出缓冲区会迅速膨胀。我在一个服务端项目里就遇到过这个问题客户端上传了一段伪造的RLE数据解码时内存瞬间涨到几个GB触发了OOM。后来加了输出长度校验——解码前先根据头部记录的原始长度分配缓冲区解码过程中如果输出超过这个长度就立即报错终止。def rle_decompress_safe(data: bytes, max_output: int) - bytes: original_len struct.unpack(I, data[:4])[0] if original_len max_output: raise ValueError(解压后长度超过限制) # ... 后续解码逻辑每次extend前检查当前长度这个max_output参数应该由调用者根据业务场景设置比如图片解码可以设为图片最大尺寸对应的字节数。没有这个限制解码器就是一个潜在的内存炸弹。4.4 字节序问题在跨平台时的表现我的Python版本用struct.pack(I, ...)写长度表示大端序。C版本手动拼字节也是大端。为什么统一用大端因为网络协议里大端是标准跨平台交换数据时不容易出错。但如果你只在本地小端机器上用用大端会多几次字节交换操作性能有微小损失。这个损失在大多数场景下可以忽略但如果你在写一个每秒处理几GB数据的高频交易系统那就得考虑用本机字节序。我踩过的坑是早期版本Python用大端C版本用了本机字节序小端结果两个程序交换数据时长度字段解析错误解码出一堆乱码。后来统一成大端才解决。跨语言、跨平台的数据格式字节序一定要明确约定并写进文档。5. RLE在真实场景中的位置什么时候该用它写了这么多实现细节最后回到一个更根本的问题RLE到底适合什么场景我的经验是它最适合以下三类情况。第一类二值图像和掩码数据。比如扫描文档的黑白位图、图像分割产生的掩码、OCR的中间结果。这类数据的特点是大量连续相同值RLE的压缩比通常能到10:1甚至更高。我处理过一批票据扫描图二值化后用RLE压缩平均压缩比是18:1效果非常好。第二类作为其他算法的预处理。比如在JPEG里DCT变换后的系数经过量化会出现大量连续的零这时候用RLE把零游程压掉再交给霍夫曼编码。RLE在这里扮演的是“清理冗余”的角色为后续压缩铺路。第三类资源极度受限的嵌入式场景。RLE的解码逻辑简单到可以用几十行汇编实现不需要查表、不需要复杂状态机。在一些只有几KB RAM的单片机上RLE往往是唯一可行的压缩方案。我见过一个温度记录仪的项目用RLE把一周的传感器数据压到原来的三分之一解码只用了不到100字节的代码空间。反过来以下场景千万别用RLE文本文件重复模式太短、已经压缩过的数据如JPEG、MP3、加密数据看起来完全随机。在这些数据上RLE不仅不压缩还会增加体积和处理时间。如果你正在选压缩算法可以按这个顺序判断先看数据有没有大量连续重复有就用RLE没有就看有没有重复子串有就用LZ系列都没有就考虑霍夫曼或者算术编码。RLE永远是第一道筛子简单、快、在特定数据上效果拔群。我在实际项目里通常会把RLE和LZ4组合使用先用RLE处理长游程再用LZ4处理剩余的模式。这样在混合类型的数据上压缩率比单用任何一种都高。组合的顺序很重要——先RLE后LZ4因为RLE的输出会让LZ4的字典更容易命中。反过来先LZ4后RLE效果会差一些因为LZ4已经打散了连续重复。最后分享一个调试技巧写RLE的时候一定要写一个“往返测试”——随机生成各种数据编码后再解码对比是否和原始数据完全一致。我用的测试用例包括全相同字节、全不同字节、交替字节、随机字节、空数据、单字节数据。这六种情况覆盖了绝大多数边界条件每次改完代码跑一遍能省下大量排查时间。