波仔
⚙️ 第六章 自己动手压缩数据
📄 一句话概括

游程编码把连续重复的数据换成【什么数据 ＋ 重复几次】；它靠的规律只有一条——一大段一模一样。

📝 本节和前面几节的关系

6.1 定了度量（字节数），这一节从最简单的一种压缩讲起。

一、最简单的规律：重复

数据里最容易看出来的规律是什么？重复。 一长串同样的字节，写一遍就够了，剩下的只要说明【重复了几次】。 这就是游程编码（RLE，Run Length Encoding）的全部思想。 名字里的【游程】说的就是连续相同的一段。

二、规则：数据加次数

编码规则非常朴素：遇到连续重复的一段，就写成【那个字节 ＋ 重复次数】。 比如 10 个 41、5 个 42、12 个 43，三组就写完了，一共 6 个字节。 原来的 27 个字节压到 6 个，压到 22%、约 4.5 倍。 解码也一样简单：照着次数把字节重复出来即可，不需要查表、不需要额外信息。

三、为什么它特别好实现

只要两个变量：记住【当前是什么】和【已经连续几个了】。 一趟扫描就能编完，不用建表、不用排序、不用回头。 所以它又快又省内存，几十年前的传真机就能跑。 这也说明：压缩算法不一定要复杂——看数据有没有现成的规律可利用。

四、它最擅长什么

黑白传真：整行整行都是白，重复段长得离谱。 图标、线条画：大片同色，边界清晰。 稀疏数据：一整段都是 0，中间偶尔有个值。 共同点就是大块大块一样的东西连在一起。 反过来说，数据稍一杂乱，它就没辙了——这正是下一节要算的账。

五、动手 Demo：游程编码的原理

游程编码（RLE）的规则很简单： 把连续重复的数据，换成【什么数据 ＋ 重复了几次】。

data = b"A" * 10 + b"B" * 5 + b"C" * 12
runs = []
cur, n = data[0], 1
for b in data[1:]:
    if b == cur:
        n += 1
    else:
        runs.append((cur, n))
        cur, n = b, 1
runs.append((cur, n))
print(runs)

实跑输出：

--------------------------------------------------------------------
游程编码的原理
--------------------------------------------------------------------

游程编码（RLE）的规则很简单：
**把连续重复的数据，换成【什么数据 ＋ 重复了几次】。**

  一串数据（十六进制）：
    41 41 41 41 41 41 41 41 41 41 42 42 42 42 42 43 43 43 43 43 43 43 43 43 43 43 43
    也就是 10 个 41、5 个 42、12 个 43

  编码之后只剩三组：

  数据     重复几次     编码成
  -----------------------------
  41       10 次        41 0a
  42       5 次         42 05
  43       12 次        43 0c

    原始长度      27 字节
    编码后长度    6 字节（3 组 × 2 字节）
    压到了        22%（4.5 倍）

  **它靠的是数据里【一大段一模一样】的规律。**
  所以它最擅长黑白传真、图标这类**大片同色的图像**。

10 个 41、5 个 42、12 个 43 → 三组，27 个字节压到 6 个，压到 22%。 编码只需一趟扫描，解码照着次数重复即可——简单是它最大的优点。

30 秒实验

  1. 手写一串 AAAAABBBBCC 的游程编码结果，再想一遍解码过程。
  2. 想想一张全白的扫描件用游程编码能压到原来的多少。

常见误区

  1. 以为游程编码通用。它只认连续重复，换个数据就失效。
  2. 以为次数可以用任意大的数表示。次数本身也要占字节，得有个上限。
自测三问（点开对答案） 1. 游程编码的规则是什么？ —— 把连续重复的数据换成【那个字节 ＋ 重复次数】。 2. 它利用的是什么规律？ —— 数据里有长长的连续重复段。 3. 它为什么容易实现？ —— 只需记住【当前字节】和【连续几次】，一趟扫描即可完成编码。

相关笔记