Java中游程编码和解码

在计算机科学中，数据压缩技术在优化存储和传输效率方面发挥着重要作用。一种经受住时间考验的技术是游程编码（RLE）。

在本教程中，我们将了解 RLE 并探索如何在 Java 中实现编码和解码。

什么是游程编码
游程编码是一种简单而有效的无损数据压缩形式。RLE 背后的基本思想是通过单个值及其计数来表示连续的相同元素，称为数据流中的“运行”，而不是作为原始运行。

这在处理重复序列时特别有用，因为它显着减少了存储或传输数据所需的空间量。

RLE 非常适合压缩基于调色板的位图图像，例如计算机图标和动画。一个著名的例子是 Microsoft Windows 3.x 启动屏幕，它是 RLE 压缩的。

让我们考虑以下示例：
String INPUT = "WWWWWWWWWWWWBAAACCDEEEEE";

如果我们对上面的字符串应用游程编码数据压缩算法，它可以呈现如下：
String RLE = "12W1B3A2C1D5E";

在编码序列中，每个字符遵循其连续出现的次数。这个规则使我们能够在解码过程中轻松地重建原始数据。

值得注意的是，标准 RLE 仅适用于“文本”输入。如果输入包含数字，RLE 无法以明确的方式对它们进行编码。

在本教程中，我们将探索两种游程编码和解码方法。

1、基于字符数组的解决方案
现在我们了解了 RLE 及其工作原理，实现游程编码和解码的经典方法是将输入字符串转换为 char数组，然后将编码和解码规则应用于该数组。

创建编码方法
实现游程编码的关键是识别每个游程并计算其长度。我们首先看一下实现，然后了解它是如何工作的：

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();
}

首先，我们使用StringBuilder来存储每个步骤的结果并将它们连接起来以获得更好的性能。

初始化计数器并将输入字符串转换为字符数组后，该函数将迭代输入字符串中的每个字符。

对于每个字符：

• 如果当前字符与下一个字符相同并且不在字符串的末尾，则计数会增加。
• 如果当前字符与下一个字符不同或者位于字符串末尾，则计数和当前字符将附加到结果StringBuilder中。然后，对于下一个唯一字符，计数将重置为1 。

当我们使用这种编码方法测试INPUT时，我们得到了预期的结果：

assertEquals(RLE, runLengthEncode(INPUT));

创建解码方法
识别每次运行对于解码 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();
}

首先，我们创建一个StringBuilder 对象来保存步骤结果，并将rle字符串转换为 char 数组以供后续处理。

此外，我们还初始化了一个整型变量count来跟踪连续出现的次数。

然后，我们迭代 RLE 编码字符串中的每个字符。对于每个字符：

• 如果字符是数字，则它有助于计数。通过使用公式10 * count + Character.getNumericValue(c)将数字附加到现有计数来更新计数。这样做是为了处理多位数计数。
• 如果该字符不是数字，则遇到新字符。然后使用Collections.nCopies()将当前字符追加到StringBuilder 重复计数次数的结果中。然后，对于下一组连续发生的情况，计数将重置为0 。

当我们使用示例验证解码方法时，测试通过：

assertEquals(INPUT, runLengthDecode(RLE));

2、基于正则表达式的解决方案
正则表达式是处理字符和字符串的强大工具。让我们看看是否可以使用正则表达式执行游程编码和解码。

创建编码方法
我们首先看一下输入字符串。如果我们可以将其拆分成一个“run数组”，那么问题就很容易解决了：

Input     : "WWWWWWWWWWWWBAAACCDEEEEE"
Run Array : ["WWWWWWWWWWWW", "B", "AAA", "CC", "D", "EEEEE"]

我们无法通过字符分割输入字符串来实现此目的。相反，我们必须按零宽度位置进行分割，例如“ W ”和“ B ”、“ B ”和“ A ”之间的位置等。

不难发现这些位置的规律：位置前后的字符是不同的。因此，我们可以使用环视和反向引用构建一个正则表达式来匹配所需的位置：“ (?<=(\\D))(?!\\1) ”。让我们快速理解这个正则表达式的含义：

• (?<=(\\D)) – 正向后向断言 look-behind可确保匹配位于非数字字符之后（\\D表示非数字字符）。
• (?!\\1) – 负向先行断言 lookahead确保匹配位置不在正向后向断言中相同的字符之前。\\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();
}

runLengthEncodeByRegEx ()方法通过了我们的测试：

assertEquals(RLE, runLengthEncodeByRegEx(INPUT));

创建解码方法
我们可以遵循类似的想法来解码 RLE 编码的字符串。首先，我们需要分割编码后的字符串并获得以下数组：

RLE String: "12W1B3A2C1D5E"
Array     : ["12", "W", "1", "B", "3", "A", "2", "C", "1", "D", "5", "E"]

一旦我们得到这个数组，我们就可以通过轻松地重复每个字符来生成解码后的字符串，例如“ W ” 12次，“ B ”一次等。

我们将再次使用环视技术来创建正则表达式来分割输入字符串：“ (?<=\\D)|(?=\\D+) ”。

在这个正则表达式中：

• (?<=\\D) – 正向后向断言 look-behind可确保拆分发生在非数字字符之后。
• | – 表示“或”关系
• (?=\\D+) – 正向先行断言 lookahead可确保拆分发生在一个或多个非数字字符之前。

接下来，我们构建基于正则表达式分割的解码方法：

String runLengthDecodeByRegEx(String rle) {
    if (rle.isEmpty()) {
        return "";
    }
    String[] arr = rle.split("(?<=\\D)|(?=\\D+)");
    if (arr.length % 2 != 0) {
        throw new IllegalArgumentException("Not a RLE string");
    }
    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();
}

最后，这种解码方法适用于我们的示例：

assertEquals(INPUT, runLengthDecodeByRegEx(RLE));

结论
在本文中，我们首先讨论了游程编码的工作原理，然后探讨了实现游程编码和解码的两种方法。