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

把每个字符当成一棵小树，反复挑权值最小的两棵合成一棵；最后从根走到字符，路上的 0 和 1 就是它的编码。

📝 本节和前面几节的关系

6.4 有了思路（短码给高频），这一节给出让程序自己算的方法。

一、为什么用树

长短码有个必须解决的问题：解码的人怎么知道一个码在哪里结束？ 如果只是随便给长短不一的 0 和 1，读起来会分不清边界。 树天然解决这件事：每个字符都是树的叶子，从根到叶子的路径就是它的码。 因为路径不会走到一半就变成另一个叶子，所以谁也不可能是别人的开头。

二、构建过程只有两句话

一、把每个字符当成一棵只有一个节点的树，权值就是它出现的次数。 二、反复挑出权值最小的两棵，合成一棵新树——权值相加，小的当左孩子（写 0）、大的当右孩子（写 1）。 重复第二步，直到只剩一棵树——这棵就是哈夫曼树。 小的先被挑走意味着它们离根更远，码更长；权值大的留在后面，自然就靠近根、码更短。

三、前缀码：为什么不用分隔符

从上面的构建过程能推出一条关键性质：任何编码都不是另一个编码的开头。 这叫做前缀码。 因为所有字符都在叶子上，而叶子没有孩子——走到一个叶子就必然结束，不可能既是终点又是中途。 有了前缀码，解码时一路顺着 0 和 1 往下走，走到叶子就输出一个字符、再回根重来，根本不用分隔符。

四、编码表怎么读出来

从树根出发，往左走记 0、往右走记 1，走到那个字符所在的叶子——记下的这串 0 和 1 就是它的编码。 实测一句话（105 个字符）：出现 23 次的空格只分到 2 位，出现 1 次的字母要 7 位。 而且这件事全由数据自己算出来，不需要人来判断谁常谁不常。 这就是 6.4 留下的那个问题，被一棵树解决了。

五、动手 Demo：使用树来构建哈夫曼编码

哈夫曼的做法只有两步：把每个字符当成一棵小树；反复挑最小的两棵合成一棵。 合成到最后只剩一棵，从根走到字符，路上的 0 和 1 就是编码。

import heapq
from collections import Counter

def build(text):
    cnt = Counter(text)
    heap = []
    for sym, w in cnt.items():
        heap.append([w, [sym, ""]])
    heapq.heapify(heap)
    while len(heap) > 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)
        for pair in lo[1:]:
            pair[1] = "0" + pair[1]
        for pair in hi[1:]:
            pair[1] = "1" + pair[1]
        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    return cnt, heapq.heappop(heap)[1:]

实跑输出：

--------------------------------------------------------------------
使用树来构建哈夫曼编码
--------------------------------------------------------------------

哈夫曼的做法只有两步：
  **一、把每个字符当成一棵只有一个节点的树，权值就是它的出现次数。**
  **二、反复挑出权值最小的两棵树，合成一棵新树**（小的当左孩子写 0、大的写 1）

  合到最后只剩一棵树——**从树根走到某个字符，路上写的 0 和 1 就是它的编码。**

  拿一句话（105 个字符）跑一遍，得到的编码表：

  字符     出现次数     哈夫曼编码     码长
  ------------------------------------------
  空格     23           00             2
  s        12           100            3
  t        12           101            3
  h        5            0100           4
  a        6            0101           4
  w        6            0111           4
  i        8            1100           4
  o        8            1101           4
  e        10           1111           4
  m        3            01100          5
  f        5            11101          5
  r        1            011010         6

  **注意头尾的对比：**
    出现最多的 空格 只有 2 位；出现最少的 n    要 7 位。
  **这就是哈夫曼的核心：谁出现得多，谁就分到短码。**
  而这件事不用人来判断——**它是由数据自己算出来的。**

出现 23 次的空格只分到 2 位；出现 1 次的字母要 7 位——短码自动给了高频字符。 前缀码保证了解码不用分隔符：所有字符都在叶子上，走到叶子就结束。

30 秒实验

  1. 用 5 个字符、权值 1、1、2、3、5 手工建一棵哈夫曼树，写出各自的编码。
  2. 想一想为什么【权值最小的两棵先合并】能让高频字符靠近根部。

常见误区

  1. 以为要额外存分隔符。前缀码不需要分隔符。
  2. 把【权值最小的两棵先合】记成【最大的先合】。顺序搞反，短码会分给低频字符。
自测三问（点开对答案） 1. 哈夫曼树是怎么建出来的？ —— 每个字符先各自成树、权值为出现次数；反复取权值最小的两棵合并（权值相加），直到只剩一棵。 2. 什么叫做前缀码？ —— 任何一个编码都不是另一个编码的开头，所以解码时不需要分隔符。 3. 字符的编码是怎么定下来的？ —— 从根走到该字符所在的叶子，往左记 0、往右记 1，记下的串就是它的编码。

相关笔记