霍夫曼編碼 (Huffman Coding)#

霍夫曼編碼（Huffman Coding）是一種無損資料壓縮的編碼方式。它的迷人之處在於：用一個非常樸素的貪心策略——「每次合併頻率最低的兩個」——竟然就能得到理論上最優的編碼方案。

問題：如何用更少的位元儲存資料#

電腦裡的每個字元最終都要落實成 0 與 1。最直覺的做法是定長編碼：替每個字元分配固定位元數的編碼。

假設一份文件只用到 A、B、C、D 四個字元，定長編碼需要 2 個位元才能區分四種情況：

這樣每個字元都花 2 位元，無論它出現一次還是一萬次。但真實文件裡，字元出現的頻率天差地遠——英文裡 e 滿天飛，z 難得一見。定長編碼對這種差異視而不見，於是浪費了大量空間。

核心直覺：讓高頻字元用短碼、低頻字元用長碼，整份資料的總位元數就會縮短。出現越多次的字元，省下的位元就被放大越多倍。

舉例來說，若 A 出現 1000 次、D 只出現 5 次，那麼把短碼留給 A、長碼丟給 D，顯然比反過來划算得多。霍夫曼編碼正是把這個直覺做到極致。

前綴碼（prefix-free code）#

一旦改用「不定長」的編碼，就會冒出一個棘手問題：位元流裡並沒有分隔符，解碼時怎麼知道一個字元的編碼在哪裡結束、下一個從哪裡開始？

來看一個會出問題的反例。假設這樣分配編碼：

現在收到位元流 01，它到底代表什麼？

• 可以拆成 0 + 1，解出 AB；
• 也可以整段視為 01，解出 C。

同一串位元有兩種讀法，解碼器無從選擇——這個編碼是有歧義的。問題的根源在於：A 的編碼 0 恰好是 C 的編碼 01 的開頭。

歧義的禍首是「前綴重疊」。只要某個字元的編碼是另一個字元編碼的前綴，解碼時就會在分岔處猶豫不決。

解決辦法就是要求編碼具備前綴性質：任何字元的編碼，都不能是另一字元編碼的前綴。滿足這條件的編碼稱為前綴碼。

前綴碼有個漂亮的等價說法：把所有編碼放到一棵二元樹上，字元只能掛在葉節點。因為從根到任一葉的路徑都不會「經過」另一個葉，所以沒有任何編碼會是另一個的前綴。霍夫曼演算法建出來的，正是這樣一棵樹。

霍夫曼演算法（貪心建樹）#

霍夫曼的做法是自底向上地把字元一棵一棵地併成樹：

1. 把每個字元看成一個獨立節點，權重就是它的出現頻率，全部丟進一個優先佇列（最小堆）。
2. 反覆取出頻率最低的兩個節點，合併成一個新的內部節點，新節點的頻率是兩者之和，再把它放回佇列。
3. 重複到佇列裡只剩一個節點，它就是樹根。
4. 為每條邊標號：左分支標 0、右分支標 1。從根走到某個葉沿途收集到的 0/1 序列，就是該字元的編碼。

之所以用最小堆，是因為每一步都要快速找出「當前頻率最低的兩個」——這正是堆最擅長的事（見 堆）。

範例#

假設字元頻率如下：

建樹過程：

1. 取最低的 C(1) 與 D(1)，合併成 CD(2)。
2. 此時佇列有 B(2)、CD(2)、A(5)；取最低的 B(2) 與 CD(2)，合併成 BCD(4)。
3. 取剩下的 A(5) 與 BCD(4)，合併成樹根(9)。

最終的樹（左 0、右 1）：

flowchart TD
    R(("9")) -->|0| A(("A:5"))
    R -->|1| BCD(("4"))
    BCD -->|0| B(("B:2"))
    BCD -->|1| CD(("2"))
    CD -->|0| C(("C:1"))
    CD -->|1| D(("D:1"))

讀出每個字元的編碼：

注意最高頻的 A 只用 1 位元，最低頻的 C、D 才用 3 位元。總位元數為 $5 \times 1 + 2 \times 2 + 1 \times 3 + 1 \times 3 = 15$ 位元；若改用定長編碼（每字元 2 位元）則需 $9 \times 2 = 18$ 位元。

實作#

import java.util.PriorityQueue

// 樹節點：葉節點帶字元，內部節點只帶頻率
class Node(
    val freq: Int,
    val ch: Char? = null,
    val left: Node? = null,
    val right: Node? = null,
) {
    fun isLeaf(): Boolean = left == null && right == null
}

// 依頻率建出霍夫曼樹，回傳樹根
fun buildTree(freq: Map<Char, Int>): Node {
    // 最小堆：頻率小的優先取出
    // 比較器只看 freq，不會碰到 Node 本身，因此不必額外的 tie-breaker
    val heap = PriorityQueue<Node>(compareBy { it.freq })
    for ((ch, f) in freq) {
        heap.add(Node(f, ch))
    }

    // 反覆合併最低頻的兩個，直到只剩樹根
    while (heap.size > 1) {
        val a = heap.poll()
        val b = heap.poll()
        heap.add(Node(a.freq + b.freq, left = a, right = b))
    }
    return heap.poll()
}

// 從根 DFS 走到各葉，沿途累積 0/1 即為編碼
fun buildCodes(node: Node?, code: String, out: MutableMap<Char, String>) {
    if (node == null) return
    if (node.isLeaf()) {
        // 只有單一字元時給它預設碼 "0"
        out[node.ch!!] = code.ifEmpty { "0" }
        return
    }
    buildCodes(node.left, code + "0", out)
    buildCodes(node.right, code + "1", out)
}

fun main() {
    val freq = mapOf('A' to 5, 'B' to 2, 'C' to 1, 'D' to 1)

    val root = buildTree(freq)
    val codes = mutableMapOf<Char, String>()
    buildCodes(root, "", codes)

    for ((ch, code) in codes) {
        println("$ch -> $code")
    }
}

為什麼貪心在這裡能得到最優解#

貪心演算法常常只能得到「還不錯」的解，但霍夫曼編碼是少數貪心能保證全域最優的漂亮案例（見 貪心演算法原理）。

關鍵在於它的局部選擇——「合併當前頻率最低的兩個」——具備一個性質：這兩個最低頻的字元，一定可以安排成編碼最長、且互為兄弟的兩個葉。直覺上很合理：頻率最低的字元最該被分配最長的編碼（這樣總位元數最省），而把它倆湊成兄弟放到樹的最底層，正好實現了這一點。

更重要的是，把這兩個節點合併成一個新節點後，剩下的問題在結構上和原問題完全一樣，只是字元少了一個。於是「對縮小後的問題求最優」就能無縫拼回「對原問題求最優」——這正是貪心成立所需的最佳子結構。

換句話說，霍夫曼的每一次合併都「不會後悔」：當下選最低頻的兩個，絕不會讓未來吃虧。這種「局部最優累積成全域最優」的保證並不常見，也正是它區別於貪心湊零錢失敗案例的地方——後者一步貪心就斷送了最優解。

真實應用#

霍夫曼編碼並非紙上談兵，它藏在許多每天都會用到的格式裡，通常作為壓縮流程的「最後一道」熵編碼，與其他技巧串接使用：

• ZIP / gzip：DEFLATE 演算法先用 LZ77 找重複片段，再用霍夫曼編碼壓縮結果。
• JPEG：影像經過離散餘弦轉換與量化後，最後一步用霍夫曼編碼壓縮係數。
• MP3：音訊量化後的資料同樣以霍夫曼編碼進一步縮小體積。

它們的共同模式是：前面的步驟負責「找出資料裡的規律」，霍夫曼則負責「把已知頻率分布的符號壓到最省」。

小結#

霍夫曼編碼示範了演算法之美：一個極簡的貪心規則，配上恰到好處的資料結構（最小堆），就解決了一個看似困難的最優化問題。記住它的兩個支柱——前綴性質保證可解碼，最佳子結構保證最優。