6.2 Huffman 編碼與 heap 應用

動機

固定長度編碼為每個符號分配相同數目的 bit，做法簡單，卻沒有利用資料的頻率差異。若 a 佔一份檔案接近一半，而 f 只偶爾出現，兩者使用同樣長的 codeword 便會浪費空間。Huffman coding 結合 binary tree 與 min-priority queue，讓常見符號走較短的路徑，罕見符號則承擔較長的路徑。

分析時要分清三個問題。第一，建構：為何每輪都要合併目前頻率最小的兩棵 subtree。第二，可解碼性：可變長度 codeword 連在一起而沒有分隔符，為何仍可逐個還原。第三，成本：在指定頻率模型下，整段資料究竟需要多少 bit。只有一棵看似合理的樹而沒有這三項檢查，答案並不完整。

Heap 的同一種用法亦會出現在合併 k 條已排序 linked list。下一個輸出必定是各 list 當前 head 中的最小者；min-heap 只保存這些候選項，毋須每輸出一次便重新掃描全部 k 個 heads。兩個問題的共通點，都是維護一個規模較小、只含目前合資格最小項目的 frontier。

定義

每輪合併兩個 minimum

先為每個符號建立一個以頻率作 key 的 leaf，全部放進 min-heap。每輪 deleteMin 兩次，把兩棵 tree 接到一個新 internal node 之下；新 node 的權重是兩者之和，再把它 insert 回 heap。每次 merge 令 heap item 數量減一，所以 m 個 leaves 恰好需要 m - 1 次 merges。

HUFFMAN(symbols with positive weights)
    H = a min-heap containing one leaf per symbol
    while size(H) > 1
        x = deleteMin(H)
        y = deleteMin(H)
        z = a new internal node with weight x.weight + y.weight
        z.left = x
        z.right = y
        insert(H, z)
    return deleteMin(H)

把較輕的 x 放在左邊可令 trace 容易重現，但交換任何 internal node 的左右 children 仍然有效，只會改變 bit string，不會改變 codeword length 或儲存成本。若有相同權重，heap 的 tie-breaking 也可能產生不同而同樣合法的樹，所以 Huffman code table 並不一定唯一。

過程中的 invariant 是：heap 內每個 item 都是一棵 subtree 的 root；各 subtree 的 leaves 互不重疊，合起來恰好是整個 alphabet。Merge 只會以 union 取代兩個互不重疊部分，而新 root 的權重正是下方所有 leaves 的總權重。最後只剩一個 root 時，每個原符號都恰好出現一次。

若輸入長度為 N，掃描並統計 frequencies 需要 O(N)。把 m 個 leaves bottom-up 建成 heap 可用 O(m)；之後 m-1 輪各有兩次 deleteMin 和一次 insert，每項最多 O(log m)，所以建樹為 O(m log m)。遍歷最終 tree 記錄所有 codes 為 O(m)，完整 preprocessing 因而是 O(N + m log m)；若題目已給 frequency table，便不用 O(N) 掃描。Encoding 對每個輸入符號做一次 code-table lookup，另花與實際輸出 bit 數成比例的時間；decoding 則對讀取的 bit 數是線性。

若 alphabet 只有一個符號，merge loop 會得到單一 leaf 和空路徑。實際檔案格式通常約定用 0 表示該符號，令重複出現仍有明確表示。本節六符號例題毋須使用這個 edge case。

定理 / 命題

以上命題足以支持本節的 decoding 與數值核算。這個建構就是 Huffman greedy algorithm，但完整證明它在所有 binary prefix trees 中使 weighted length 最小，需要另一套 exchange argument，並不屬於本節課程來源所支持的範圍；以下推導不會假裝已完成該 optimality proof。

證明思路

第一個命題可用反證法理解。假設某 leaf code 是另一個 leaf code 的 prefix，沿較短 code 由 root 行走後已到達第一個 leaf，卻仍須沿更多 edges 才到第二個符號。Leaf 沒有 child，故不可能。這也解釋了為何 source symbols 必須放在 leaves，而不能放在 internal nodes。

解碼時由 root 開始逐 bit 行走。第一次到達 leaf 時，第一個符號已被強制決定：若提早停止，internal node 便要代表 code；若繼續走，該 leaf code 又會成為較長 code 的 prefix。輸出符號、回到 root，對餘下 codewords 重複即可。若 bit stream 結束時仍停在 internal node，它是截斷或無效資料，而不是另一種合法解碼。

要證明 merge-sum identity，觀察權重為 p 與 q 的兩個 roots 被接到新 parent 後，兩棵 subtree 內每個 leaf 的 depth 都增加一。因此 weighted length 的增加恰好是 p+q，也就是新 internal node 的權重。由 depth 全為零的獨立 leaves 開始，把每輪增量相加，就得到最終 weighted external path length。故 code-length sum 與 merge-weight sum 應相等，可用來偵測算術或 tree trace 錯誤。

對 k-way merge，invariant 是 heap 恰好保存每條非空 list 的第一個未輸出 element。因為每條 list 已排序，該 head 不大於同一 list 其餘未輸出 elements；所以 heap minimum 亦是全體剩餘元素的 global minimum。刪除它並把同一 list 的 successor 放回 heap，便恢復 invariant。

例題詳解

                           (100)
                         0 /   \ 1
                       a:45    (55)
                              0 /  \ 1
                              (25)  (30)
                             0/ \1  0/ \1
                          c:12 b:13 (14) d:16
                                    0/ \1
                                  f:5 e:9

MERGE_K_SORTED_LISTS(lists)
    H = empty min-heap
    for each nonempty list i
        insert(H, (lists[i].head.value, i, lists[i].head))
    output = empty list
    while H is not empty
        (value, i, node) = deleteMin(H)
        successor = node.next
        append value to output
        if successor exists
            insert(H, (successor.value, i, successor))
    return output

常見錯誤

• 合併兩個最大 weights，或只按原始 frequency list 繼續選擇。每輪都必須在目前 heap 中選兩個 minima，包括剛 insert 的 internal nodes。
• 由 leaf 向 root 倒讀 code。Code 是 root-to-leaf path，反轉後不是同一 bit string。
• 把 source symbol 放在 internal node。它的 code 便可能成為 descendant code 的 prefix，破壞無分隔符解碼。
• 斷言 frequency 較高者的 code 必定嚴格較短。Tie 或 tree shape 可令多個符號同長；真正長度由最終 tree 決定。
• 只數 codeword 數目而沒有計 weighted length；另要記住 224,000 bits 是 payload，未包括 tree/header overhead。
• 認為六個 symbols 可用兩個 fixed bits。2^2=4 只表示四種值，六個 symbols 必須用三個 bits。
• 把 k 條 list 的所有 elements 一次放入 heap。只有每條非空 list 的 current head 合資格，heap size 應不超過 k。

總結

Huffman construction 以 min-heap 反覆合併兩個 minimum-weight roots。原符號全在 leaves，因此 root-to-leaf codes 是 prefix-free，連續 codewords 亦可唯一解碼。六符號例題的 merges 是 5+9=14、12+13=25、14+16=30、25+30=55、45+55=100；碼長為 1,3,3,3,4,4，100,000-character payload 恰好使用 224,000 bits。相對指定的 8-bit ASCII 節省 576,000 bits，相對最短三-bit固定編碼節省 76,000 bits。

Heap 亦可合併 k 條 sorted lists。每條非空 list 只提供一個 current head，令 n 次輸出各以 O(log k) 找 global minimum，總時間 O(n log k)，額外空間 O(k)。

練習

1. 由 weights 5,9,12,13,16,45 開始，列出每次 Huffman merge，以及 insert 後 heap 餘下的 weights。
2. 使用完整建構中的 code table，解讀 11011100111，並標出 leaf boundaries。
3. 分別以 weighted code lengths 和 merge-sum identity 重算六符號 payload；再寫出相對 8-bit ASCII 與六符號最短 fixed-length code 的節省量。
4. 判斷 {0,01,11} 是否 prefix-free，並解釋 decoding 後果。
5. 為合併 k 條 sorted linked lists 寫出 heap 方法，說明 invariant、以總長度 n 表示的時間複雜度，以及 auxiliary space。

答案與解答