第58天：Python 运行长度编码（RLE）——使用这个超简洁的 O(n) 技巧专业压缩字符串

Source: Dev.to

介绍

欢迎来到 #80DaysOfChallenges 之旅的第 58 天！本次中级挑战实现了 运行长度编码（RLE），这是一种经典的压缩技术，可以把 "AAAAABBBCC" 转换为 "A5B3C2"。它同样被用于传真机、BMP 图像，甚至一些游戏格式，对具有长串重复字符的数据效果惊人。

该解决方案纯粹、易读，且在 O(n) 时间和 O(1) 额外空间（除输出外）下运行。无需库、无需复杂性，只是干净的 Python 代码即可工作。

如果你对压缩、数据编码感兴趣，或只是喜欢看到长字符串显著缩短，这个 “Python RLE 压缩器” 既美观又实用，立刻可用。

示例

"WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWB"
→ "W12B1W12B3W24B1"

第 58 天的关键要点：RLE 编码函数

函数设计：立即检查空输入

def rle_encode(text: str) -> str:
    if not text:
        return ""

    result = []
    count = 1

对空输入返回空字符串，完美。初始化一个结果列表（用于高效构建）和 count = 1（因为单个字符算作长度 1 的运行）。

核心循环：运行检测的魔法

    for i in range(1, len(text)):
        if text[i] == text[i - 1]:
            count += 1
        else:
            result.append(f"{text[i - 1]}{count}")
            count = 1

• 如果当前字符等于前一个字符，计数 count 加 1。
• 否则，结束当前运行，将其加入 result，并将 count 重置为 1，开始新的运行。

对于 "AAA"：
i = 1 → count = 2，i = 2 → count = 3 → 循环结束 → 最后追加 "A3"。

最后一次运行：别忘了最后的分组！

    # Handle the final run
    result.append(f"{text[-1]}{count}")

    return "".join(result)

循环会遗漏最后一次运行，所以我们在结束时统一追加。这是基于运行的算法中的经典模式。

主交互：真实测试

user_input = input("Enter a string to encode: ").strip()

if user_input == "":
    print("No input provided. Exiting.")
else:
    encoded = rle_encode(user_input)
    print(f"Encoded (RLE): {encoded}")

干净的输入，立即得到压缩结果。试试 "aaaabbbcca" → "a4b3c2a1"。

总结与反思

这个 RLE 编码器简短、完美，展示了数据压缩中最有用的模式之一：计数器重置的运行检测。它强化了以下概念：

• 始终单独处理最后一次运行 – 所有运行长度算法的通用做法。
• 列表 + join 优于字符串 += – 对长运行而言是 O(n) 而不是 O(n²)。
• 真实的压缩威力 – "A" × 1 000 000 会变成 "A1000000"，体积极小！

该技术被用于 PNG、TIFF，甚至一些视频编解码器。

高级替代方案

• 实现一个 解码 函数（RLE 是可逆的！）。
• 处理输入中的数字（当前版本把 "111" 当作三个 '1' 字符）。
• 为文件压缩使用 二进制 RLE。

后续步骤与资源

第 58 天让你只用几行代码就拥有了真实的压缩能力。尝试把你的名字重复 1000 次进行压缩吧！

• 挑战 #58 的源代码：scripts/run_length_encoding.py
• 主仓库：80-days-of-challenges
• 每日更新：Twitter/X (@Shahrouzlogs)

你压缩过的最长运行是什么？在下方留下你最狂野的字符串吧！ 🔥