Python字符串解压算法：从基础RLE到复杂嵌套模式的实现与解析93

在数据处理和信息传输领域，字符串压缩与解压是常见的操作，旨在减少存储空间和提高传输效率。Python作为一门功能强大且易于学习的语言，提供了丰富的工具和灵活的语法来实现各种字符串解压算法。本文将深入探讨Python中不同层次的字符串解压算法，从最基础的运行长度编码（RLE）到处理复杂嵌套重复模式的高级算法，并提供详细的代码实现和解析。

一、字符串解压的背景与意义

字符串压缩的核心思想是识别并消除重复模式。例如，字符串 "AAAABBC" 可以被压缩为 "A4B2C1"。解压则是这个过程的逆向操作，即将压缩后的字符串恢复到原始形式。解压算法的设计需要考虑以下几个方面：
效率：解压速度对实时性要求高的应用至关重要。
准确性：必须确保解压后的字符串与原始字符串完全一致。
适用性：算法应能处理各种类型的压缩模式。
鲁棒性：对异常或格式不正确的输入应有合理的处理机制。

Python因其简洁的语法和强大的字符串操作能力，成为实现这些算法的理想选择。

二、基础解压算法：运行长度编码 (Run-Length Encoding, RLE)

运行长度编码（RLE）是一种非常简单且广泛使用的无损数据压缩算法。它通过存储连续重复字符的次数来压缩数据。例如，字符串 "AAABBCDDD" 可以被RLE压缩为 "A3B2C1D3"。RLE解压算法的目标就是将这种格式恢复为原始字符串。

2.1 RLE压缩规则

RLE压缩通常遵循“字符+重复次数”的模式。如果字符只出现一次，次数可以省略（如 "C" 等同于 "C1"），也可以显式表示。为了简化，我们假设数字总是跟在字符后面，且数字表示重复次数。

2.2 Python实现RLE解压

RLE解压的思路是遍历压缩字符串。当遇到一个字母时，它代表一个需要重复的字符；紧接着的数字则代表重复的次数。我们将这些字符和次数组合起来，构建解压后的字符串。

```python
import re
def decompress_rle(compressed_string: str) -> str:
"""
解压运行长度编码（RLE）字符串。
假设输入格式为 '字符数字'，例如 'A3B2C1D3'。
如果字符只出现一次，数字可以省略（例如 'C' 视为 'C1'）。

Args:
compressed_string: 压缩后的RLE字符串。

Returns:
解压后的原始字符串。
"""
if not compressed_string:
return ""
decompressed_parts = []
i = 0
n = len(compressed_string)
while i < n:
char = compressed_string[i]
i += 1
# 收集数字部分
count_str = ""
while i < n and compressed_string[i].isdigit():
count_str += compressed_string[i]
i += 1

# 如果没有数字，默认为1
count = int(count_str) if count_str else 1

(char * count)

return "".join(decompressed_parts)
# 示例测试
print(f"RLE 解压 'A3B2C1D3': {decompress_rle('A3B2C1D3')}") # 输出：AAABBCDDD
print(f"RLE 解压 'X5Y': {decompress_rle('X5Y')}") # 输出：XXXXXY
print(f"RLE 解压 'ABC': {decompress_rle('ABC')}") # 输出：ABC
print(f"RLE 解压 '': {decompress_rle('')}") # 输出：
print(f"RLE 解压 'a1b2c3': {decompress_rle('a1b2c3')}") # 输出：abbccc
```

2.3 算法分析

时间复杂度： O(N)，其中 N 是压缩字符串的长度。因为我们只需要遍历一次压缩字符串。如果考虑到最终解压后字符串的长度 M，那么实际操作（字符串拼接）的时间复杂度可能接近 O(M)，因为每次 `char * count` 都会创建一个新字符串。使用列表 `append` 后 `"".join` 可以优化到 O(M)。
空间复杂度： O(M)，其中 M 是解压后字符串的长度。这是存储解压结果所需的空间。

三、进阶解压算法：处理嵌套重复模式

RLE算法只能处理简单的连续字符重复。然而，在实际应用中，我们可能会遇到更复杂的压缩格式，例如 `3[a]2[bc]` 解压为 `aaabcbc`，或者更进一步的嵌套模式，如 `3[a2[c]]` 解压为 `accaccacc`。这种模式通常需要借助数据结构——栈（Stack）来解决。

3.1 嵌套重复模式的规则

我们定义一种更通用的压缩规则：
数字后面跟着方括号 `[]`，表示方括号内的子串需要重复的次数。
方括号内的子串可以包含普通字符，也可以包含嵌套的 `数字[子串]` 模式。
例如：

`3[a]` -> `aaa`
`2[abc]` -> `abcabc`
`3[a2[c]]` -> `accaccacc` (内部 `2[c]` 变为 `cc`，然后 `3[acc]` 变为 `accaccacc`)
`2[ab]3[c]` -> `ababc` (没有嵌套，但有多个独立重复块)

3.2 为什么需要栈？

当遇到嵌套结构时，我们需要“记住”当前处理到哪个重复次数和哪部分已经解压的字符串，以便在内部的子结构解压完成后，能正确地将它们组合起来。栈的后进先出（LIFO）特性非常适合这种“记住并稍后恢复”的场景：
当遇到一个数字和紧随其后的 `[` 时，这意味着我们要开始解压一个新的内部模式。我们需要把当前已经构建好的字符串和当前的重复次数“压入栈中”，以便在解压完内部模式后能继续处理。
当遇到 `]` 时，表示一个内部模式解压完成。我们从栈中“弹出”之前保存的重复次数和外层字符串，将刚刚解压的内部模式重复相应次数后，追加到外层字符串上。

3.3 Python实现嵌套解压（基于栈）

```python
def decompress_nested_string(s: str) -> str:
"""
解压包含嵌套重复模式的字符串。
例如 '3[a]2[bc]' -> 'aaabcbc', '3[a2[c]]' -> 'accaccacc'。

Args:
s: 压缩后的字符串。

Returns:
解压后的原始字符串。
"""
stack = [] # 栈用于存储 [重复次数, 当前已解压的字符串]
current_string = "" # 当前正在构建的字符串片段
current_num = 0 # 当前的重复次数

for char in s:
if '0'