Run-Length Encoding(RLE)

Run-length encoding 是被许多 bitmap 文件格式支持的数据压缩算法
适合压缩任何数据类型, 压缩比例受数据内容所影响
RLE 不能获得高级压缩方法的压缩比例, 但是容易实现和执行
作为使用复杂压缩算法或者不使用压缩的另一种选择
RLE 工作方式是减少重复字符的物理尺寸, 被编码成两个字节, 第一个字节表示字符数量, 第二个字节表示本身字符值.

例子

15 个 A 的字符串在不压缩的情况下需要 15 个字节存储

AAAAAAAAAAAAAAA

当使用 RLE 编码之后, 仅仅需要 2 个字节

15A

上面形成的 15A 表示一个 RLE 包, 第一个字节 15 表示 run 的数量, 表示重复的数量, 第二个字节 A 表示 run 值, 表示字符本身.

当 run 字符发生变化时或者 run 的数量超过了最大可用值, 新的包会形成.

例如, 字符串包含 4 个不同字符

AAAAAAbbbXXXXXt

使用 RLE, 可以形成 4 个 2 字节包

6A3b5X1t

当编码之后, 15 个字节字符串仅仅需要 8 字节字符串表示. 压缩比例达到 2:1. 长的 run 在特定数据类型中很少见, 例如 ASCII 文本. 在上面的例子中, 最后的 run(t) 仅仅包含一个字符, 一个字符也是一个 run, 也需要一个 run 数量和 run 值, 因此一个单个的 run 实际需要更多的空间. 同样的道理, 两个字符的数据当 RLE 编码后, 需要相同的空间大小.

在上面的例子中, 最后单个字符并不会影响压缩比例, 因为数据存在很多长的 run.

但是需要注意下面的情况: