> huffman | 最佳 | 編碼 <
// Huffman 編碼——最佳前綴碼壓縮演算法
最佳碼長
在給定的頻率分佈下，產生平均碼長最短的前綴碼。
前綴自由
任一碼字都不是其他碼字的前綴，確保解碼時不會產生歧義。
依頻率調整
出現頻率越高的字元自動獲得越短的碼字，提升整體壓縮效率。
>> 技術細節
Huffman 編碼的運作原理:
Huffman 編碼會自底向上建立一棵二元樹。演算法從各個字元的出現頻率開始，重複將頻率最低的兩個節點合併成一個父節點，直到只剩下根節點為止。走向左子樹代表 '0'，走向右子樹代表 '1'。頻率越高的字元越靠近根節點，因此可以使用更短的碼字，進而在給定的頻率分佈下達成最優無失真壓縮。
Huffman 編碼範例:
Text: "AABBBCCCC"
Frequencies:
A: 2
B: 3
C: 4
Tree Building:
1. Combine A(2) + B(3) = AB(5)
2. Combine C(4) + AB(5) = Root(9)
Tree:
Root(9)
/ \
C(4) AB(5)
/ \
A(2) B(3)
Codes:
C: 0
A: 10
B: 11
Encoded: 10 10 11 11 11 0 0 0 0
= 1010111111 0000
為什麼要使用 Huffman 編碼？:
- ▸接近資訊理論極限的壓縮率
- ▸實作相對簡單，容易整合進專案
- ▸是 ZIP／JPEG 等格式中的關鍵元件
- ▸無失真壓縮，不會遺失任何資料
- ▸在實際生產環境中已被長期驗證
>> 常見問題
什麼是 Huffman 編碼？
Huffman 編碼是一種最優前綴碼的無失真壓縮演算法，由 David A. Huffman 在 1952 年提出。它根據字元出現的頻率指派長度不同的位元串，頻率越高的字元使用越短的碼字，以此將平均碼長降到最低。
為什麼稱為「前綴碼」或「前綴自由」？
前綴碼指的是任何一個碼字都不會是其他碼字的前綴。例如，如果字元 A 的碼字是 "01"，那麼其他字元的碼字就不能以 "01" 開頭。藉由這個性質，只要從左到右讀取位元流，就能在沒有額外分隔符的情況下唯一地還原出每一個碼字。
Huffman 編碼的壓縮效果如何？
對於給定的頻率分佈，Huffman 編碼可以達到非常接近理論熵極限的最優壓縮，通常誤差在 1 個 bit 以內。對英文文字來說，常見的壓縮率約為 60–70%，當字元頻率差異越大時效果越顯著。
Huffman 編碼一般用在哪些地方？
Huffman 編碼廣泛用於 JPEG 影像壓縮、ZIP 檔案壓縮（在 DEFLATE 中與 LZ77 搭配）、MP3 音訊以及許多其他格式。實務上通常會與其他演算法一起使用，例如 JPEG 在 DCT 與量化後使用 Huffman，而 ZIP 則在 LZ77 之後再進行 Huffman 編碼。
// 計算範例
| Symbol | Freq | Bits | Code |
|---|---|---|---|
| A | 4 | 1 | 0 |
| B | 2 | 2 | 10 |
| C | 1 | 2 | 11 |
// 程式碼範例
Input AAAABBC (7 symbols, 56 bits as 8-bit ASCII) Counts A=4 B=2 C=1 Merge C(1)+B(2) -> node(3); node(3)+A(4) -> root(7) Codes A=0 B=10 C=11 (0/1 on left/right branches; ties may swap) Encoded 0 0 0 0 10 10 11 = 4*1 + 2*2 + 1*2 = 10 bits
>> 更多問題
問：霍夫曼編碼是唯一的嗎？
答：不一定。頻率相同時，節點的選擇和 0/1 的分配可能不同。但任何正確的霍夫曼樹，其碼長與總長度都是最佳且相同的。
問：「前綴碼」是什麼意思？
答：任何碼字都不是另一個碼字的開頭。因此無需分隔符即可解碼：從根出發沿位元走到葉子即得一個符號。
問：霍夫曼編碼什麼時候不是最佳？
答：它為每個符號分配整數個位元，機率極度偏斜時（如 0.99）效率下降；算術編碼更接近熵。解碼端還需要碼表。