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

莫尔斯码的妙处只有一条：最常出现的字母，码最短；哈夫曼做的就是把这条经验变成能自动算出来的方法。

📝 本节和前面几节的关系

6.3 的教训是【要找规律】，这一节去找一种更通用的规律：出现频率。

一、莫尔斯码的约定

莫尔斯码把每个字母写成点（.）和划（-）的组合。 有意思的是它的码长并不统一： E 只用一个点，因为它是英语里最常见的字母。 T 用一划，第二常见。 不常出现的字母码就长得多，比如 Q 是 --.-（四个符号）。

二、这条经验为什么成立

因为发报的时间是按符号数算的。 把短码留给高频字母，平均每个字母要发的符号数就下来了。 这不是凭感觉定的，是有人统计过英语里各字母的出现频率之后定下来的。 而且是编码者主动利用了数据的统计特性——这是它高明的地方。

三、算一笔账

拿一句话统计各字母的次数，再分别按两种方式算总符号数： 定长编码：字母 26 个，每个都得用 5 位，一共多少符号一目了然。 莫尔斯码：每个字母按各自的码长算，再按出现次数加权求和。 实测一句 39 个字母的话：定长要 195 个符号，莫尔斯只要 88 个——省了一半多。 省下来的全部来自那一条约定：谁常出现，谁短。

四、还差什么

莫尔斯码离哈夫曼只差最后也是最关键的一步： 莫尔斯码的码长是【人为定死】的——E 短、Q 长，是几十年前约定好的。 可数据换了呢？中文文章、程序代码、二进制文件，字母频率完全不同。 那能不能让程序自己去统计、自己去分配长短？ 1952 年，哈夫曼给出了答案——而且可以证明它是最优的（6.5、6.6）。

五、动手 Demo：从莫尔斯码中发现哈夫曼算法的基础

莫尔斯码有个很妙的约定：最常出现的字母，码最短。 统计一句话里各字母出现的次数，看看这个约定站不站得住。

from collections import Counter
text = "it was the best of times it was the worst of times"
cnt = Counter(c for c in text if c != " ")
for ch, k in cnt.most_common(6):
    print("%s 出现 %d 次" % (ch, k))
# 定长 5 位 对 莫尔斯码长
print("定长", len(text.replace(" ", "")) * 5)

实跑输出：

--------------------------------------------------------------------
从莫尔斯码中发现哈夫曼算法的基础
--------------------------------------------------------------------

莫尔斯码有个很妙的约定：**最常出现的字母，码最短。**
  E 是英语里最常见的字母，所以只用一个点（.）
  T 次常见，用一划（-）
  不常出现的字母码就长（比如 Q = --.-）

  统计一句话里各字母出现多少次（共 39 个字母）：

  字符     出现次数     占比      莫尔斯码     码长
  --------------------------------------------------
  t        8            20.5%     -            1
  s        6            15.4%     ...          3
  e        5            12.8%     .            1
  i        4            10.3%     ..           2
  w        3            7.7%      .--          3
  o        3            7.7%      ---          3

  把这两种编码各算一遍总符号数：

    定长编码（每个字母 5 个符号）  195 个符号
    莫尔斯码（高频用短码）        88 个符号
    省了                          55%

  **莫尔斯码没有别的技巧，只是把短码留给了高频字符。**
  哈夫曼在 1952 年做的，就是把这条经验**变成能自动算出来的方法。**

出现最多的 t 和次多的 e，在莫尔斯码里恰恰都只占 1 个符号。 定长编码要 195 个符号，莫尔斯码只要 88 个——短码给高频字符的威力。

30 秒实验

  1. 统计一段中文里最常出现的字，想一想它该不该给最短的编码。
  2. 查一查英文里出现频率最高的前五个字母分别是什么。

常见误区

  1. 以为莫尔斯码天生就不等长。它是按英语的频率约定出来的。
  2. 以为这个思路只能用于文字。任何有频率差的数据都能用。
自测三问（点开对答案） 1. 莫尔斯码最妙的一条约定是什么？ —— 最常出现的字母给最短的码，比如 E 只用一个点。 2. 这条约定为什么能省时间？ —— 发报时间按符号数算，短码留给高频字母能压低平均符号数。 3. 莫尔斯码还差哪一步才是哈夫曼？ —— 码长是人为约定的；哈夫曼让程序根据数据自己统计频率、自己分配长短码。

相关笔记