Java中的游程编码与解码实现

1. 概述

在计算机科学中，数据压缩技术对优化存储和传输效率至关重要。游程编码（Run-Length Encoding, RLE）就是其中一种经久不衰的经典压缩算法。

本文将深入解析RLE原理，并探讨在Java中实现编码和解码的两种方案。

2. 理解游程编码

游程编码是一种简单高效的无损数据压缩技术。其核心思想是将数据流中连续相同的元素（称为"游程"）用单个值及其出现次数表示，而非存储原始序列。

这种技术特别适合处理重复性强的数据，能显著减少存储和传输所需空间。RLE常用于压缩调色板位图图像（如计算机图标和动画），典型案例是微软Windows 3.x启动画面的压缩。

看个具体例子：

String INPUT = "WWWWWWWWWWWWBAAACCDEEEEE";

应用RLE算法后，压缩结果为：

String RLE = "12W1B3A2C1D5E";

在编码序列中，每个字符前都跟着其连续出现的次数。这种规则使解码时能轻松还原原始数据。

⚠️ 需要注意：标准RLE仅适用于纯文本输入。若输入包含数字，RLE无法进行无歧义编码。

本文将探讨两种RLE编解码实现方案。

3. 基于字符数组的解决方案

理解RLE原理后，经典实现方式是将输入字符串转为字符数组，再应用编解码规则。

3.1. 创建编码方法

实现RLE编码的关键在于识别每个游程并计算其长度。先看实现代码：

String runLengthEncode(String input) {
    StringBuilder result = new StringBuilder();
    int count = 1;
    char[] chars = input.toCharArray();
    for (int i = 0; i < chars.length; i++) {
        char c = chars[i];
        if (i + 1 < chars.length && c == chars[i + 1]) {
            count++;
        } else {
            result.append(count).append(c);
            count = 1;
        }
    }
    return result.toString();
}

代码逻辑解析：

1. 使用StringBuilder高效拼接结果
2. 初始化计数器并转换输入为字符数组
3. 遍历每个字符：
   • 当前字符与下一字符相同且未到末尾时：计数器递增
   • 当前字符与下一字符不同或到达末尾时：将计数和当前字符追加到结果，重置计数器为1

测试用例验证：

assertEquals(RLE, runLengthEncode(INPUT));

3.2. 创建解码方法

解码RLE字符串的关键仍是识别游程。游程包含字符及其重复次数（如"12W"或"2C"）。

解码方法实现：

String runLengthDecode(String rle) {
    StringBuilder result = new StringBuilder();
    char[] chars = rle.toCharArray();

    int count = 0;
    for (char c : chars) {
        if (Character.isDigit(c)) {
            count = 10 * count + Character.getNumericValue(c);
        } else {
            result.append(String.join("", Collections.nCopies(count, String.valueOf(c))));
            count = 0;
        }
    }
    return result.toString();
}

代码解析：

1. 初始化StringBuilder和字符数组
2. 遍历RLE字符串的每个字符：
   • 字符为数字时：更新计数（10 * count + 数字值），此处理支持多位数计数
   • 字符为非数字时：将当前字符重复count次追加到结果，重置计数器

✅ Java 11+优化：可用String.valueOf(c).repeat(count)替代Collections.nCopies()

测试验证：

assertEquals(INPUT, runLengthDecode(RLE));

4. 基于正则表达式的解决方案

正则表达式是处理字符和字符串的利器，我们尝试用它实现RLE编解码。

4.1. 创建编码方法

核心思路是将输入字符串拆分为"游程数组"：

输入     : "WWWWWWWWWWWWBAAACCDEEEEE"
游程数组 : ["WWWWWWWWWWWW", "B", "AAA", "CC", "D", "EEEEE"]

需在字符变化处（如W→B、B→A）进行零宽度分割。构建正则表达式：(?<=(\\D))(?!\\1)，解析如下：

• (?<=(\\D))：正向后行断言，确保匹配位置在非数字字符之后
• (?!\\1)：负向先行断言，确保匹配位置不在与前一个相同字符之前（\\1引用前一个匹配字符）

组合使用可在相同字符游程边界处分割字符串。

编码方法实现：

String runLengthEncodeByRegEx(String input) {
    String[] arr = input.split("(?<=(\\D))(?!\\1)");
    StringBuilder result = new StringBuilder();
    for (String run : arr) {
        result.append(run.length()).append(run.charAt(0));
    }
    return result.toString();
}

获取游程数组后，只需将每个游程的长度和首字符追加到结果即可。

测试验证：

assertEquals(RLE, runLengthEncodeByRegEx(INPUT));

4.2. 创建解码方法

类似思路，需将RLE字符串拆分为：

RLE字符串: "12W1B3A2C1D5E"
数组     : ["12", "W", "1", "B", "3", "A", "2", "C", "1", "D", "5", "E"]

构建分割正则：(?<=\\D)|(?=\\D+)，解析如下：

• (?<=\\D)：正向后行断言，在非数字字符后分割
• |：逻辑或
• (?=\\D+)：正向先行断言，在一个或多个非数字字符前分割

此组合可在计数与字符边界处分割RLE字符串。

解码方法实现：

String runLengthDecodeByRegEx(String rle) {
    if (rle.isEmpty()) {
        return "";
    }
    String[] arr = rle.split("(?<=\\D)|(?=\\D+)");
    if (arr.length % 2 != 0) {
        throw new IllegalArgumentException("非RLE格式字符串");
    }
    StringBuilder result = new StringBuilder();

    for (int i = 1; i <= arr.length; i += 2) {
        int count = Integer.parseInt(arr[i - 1]);
        String c = arr[i];

        result.append(String.join("", Collections.nCopies(count, c)));
    }
    return result.toString();
}

代码包含基础验证：

1. 空字符串直接返回
2. 数组长度必须为偶数（计数+字符成对出现）
3. 遍历数组时，奇数位为计数，偶数位为字符

测试验证：

assertEquals(INPUT, runLengthDecodeByRegEx(RLE));

5. 总结

本文首先解析了游程编码的工作原理，然后探讨了两种实现方案：

• 基于字符数组的传统方法
• 基于正则表达式的简洁方案

两种方法各有特点：字符数组方案更直观易读，正则方案更简洁但需要理解正则技巧。实际项目中可根据团队熟悉度选择。

完整示例代码可在GitHub仓库获取。