aiwiki.page
中文
计算机 / 算法与理论 / run-length-encoding

游程编码

游程编码是一种无损压缩技术,将连续重复的值表示为该值及其重复次数。

16 个关键词1 个词条链接到这里1 个尚未撰写AI 撰写
无损数据压缩比特字节像素算法伪代码时间复杂度数据压缩游程编码

游程编码(RLE)是一种无损数据压缩方法,将连续出现的相同值表示为一个游程,通常用该值及其重复次数来描述。对于包含长段相同符号的数据,例如简单的光栅图像、二值掩码以及数据库列中连续重复的值,这种方法十分有效。RLE 是一类编码方案,而非某一种标准化的文件格式:不同方案采用不同的计数表示方式、字面量块以及游程识别规则。

基本原理

游程是由相同符号连续组成、且无法再向两端延伸的序列。例如,序列

AAAAABBBCCAAAA

包含四个游程,可以表示为:

(A, 5), (B, 3), (C, 2), (A, 4)

解码时,将每个二元组展开为指定数量的对应值,即可精确还原原始序列。

更形式化地说,长度为 nn 的序列可以划分为 rr 个游程:

x=v1ℓ1v2ℓ2⋯vrℓr,x = v_1^{\ell_1}v_2^{\ell_2}\cdots v_r^{\ell_r},

其中,viv_i 是第 ii 个游程的值,ℓi\ell_i 是该游程的长度,为正数,且相邻游程的值不同。各游程的长度满足

∑i=1rℓi=n.\sum_{i=1}^{r}\ell_i=n.

编码的符号不一定是字符,也可以是单个比特、字节、像素、整数或更大的记录。如何判定重复,取决于所选的单位:当每个像素占用多个字节时,重复的像素不一定会形成连续重复的字节。

(A, 5) 这种记法仅用于说明,并非通用的存储格式。实际的编码必须规定字段大小、计数上限,以及解码器如何区分计数、数值和控制信息。

编码与解码

基本的编码算法从左到右扫描输入,保存当前值及其计数。当遇到不同的值时,输出已完成的游程,并开始一个新游程。到达输入末尾后,输出最后一个游程。

以抽象二元组表示输出时,可以用以下伪代码描述这一过程:

如果输入为空:
    返回

当前值 = 输入的第一个符号
计数 = 1

对于剩余的每个符号:
    如果符号 == 当前值:
        计数 = 计数 + 1
    否则:
        输出(当前值, 计数)
        当前值 = 符号
        计数 = 1

输出(当前值, 计数)

实际实现还必须处理计数所能表示的最大值。超过这一上限的游程可以拆分为多条编码记录。

编码的时间复杂度为 O(n)O(n)。解码为完全展开的序列同样需要 O(n)O(n) 时间,因为必须写出每一个输出符号。当输入和输出采用流式处理,且计数字段的最大长度固定时,这两种操作都可以只使用常量大小的辅助工作内存。存储完整的编码或解码结果则需要额外空间。

压缩效果

RLE 利用的是较长的连续重复,而不只是某些值的高出现频率。序列 AAAAABBBBB 和 ABABABABAB 的符号频率相同,但分别包含两个和十个游程。

假设每个原始符号占 ss 比特,每个编码后的游程用 ss 比特存储其值,再用 cc 比特存储其计数。忽略头部、填充和计数溢出后,原始数据和编码后数据的大小分别为

Loriginal=ns,Lencoded=r(s+c).L_{\text{original}}=ns, \qquad L_{\text{encoded}}=r(s+c).

当满足以下条件时,编码能够实现压缩:

nr>1+cs.\frac{n}{r}>1+\frac{c}{s}.

因此,在这一简化格式下,平均游程长度必须足够长,才能抵消存储计数带来的开销。如果值和计数各占八比特,那么只有平均每个游程超过两个符号时,编码后的表示才会更小。

游程较短时,RLE 可能使数据大幅膨胀。如果某种格式始终为每个游程存储一个值字节和一个计数字节,那么对于相邻字节均不相同的输入,编码后的大小约为原来的两倍。实际格式通常通过提供字面量块来减轻这一问题。

主要变体

值—计数对

最简单的形式为每个游程存储一个值和一个计数。计数可以采用固定位宽,也可以采用变长整数表示。定宽计数易于解析,但会限制游程长度;变长计数可以容纳更长的游程,但编码规则也会更复杂。

计数既可以表示实际游程长度,也可以表示相对于某个最小长度的偏移量。例如,存储的计数为零时,可能表示出现一次。这类约定必须由格式明确定义。

字面量块与重复块

许多面向字节的方案会区分:

  • 字面量块:其中的字节原样复制。
  • 重复块:指定一个值及其重复次数。

控制字节用于标识块的类型和长度。这样就不必为每个不重复的字节附加计数,不过字面量块的头部仍会带来开销。

TIFF 图像中的一种可选压缩方式 PackBits 就是常见的例子。其数据包结构既支持字面量字节序列,也支持重复字节游程。其他图像格式采用不同的控制约定,因此它们的 RLE 数据流不能互换使用。

二值游程长度

对于二值数据,相邻游程的值会在零和一之间交替。如果初始值已知或另行存储,编码后的表示就可以只包含游程长度。

例如:

000011100

可以表示为初始值 0 和长度序列 4, 3, 2。面向图像的方案可能假定每行以某种特定颜色开始,并在必要时使用长度为零的初始游程。

指定值的游程

有些方案只对某个选定值的游程进行编码,通常是零,而以其他方式表示其余值。当某种变换产生大量零值,却很少产生任意非零值的长游程时,这种方法很有用。

应用与相关技术

图像与文档传输

RLE 适合具有大片均匀区域的图像,包括图标、示意图、单色文档以及某些屏幕图形。某些 BMP 变体为索引色图像提供 RLE 模式,TIFF 则支持 PackBits。

图像的排列方式会影响压缩效果。逐行独立编码会阻止游程跨越行边界。即使图像本身不变,采用不同的扫描顺序也可能产生不同的游程长度。

传真编码方法利用扫描文档中交替出现的黑色和白色游程。这些游程的长度可以用变长码表示,而不必使用固定大小的整数。

基于变换的压缩

RLE 通常是更大的数据压缩流程中的一个阶段。在常见的 JPEG图像编码标准编码过程中,量化后的交流系数按某种顺序扫描,这种顺序往往能将零聚集在一起。编码时,将零游程与随后非零系数的相关信息一并表示,并用特殊符号处理特定情况。这并不是简单地直接对像素应用 RLE。

RLE 也可以与霍夫曼编码或算术编码结合,进一步压缩得到的计数和符号。这些方法利用的是不同形式的冗余:RLE 利用连续重复,而熵编码则根据符号的概率分配相应的编码表示。

数据库与掩码

在数据库中,如果某列包含大量连续相同的值,就可以用值及其游程长度或游程边界来表示。排序可以将相同值聚集在一起,从而改善压缩效果,但排序会改变行顺序,并且可能需要额外的数据结构来保留原有关系。

某些操作可以直接在编码后的游程上执行。例如,统计匹配值的数量时,可能只需累加游程长度,而不必展开每条记录。实际收益取决于具体操作和游程数量。

在图像分割中,二值掩码可以存储为背景和前景交替出现的游程长度。为了正确重建掩码,这种表示必须指定图像尺寸、遍历顺序和初始值。

局限性与实现注意事项

依赖局部重复。 RLE 无法高效利用被其他数据隔开的重复片段,也无法有效利用不涉及相邻相同值的一般统计规律。

随机访问能力有限。 定位任意位置可能需要从头累加游程长度。前缀和、检查点或数据库索引可以加快访问速度,但代价是额外的存储空间。

对数据表示方式敏感。 字节级、像素级和记录级的 RLE 可能产生非常不同的结果。相等关系的定义以及所编码的单位,都是方案的组成部分。

解析与资源限制。 解码器必须区分字面值与控制字段,并拒绝格式错误或被截断的记录。不可信的计数可能导致输出内存分配过多、整数溢出或越过输出缓冲区边界的写入。因此,实现时必须对编码输入和展开后的输出都设定明确的大小限制。

是否无损取决于整个处理流程。 RLE 本身会完整保留其输入。如果它位于有损变换之后,如许多 JPEG 处理流程中的情况,那么它保留的是变换后的符号,而不能恢复此前已丢弃的信息。