游程编码(RLE)是一种无损数据压缩方法,将连续出现的相同值表示为一个游程,通常用该值及其重复次数来描述。对于包含长段相同符号的数据,例如简单的光栅图像、二值掩码以及数据库列中连续重复的值,这种方法十分有效。RLE 是一类编码方案,而非某一种标准化的文件格式:不同方案采用不同的计数表示方式、字面量块以及游程识别规则。
基本原理
游程是由相同符号连续组成、且无法再向两端延伸的序列。例如,序列
AAAAABBBCCAAAA
包含四个游程,可以表示为:
(A, 5), (B, 3), (C, 2), (A, 4)
解码时,将每个二元组展开为指定数量的对应值,即可精确还原原始序列。
更形式化地说,长度为 的序列可以划分为 个游程:
其中, 是第 个游程的值, 是该游程的长度,为正数,且相邻游程的值不同。各游程的长度满足
编码的符号不一定是字符,也可以是单个比特、字节、像素、整数或更大的记录。如何判定重复,取决于所选的单位:当每个像素占用多个字节时,重复的像素不一定会形成连续重复的字节。
(A, 5) 这种记法仅用于说明,并非通用的存储格式。实际的编码必须规定字段大小、计数上限,以及解码器如何区分计数、数值和控制信息。
编码与解码
基本的编码算法从左到右扫描输入,保存当前值及其计数。当遇到不同的值时,输出已完成的游程,并开始一个新游程。到达输入末尾后,输出最后一个游程。
以抽象二元组表示输出时,可以用以下伪代码描述这一过程:
如果输入为空:
返回
当前值 = 输入的第一个符号
计数 = 1
对于剩余的每个符号:
如果符号 == 当前值:
计数 = 计数 + 1
否则:
输出(当前值, 计数)
当前值 = 符号
计数 = 1
输出(当前值, 计数)
实际实现还必须处理计数所能表示的最大值。超过这一上限的游程可以拆分为多条编码记录。
编码的时间复杂度为 。解码为完全展开的序列同样需要 时间,因为必须写出每一个输出符号。当输入和输出采用流式处理,且计数字段的最大长度固定时,这两种操作都可以只使用常量大小的辅助工作内存。存储完整的编码或解码结果则需要额外空间。
压缩效果
RLE 利用的是较长的连续重复,而不只是某些值的高出现频率。序列 AAAAABBBBB 和 ABABABABAB 的符号频率相同,但分别包含两个和十个游程。
假设每个原始符号占 比特,每个编码后的游程用 比特存储其值,再用 比特存储其计数。忽略头部、填充和计数溢出后,原始数据和编码后数据的大小分别为
当满足以下条件时,编码能够实现压缩:
因此,在这一简化格式下,平均游程长度必须足够长,才能抵消存储计数带来的开销。如果值和计数各占八比特,那么只有平均每个游程超过两个符号时,编码后的表示才会更小。
游程较短时,RLE 可能使数据大幅膨胀。如果某种格式始终为每个游程存储一个值字节和一个计数字节,那么对于相邻字节均不相同的输入,编码后的大小约为原来的两倍。实际格式通常通过提供字面量块来减轻这一问题。
主要变体
值—计数对
最简单的形式为每个游程存储一个值和一个计数。计数可以采用固定位宽,也可以采用变长整数表示。定宽计数易于解析,但会限制游程长度;变长计数可以容纳更长的游程,但编码规则也会更复杂。
计数既可以表示实际游程长度,也可以表示相对于某个最小长度的偏移量。例如,存储的计数为零时,可能表示出现一次。这类约定必须由格式明确定义。
字面量块与重复块
许多面向字节的方案会区分:
- 字面量块:其中的字节原样复制。
- 重复块:指定一个值及其重复次数。
控制字节用于标识块的类型和长度。这样就不必为每个不重复的字节附加计数,不过字面量块的头部仍会带来开销。
TIFF 图像中的一种可选压缩方式 PackBits 就是常见的例子。其数据包结构既支持字面量字节序列,也支持重复字节游程。其他图像格式采用不同的控制约定,因此它们的 RLE 数据流不能互换使用。
二值游程长度
对于二值数据,相邻游程的值会在零和一之间交替。如果初始值已知或另行存储,编码后的表示就可以只包含游程长度。
例如:
000011100
可以表示为初始值 0 和长度序列 4, 3, 2。面向图像的方案可能假定每行以某种特定颜色开始,并在必要时使用长度为零的初始游程。
指定值的游程
有些方案只对某个选定值的游程进行编码,通常是零,而以其他方式表示其余值。当某种变换产生大量零值,却很少产生任意非零值的长游程时,这种方法很有用。
应用与相关技术
图像与文档传输
RLE 适合具有大片均匀区域的图像,包括图标、示意图、单色文档以及某些屏幕图形。某些 BMP 变体为索引色图像提供 RLE 模式,TIFF 则支持 PackBits。
图像的排列方式会影响压缩效果。逐行独立编码会阻止游程跨越行边界。即使图像本身不变,采用不同的扫描顺序也可能产生不同的游程长度。
传真编码方法利用扫描文档中交替出现的黑色和白色游程。这些游程的长度可以用变长码表示,而不必使用固定大小的整数。
基于变换的压缩
RLE 通常是更大的数据压缩流程中的一个阶段。在常见的 JPEG图像编码标准编码过程中,量化后的交流系数按某种顺序扫描,这种顺序往往能将零聚集在一起。编码时,将零游程与随后非零系数的相关信息一并表示,并用特殊符号处理特定情况。这并不是简单地直接对像素应用 RLE。
RLE 也可以与霍夫曼编码或算术编码结合,进一步压缩得到的计数和符号。这些方法利用的是不同形式的冗余:RLE 利用连续重复,而熵编码则根据符号的概率分配相应的编码表示。
数据库与掩码
在数据库中,如果某列包含大量连续相同的值,就可以用值及其游程长度或游程边界来表示。排序可以将相同值聚集在一起,从而改善压缩效果,但排序会改变行顺序,并且可能需要额外的数据结构来保留原有关系。
某些操作可以直接在编码后的游程上执行。例如,统计匹配值的数量时,可能只需累加游程长度,而不必展开每条记录。实际收益取决于具体操作和游程数量。
在图像分割中,二值掩码可以存储为背景和前景交替出现的游程长度。为了正确重建掩码,这种表示必须指定图像尺寸、遍历顺序和初始值。
局限性与实现注意事项
依赖局部重复。 RLE 无法高效利用被其他数据隔开的重复片段,也无法有效利用不涉及相邻相同值的一般统计规律。
随机访问能力有限。 定位任意位置可能需要从头累加游程长度。前缀和、检查点或数据库索引可以加快访问速度,但代价是额外的存储空间。
对数据表示方式敏感。 字节级、像素级和记录级的 RLE 可能产生非常不同的结果。相等关系的定义以及所编码的单位,都是方案的组成部分。
解析与资源限制。 解码器必须区分字面值与控制字段,并拒绝格式错误或被截断的记录。不可信的计数可能导致输出内存分配过多、整数溢出或越过输出缓冲区边界的写入。因此,实现时必须对编码输入和展开后的输出都设定明确的大小限制。
是否无损取决于整个处理流程。 RLE 本身会完整保留其输入。如果它位于有损变换之后,如许多 JPEG 处理流程中的情况,那么它保留的是变换后的符号,而不能恢复此前已丢弃的信息。