游程编码（Run-Length Encoding，RLE）是最简单且历史最悠久的无损数据压缩算法之一。它的核心思想极其直观：将连续重复的字符序列替换为”字符+重复次数”的二元组。虽然RLE本身对一般文本的压缩效果有限，但在处理具有大量连续重复数据的场景（如简单图像、BWT变换后的数据、传真图像）时表现出色。
算法核心思想
RLE基于一个简单观察：许多类型的数据中存在大量连续相同的符号。例如：
– 二值图像中大片连续的黑白像素
– BWT变换后的数据中聚集的相同字符
– 简单图形的扫描线数据
编码过程
扫描输入数据，将连续重复的字符替换为(字符, 计数)的形式。
示例：
– 原始：AAAABBBCCDAA
– 编码：A4B3C2D1A2
解码过程
遍历编码序列，将每个(字符, 计数)展开为对应数量的字符。
位打包优化
对于二值数据（只有0和1），可以进一步优化：
– 使用变长编码表示连续的0和1的个数
– 或者固定使用N位存储计数，最大化压缩效率
Java完整实现
import java.util.*;
/**
* 游程编码（RLE）实现
* 包含基础RLE、位打包优化和二值图像专用版本
*/
public class RunLengthEncoding {
/**
* 基础RLE编码
* @param input 原始字节数组
* @return 编码后的(RLE符号)列表
*/
public List<Run> encode(byte[] input) {
List<Run> result = new ArrayList<>();
if (input == null || input.length == 0) {
return result;
}
byte current = input[0];
int count = 1;
for (int i = 1; i < input.length; i++) {
if (input[i] == current && count < 255) {
// 继续当前游程，上限255（用一个字节存储）
count++;
} else {
// 结束当前游程，开始新游程
result.add(new Run(current, count));
current = input[i];
count = 1;
}
}
// 添加最后一个游程
result.add(new Run(current, count));
return result;
}
/**
* 基础RLE解码
*/
public byte[] decode(List<Run> encoded) {
// 先计算总长度
int totalLength = 0;
for (Run run : encoded) {
totalLength += run.count;
}
byte[] result = new byte[totalLength];
int pos = 0;
for (Run run : encoded) {
Arrays.fill(result, pos, pos + run.count, run.value);
pos += run.count;
}
return result;
}
/**
* 将RLE结果打包为紧凑的字节数组
* 格式：[值1, 计数1, 值2, 计数2, ...]
*/
public byte[] packRuns(List<Run> runs) {
byte[] packed = new byte[runs.size() * 2];
for (int i = 0; i < runs.size(); i++) {
packed[i * 2] = runs.get(i).value;
packed[i * 2 + 1] = (byte) runs.get(i).count;
}
return packed;
}
/**
* 从字节数组解包RLE结果
*/
public List<Run> unpackRuns(byte[] packed) {
List<Run> runs = new ArrayList<>();
for (int i = 0; i < packed.length; i += 2) {
runs.add(new Run(packed[i], packed[i + 1] & 0xFF));
}
return runs;
}
/**
* 二值图像专用RLE（像素只有0和1）
* 假设数据以0开始交替记录游程长度
*/
public List<Integer> encodeBinary(byte[] input) {
List<Integer> result = new ArrayList<>();
if (input == null || input.length == 0) {
return result;
}
byte current = input[0];
int count = 1;
for (int i = 1; i < input.length; i++) {
if (input[i] == current) {
count++;
} else {
result.add(count);
current = input[i];
count = 1;
}
}
result.add(count);
// 如果原始数据以1开始，在头部插入0
if (input[0] == 1) {
result.add(0, 0);
}
return result;
}
/**
* 二值图像RLE解码
* @param encoded 游程长度列表（假设以0开始交替）
* @return 解码后的二值数据
*/
public byte[] decodeBinary(List<Integer> encoded) {
int totalLength = encoded.stream().mapToInt(Integer::intValue).sum();
byte[] result = new byte[totalLength];
int pos = 0;
byte value = 0;
for (int count : encoded) {
Arrays.fill(result, pos, pos + count, value);
pos += count;
value = (byte) (1 - value); // 0和1交替
}
return result;
}
/**
* 位打包编码：用位存储二值数据的游程
* 使用Golomb-Rice编码存储游程长度
*/
public BitPackedResult encodeBitPacked(byte[] input, int k) {
List<Integer> runs = encodeBinary(input);
// 使用k位存储商和余数（Golomb-Rice）
// 对于参数m=2^k，编码q = n/m, r = n%m
// q用一元编码，r用k位二进制
StringBuilder bits = new StringBuilder();
for (int run : runs) {
int q = run >> k; // 商
int r = run & ((1 << k) - 1); // 余数
// 一元编码商
for (int i = 0; i < q; i++) {
bits.append('1');
}
bits.append('0'); // 终止符
// k位二进制编码余数
String binary = Integer.toBinaryString(r);
while (binary.length() < k) {
binary = "0" + binary;
}
bits.append(binary);
}
return new BitPackedResult(bits.toString(), input[0] == 1, k);
}
/**
* 计算压缩率
*/
public double compressionRatio(byte[] original, List<Run> encoded) {
int originalSize = original.length;
int compressedSize = encoded.size() * 2; // 每个Run占2字节
return 1.0 - (double) compressedSize / originalSize;
}
/**
* RLE游程数据类
*/
public static class Run {
public final byte value;
public final int count;
public Run(byte value, int count) {
this.value = value;
this.count = count;
}
@Override
public String toString() {
return String.format("(%d,%d)", value & 0xFF, count);
}
}
/**
* 位打包结果封装
*/
public static class BitPackedResult {
public final String bitString;
public final boolean startsWithOne;
public final int k;
public BitPackedResult(String bitString, boolean startsWithOne, int k) {
this.bitString = bitString;
this.startsWithOne = startsWithOne;
this.k = k;
}
public int bitLength() {
return bitString.length();
}
public int byteLength() {
return (bitString.length() + 7) / 8;
}
}
public static void main(String[] args) {
RunLengthEncoding rle = new RunLengthEncoding();
// 测试1：基础RLE（文本数据）
String text = "AAAABBBCCDAAEEEEEEFFFFFFFF";
byte[] textBytes = text.getBytes();
System.out.println("=== 基础RLE测试 ===");
System.out.println("原始数据: " + text);
System.out.println("原始长度: " + textBytes.length + " 字节");
List<Run> encoded = rle.encode(textBytes);
System.out.println("RLE编码: " + encoded);
byte[] packed = rle.packRuns(encoded);
System.out.println("打包后长度: " + packed.length + " 字节");
double ratio = rle.compressionRatio(textBytes, encoded);
System.out.printf("压缩率: %.2f%%\n", ratio * 100);
byte[] decoded = rle.decode(rle.unpackRuns(packed));
System.out.println("解压验证: " + text.equals(new String(decoded)));
// 测试2：二值图像RLE
System.out.println("\n=== 二值图像RLE测试 ===");
byte[] binaryImage = {
0, 0, 0, 0, 0, 1, 1, 1,
1, 1, 0, 0, 0, 1, 1, 1,
1, 1, 1, 0, 0, 0, 0, 0
};
System.out.println("原始二值数据: " + Arrays.toString(binaryImage));
List<Integer> binaryEncoded = rle.encodeBinary(binaryImage);
System.out.println("二值RLE: " + binaryEncoded);
byte[] binaryDecoded = rle.decodeBinary(binaryEncoded);
System.out.println("解压验证: " + Arrays.equals(binaryImage, binaryDecoded));
// 测试3：BWT后的数据（RLE的理想场景）
System.out.println("\n=== BWT后数据RLE测试 ===");
String bwtLike = "annb$aaacccdddddeeee";
byte[] bwtBytes = bwtLike.getBytes();
List<Run> bwtEncoded = rle.encode(bwtBytes);
System.out.println("原始: " + bwtLike);
System.out.println("RLE编码: " + bwtEncoded);
double bwtRatio = rle.compressionRatio(bwtBytes, bwtEncoded);
System.out.printf("压缩率: %.2f%%\n", bwtRatio * 100);
}
}
算法变体与优化
游程预测编码
对于某些数据，可以存储当前游程与前一个游程的差值，进一步减小数值范围。
自适应RLE
根据数据的统计特性动态调整：
– 对高频字符使用更短的编码
– 对低频字符保留原始形式（避免负压缩）
与BWT的协同
RLE最常见的应用场景是BWT的后处理阶段。BWT将相似字符聚集后，RLE可以轻松将这些长游程压缩为极短编码。bzip2就是这一组合的经典代表。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 编码时间 | O(n) | 单次线性扫描 |
| 解码时间 | O(n) | 线性展开 |
| 空间复杂度 | O(n) | 最坏情况下翻倍 |
| 最佳压缩率 | 接近100% | 单一字符重复时 |
| 最差压缩率 | -100% | 无连续重复时，大小翻倍 |
实际应用
RLE广泛应用于：
– PCX图像格式：早期的PCX使用RLE压缩
– TIFF图像格式：支持多种RLE变体
– BMP图像格式：可选的RLE4和RLE8压缩
– 传真协议（G3/G4）：使用改进的RLE处理黑白扫描线
– BZIP2后处理：BWT+MTF后的RLE阶段
总结
游程编码虽然简单，但深刻理解它对于学习压缩算法至关重要：
1. 简单高效：实现简洁，编解码速度极快
2. 场景依赖：压缩效果高度依赖数据特性
3. 组合威力：与BWT、MTF等算法组合可产生强大的压缩效果
RLE是理解数据冗余和压缩本质的最佳入门算法。
