Java中的游程编码及其解码

Kahen大约 6 分钟

Java中的游程编码及其解码

1. 概述

在计算机科学中，数据压缩技术在优化存储和传输效率方面扮演着重要角色。其中一种历经时间考验的技术是游程编码（Run-length Encoding，简称RLE）。

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

2. 理解游程编码

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

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

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

让我们考虑以下示例：

String INPUT = "WWWWWWWWWWWWBAAACCDEEEEE";

如果我们对上面的字符串应用游程编码数据压缩算法，它可以被渲染为：

String RLE = "12W1B3A2C1D5E";

在编码序列中，每个字符后面跟着它连续出现的次数。这个规则允许我们在解码期间轻松地重建原始数据。

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

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

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

现在我们已经理解了RLE及其工作原理，实现游程编码和解码的一个经典方法是将输入字符串转换为_char_数组，然后对数组应用编码和解码规则。

3.1. 创建编码方法

实现游程编码的关键是识别每个游程并计算其长度。让我们首先看看实现，然后理解它的工作原理：

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_来存储每个步骤的结果，并将它们连接起来以获得更好的性能。

在初始化一个计数器并将输入字符串转换为_char_数组之后，该函数遍历输入字符串中的每个字符。

对于每个字符：

如果当前字符与下一个字符相同，并且我们不在字符串的末尾，则增加计数。
如果当前字符与下一个字符不同，或者我们在字符串的末尾，则将计数和当前字符追加到结果_StringBuilder_。然后，计数重置为_1_，以用于下一个唯一字符。

最后，使用_toString()_将_StringBuilder_转换为字符串，并将其作为编码过程的结果返回。

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

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

接下来，让我们逐步分解代码并理解它的工作原理。

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

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

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

如果字符是数字，它就有助于计数。通过使用公式_10 * count + Character.getNumericValue(c)_来更新计数。这是为了处理多位数字的计数。
如果字符不是数字，遇到了一个新的字符。然后，当前字符被追加到结果_StringBuilder_中，重复计数次，使用_Collections.nCopies()。然后，计数重置为_0，用于下一组连续出现。

值得一提的是，如果我们使用Java 11或更高版本，_String.valueOf(c).repeat(count)是重复字符_c _count_次的更好选择。

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

assertEquals(INPUT, runLengthDecode(RLE));

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

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

4.1. 创建编码方法

让我们首先看看输入字符串。如果我们能够将其分割成一个“游程数组”，那么问题就可以很容易地解决：

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

我们不能通过字符来分割输入字符串来实现这一点。相反，我们必须通过零宽位置来分割，例如在‘W’和‘B’之间、‘B’和‘A’之间等的位置。

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

(?<=(\D)) – 正向环视断言确保匹配是在非数字字符之后（\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();
}

正如我们所看到的，在我们获得游程数组之后，其余的任务只是简单地将每个游程的长度和字符追加到准备好的_StringBuilder_。

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

assertEquals(RLE, runLengthEncodeByRegEx(INPUT));

4.2. 创建解码方法

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

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

一旦我们获得这个数组，我们就可以通过简单地重复每个字符，例如‘W’重复12次，‘B’重复1次等，来生成解码后的字符串。

我们将再次使用环视技术来创建正则表达式来分割输入字符串：“(?<=\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("Not a RLE string");
    }
    StringBuilder result = new StringBuilder