霍夫曼編碼 — 用最少 bit 說最多話

我們每天在網路上傳送圖片、音訊、文字，這些檔案在傳輸前幾乎都經過壓縮。壓縮到底是怎麼做到的？為什麼壓縮後的檔案可以還原成原本的樣子？

在上一篇關於 JPEG 壓縮的文章裡，我們提到了霍夫曼編碼是 JPEG 壓縮流程的最後一步，這篇文章想更深入地聊聊霍夫曼編碼本身。

頻率與編碼

假設你要傳送一段文字，裡頭只有四個字母：A、B、C、D。最直覺的做法是用固定長度的二進位編碼：

字元	編碼
A	00
B	01
C	10
D	11

每個字元 2 bits，清楚明瞭。但如果 A 出現了 1000 次，而 D 只出現 1 次呢？用一樣長的編碼來表示頻率差異這麼大的字元，總覺得有點浪費。

這就是霍夫曼編碼想解決的問題：

讓出現頻率高的字元用比較短的編碼，頻率低的用比較長的。

這個概念和摩斯電碼很像 — 英文中最常出現的字母 E 只用一個點 . 來表示，而不常出現的 Q 則要用 --.- 四個符號。

資訊量與熵

在討論壓縮之前，先來想一個問題：一個事件的「資訊量」到底該怎麼衡量？

假設有人告訴你「明天太陽會從東邊升起」，你不會覺得學到了什麼新東西 —— 這件事情幾乎是確定的。但如果有人說「明天會下冰雹」，你會非常驚訝，因為這件事發生的機率極低。

Claude Shannon 在 1948 年提出了資訊量的數學定義。一個發生機率為 $p$ 的事件，它的資訊量（information content）為：

I = -\log_2(p)

機率越低，資訊量越大。這很直覺 — 越意外的事情，帶來的資訊越多。一個訊息源的熵（entropy），就是所有符號的平均資訊量：

H = -\sum_{i} p_i \log_2(p_i)

熵告訴我們的是：對於這個訊息源，理論上每個符號平均最少需要多少 bits 來編碼。霍夫曼編碼的厲害之處在於，它可以非常接近這個理論下限。

霍夫曼編碼的演算法

David A. Huffman 在 1952 年提出了這個演算法。演算法本身相當好理解，實作起來也很簡單，但是效果驚人，一直到現在都能看到霍夫曼編碼的身影。

步驟

統計頻率：計算每個字元出現的次數
建立 Priority Queue：將所有字元按照頻率由小到大排列
反覆合併：取出頻率最小的兩個節點，合併為一個新節點（頻率為兩者之和），放回佇列
重複直到只剩一個：這個節點就是霍夫曼樹的根
產生編碼表：從根遍歷，往左走記 0，往右走記 1

實際走一遍

用字串 "aabbbcccc" 當例子：

Step 1 — 統計頻率：

a: 2, b: 3, c: 4

Step 2 — 取最小的兩個合併：

a(2) + b(3) → ab(5)

Step 3 — 再取最小的兩個：

c(4) + ab(5) → root(9)

最終的霍夫曼樹：

        (9)
       /   \
     0       1
    c(4)   (5)
           /   \
         0       1
        a(2)   b(3)

編碼表：

字元	編碼	長度
c	0	1
a	10	2
b	11	2

原始用 ASCII 編碼： $9 \times 8 = 72$ bits。霍夫曼編碼後： $4 \times 1 + 2 \times 2 + 3 \times 2 = 14$ bits。

為什麼霍夫曼編碼那麼好用

霍夫曼編碼是一種前綴碼（prefix code）。前綴碼的定義是：沒有任何一個編碼是另一個編碼的前綴。

舉例來說，如果 A = 0，B = 01，那麼當解碼器讀到 01 的時候，它不知道這是「A 後面接了個 1」還是「B」。

霍夫曼編碼保證不會發生這種情況，因為所有字元都在葉節點上 — 從根到任何葉節點的路徑，不會是另一條路徑的前綴，這個特性讓解析本身也非常簡單。在所有前綴碼中，霍夫曼編碼能產生最短的平均編碼長度。

程式碼實作

以下是 JavaScript 的實作：

function buildTree(freqMap) {
  const nodes = [...freqMap.entries()]
    .map(([char, freq]) => ({ char, freq, left: null, right: null }))

  while (nodes.length > 1) {
    nodes.sort((a, b) => a.freq - b.freq)
    const left = nodes.shift()
    const right = nodes.shift()
    nodes.push({
      char: null,
      freq: left.freq + right.freq,
      left,
      right,
    })
  }

  return nodes[0]
}

function buildCodeTable(node, prefix = '', table = {}) {
  if (node.char !== null) {
    table[node.char] = prefix || '0'
    return table
  }
  buildCodeTable(node.left, prefix + '0', table)
  buildCodeTable(node.right, prefix + '1', table)
  return table
}

buildTree 每次取出最小的兩個合併，直到只剩一個根節點。buildCodeTable 則是從根開始遞迴，每往左走一步加 0，往右走一步加 1。

解碼的過程也很直覺 — 從根節點開始，讀到 0 往左走，讀到 1 往右走，到達葉節點就輸出對應的字元，然後回到根繼續：

function decode(encoded, root) {
  let result = ''
  let current = root

  for (const bit of encoded) {
    current = bit === '0' ? current.left : current.right
    if (current.char !== null) {
      result += current.char
      current = root
    }
  }

  return result
}

互動：霍夫曼編碼器

試試看在下方輸入任意文字，即時觀察霍夫曼編碼的結果。你可以把滑鼠移到編碼表的某個字元上，在編碼結果中會高亮對應的 bits。

載入霍夫曼編碼器中…

試試看輸入不同的文字，觀察幾個有趣的現象：

輸入只有一種字元的文字（如 aaaa），每個字元只需要 1 bit
輸入所有字元頻率相同的文字，編碼長度會趨近於固定長度
輸入頻率差異越大的文字，壓縮率越高

霍夫曼編碼的限制

霍夫曼編碼並非萬能，有一些實務上的限制：

每個符號至少 1 bit。 即使某個字元的理論最佳編碼長度是 0.3 bits，霍夫曼編碼也只能分配至少 1 bit。這在某些極端分佈下會造成效率損失。

需要事先知道頻率。 編碼前要先掃描一遍資料才能統計頻率，或是使用預先定義好的頻率表。在 JPEG 中，標準就定義了預設的霍夫曼表，也允許自訂。

編碼表需要一起傳送。 解碼端需要知道編碼表才能還原資料，所以編碼表本身也佔空間。對於小資料來說，編碼表的 overhead 可能抵消壓縮的效益。

霍夫曼編碼在哪裡？

JPEG — 影像壓縮的最後一步就是霍夫曼編碼
DEFLATE（ZIP、gzip）— 結合 LZ77 與霍夫曼編碼
MP3 — 音訊壓縮中也使用了霍夫曼編碼
HTTP/2 — HPACK header 壓縮使用了靜態霍夫曼表

後記

霍夫曼編碼是那種「理解之後會覺得理所當然」的演算法。它的核心想法極其簡單 — 常見的東西用短的表示，罕見的東西用長的。但要把這個想法變成通用的演算法，就需要很多設計上的巧思。

七十多年過去了，這個演算法依然活躍在我們每天使用的各種格式裡。

不知道這些人有了 AI 輔助會變成什麼樣子呢？

文章分類

其他頁面

斜槓人生