Huffman 編碼 | 最佳前綴碼壓縮

>> 功能特色

[OPTIMAL]

最佳碼長

在給定的頻率分佈下，產生平均碼長最短的前綴碼。

[PREFIX-FREE]

前綴自由

任一碼字都不是其他碼字的前綴，確保解碼時不會產生歧義。

[ADAPTIVE]

依頻率調整

出現頻率越高的字元自動獲得越短的碼字，提升整體壓縮效率。

>> 技術細節

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 編碼。

[Base64.sh]

> huffman | 最佳 | 編碼 <