算法原理
游程編碼 (Run-Length Encoding, RLE) 是最簡單的無損壓縮算法：將連續重複的字符替換為 計數 + 字符。適合含大量連續重複數據的場景 (如 BMP 圖像、簡單文本、日誌)。
示例
原文: "AAABBBCCCCCDD" (12 字符)
編碼: "3A3B5C2D" (8 字符, 壓縮率 33%)
解碼: 還原為原文
完整 Java 實現
public final class RleCodec {
/** 編碼：字符串 -> RLE 壓縮字符串 */
public static String encode(String source) {
if (source == null || source.length() <= 1) return source;
StringBuilder sb = new StringBuilder();
int len = source.length();
for (int i = 0; i < len; ) {
char cur = source.charAt(i);
int run = 1;
while (i + run < len && source.charAt(i + run) == cur) run++;
if (run > 1) sb.append(run).append(cur);
else sb.append(cur);
i += run;
}
return sb.toString();
}
/** 解碼：RLE 字符串 -> 原文字符串 */
public static String decode(String encoded) {
if (encoded == null || encoded.length() <= 1) return encoded;
StringBuilder sb = new StringBuilder();
int len = encoded.length();
for (int i = 0; i < len; i++) {
char ch = encoded.charAt(i);
if (Character.isDigit(ch)) {
// 讀取完整數字 (支援多位數計數)
int j = i;
while (j < len && Character.isDigit(encoded.charAt(j))) j++;
int count = Integer.parseInt(encoded.substring(i, j));
// 下一字符為重複字符
if (j < len) {
char repeat = encoded.charAt(j);
sb.append(String.valueOf(repeat).repeat(Math.max(0, count)));
i = j; // 外層循環會 i++
}
} else {
sb.append(ch);
}
}
return sb.toString();
}
// 測試
public static void main(String[] args) {
String[] tests = {
"AAABBBCCCCCDD",
"Hello World",
"111222333",
"A",
"",
"12A3B" // 包含數字字符的原文測試
};
for (String s : tests) {
String enc = encode(s);
String dec = decode(enc);
System.out.printf("原文: %-15s 編碼: %-10s 解碼: %-15s %s%n",
"\"" + s + "\"", "\"" + enc + "\"", "\"" + dec + "\"",
s.equals(dec) ? "✓" : "✗ 失敗");
}
}
}
關鍵實現細節
| 點 | 處理 |
|---|
| 多位數計數 | while (isdigit) j++ 解析完整整數，支援 >9 連續字符 |
| 原文含數字 | 編碼時不對單個字符輸出計數 1，解碼時只有數字後緊跟字符才視為計數，避免歧義 |
| 空字符串/單字符 | 直接返回 |
| 性能 | O(N) 時間，StringBuilder 避免字符串拼接開銷 |
變體與優化方向
- 位級 RLE：針對二進制圖像 (如傳真、BMP)，按位編碼，壓縮率更高
- 帶符號 RLE：區分「字面長度」與「重複長度」，如
0-127: 字面長度; 128-255: 重複長度 (PCX 格式)
- 二維 RLE：掃描行間共享游程，用於 TIFF、PDF 圖像壓縮
- 硬件加速：GPU/ASIC 並行掃描計數
應用場景與局限
| 適合 | 不適合 |
|---|
| 簡單圖像 (圖標、掃描件、漫畫) | 自然照片、加密數據、高熵文本 |
| 日誌文件 (大量重複時間戳/級別) | 已壓縮文件 (zip、jpg、mp4) |
| 網絡傳輸帶寬受限、CPU 受限環境 | 需要高壓縮比的通用存儲 |
現代替代品對比
| 算法 | 壓縮率 | 速度 | 複雜度 | Java 實現 |
|---|
| RLE | 低 (專用數據高) | 極快 | O(1) | 手寫 20 行 |
| LZ4 | 中 | 極快 (GB/s) | 中 | lz4-java |
| Snappy | 中 | 極快 | 中 | snappy-java |
| Zstd | 高 | 快 | 高 | zstd-java |
| GZIP/Deflate | 高 | 中 | 高 | JDK 內建 |
總結
RLE 是壓縮算法入門的「Hello World」，代碼極簡、無狀態、流式友好。雖通用壓縮率低，但在特定數據模式 (長游程)、嵌入式設備、教學演示、簡單協議幀分隔 等場景仍具獨特價值。掌握其編碼/解碼對稱邏輯、數字歧義消解、邊界條件處理，有助於理解 LZ77、Huffman 等現代算法的基因。
