一、四种算法的账

拿同一句话（105 个字符、17 种不同字符）算四种表示方式的位数： 原样：每字符 1 字节 = 8 位，共 840 位（这是 100%）。 定长编码：17 种字符至少用 5 位，共 525 位（62%）——比原样省，但没利用频率。 游程编码：这句话没有可压缩的连续重复，反而涨到 1680 位（200%）。 哈夫曼编码：共 376 位（45%）——最大赢家。

二、为什么它是最优的

哈夫曼有个正式的名号：最优前缀编码。 意思是：在【每个字符独立编码、且必须构成前缀码】这个框框里，它给出的总位数最少。 直观理解也不难：算法每步都把两个最小的合并，等价于让【最不常出现的】沉到最深的地方。 所以它不是【一种还不错的办法】，而是这一框架下的天花板。

三、天花板在哪儿：信息熵

那这个框架本身的天花板又在哪儿？信息论给了一个数：信息熵。 熵算的是【这段数据平均每个字符携带多少信息】，也是任何无损压缩都不可能越过的下限。 实测那句话：平均熵 3.55 位/字符，理论下限约 373 位。 哈夫曼用了 376 位——只比下限多 3 位。 通常哈夫曼的结果会在【熵】和【熵＋1 位】之间，这就是它被认为已经压到底了的原因。

四、它也不是没有代价

要额外存编码表。 解码的人得知道每个码对应哪个字符，文件越小编码表的占比越重。 要先把数据全看一遍才能统计频率。 流式数据（比如直播）就不好办，得改用自适应变体。 数据太短反而不划算。 一段十几个字符的文本，编码表的开销比省下来的还多。 所以要再往下压，只能换思路——不再一个字符一个字符地编，这就进入了有损压缩的地盘（6.7）。

五、动手 Demo：通过哈夫曼算法大幅提高压缩效率

同一句话，四种表示方式的位数对比。 哈夫曼的结果已经贴着信息熵给出的理论下限。

cnt, codes = build(text)
n = len(text)
print("原样    ", n * 8)
print("定长    ", n * 5)
print("哈夫曼  ", sum(cnt[c] * len(k) for c, k in codes))
ent = -sum((v / n) * math.log2(v / n) for v in cnt.values())
print("信息熵下限", round(ent * n))

实跑输出：

--------------------------------------------------------------------
通过哈夫曼算法大幅提高压缩效率
--------------------------------------------------------------------

  同一句话，四种算法的账：

  表示方式                           位数     相对原样
  -----------------------------------------------------
  原样（每字符 1 字节 = 8 位）       840      100%
  定长编码（17 种字符，5 位）        525      62%
  游程编码（本句无可压缩的重复）     1680     200%
  哈夫曼编码                         376      45%

  信息论里有个下限：**任何无损压缩都不可能压到【信息熵】以下。**
  这句话 105 个字符，平均信息熵 3.55 位/字符，理论下限约 373 位。
  哈夫曼编码用了 376 位——**已经贴着这个下限了。**

  **所以哈夫曼被称为【最优前缀编码】：在同一套【按字符独立编码】的框架里，**
  它已经做到最好，压不下去了。
  想再往下压，只能换思路：**不再一个字符一个字符地编**——那是有损压缩的地盘。

840 位 → 525 位（定长 62%）→ 376 位（哈夫曼 45%）。 信息熵下限约 373 位，哈夫曼 376 位——只多 3 位，已经压到底了。

30 秒实验

1. 把句子换成一篇文章，重新算一遍哈夫曼的压缩率，看是否更低。
2. 想想为什么文件只有十几个字符时，哈夫曼反而不划算。

常见误区

1. 以为哈夫曼可以无限压。它受信息熵限制，压不过下限。
2. 忘了编码表也要占地方。文件越小编码表的开销占比越大。

• ☐ 下一节（6.7 无损压缩与有损压缩）

相关笔记

• 使用树来构建哈夫曼编码 — 编码表是怎么来的
• 无损压缩与有损压缩 — 压不下去之后怎么办
• 游程编码的缺点 — 换个角度看那 200%
• 🔵 计算机基础 · 索引 — 硬件底层的入门课
• ⚙️ 程序是怎样跑起来的 · 索引