通用資料壓縮演算法導論：從霍夫曼編碼到 LZ77/LZW 字典法

壓縮分類總覽

本文聚焦 通用無損壓縮，核心演算法演進：霍夫曼編碼 → LZ77 → LZ78 → LZW → DEFLATE (LZ77+霍夫曼)。

一、霍夫曼編碼：最優前綴碼

核心思想

出現機率高的符號分配短碼，低機率分配長碼；前綴碼 保證無歧義解碼 (無碼字是另一碼字前綴)。

建樹步驟

1. 統計各符號頻率 (或自適應動態統計)。
2. 建立葉節點放入最小堆 (優先佇列)。
3. 重複取出兩最小節點合併為新節點 (權重 = 兩者之和)，放回堆，直到剩一個根節點。
4. 從根向葉走訪：左 0、右 1，得到各符號編碼。

範例

符號:  A   B   C   D
頻率: 12   3   4   5
霍夫曼樹:
        root(24)
       /    \
     A(12)  @(12)
           /   \
        D(5)   @(7)
              /  \
           C(4)  B(3)

編碼: A=0, D=10, C=110, B=111
總位元: 12*1 + 5*2 + 4*3 + 3*3 = 43 bits
固定 2-bit 編碼需 48 bits → 壓縮 10%

二、LZ77：滑動視窗字典壓縮

核心概念

字典 = 已處理過的資料本身 (滑動視窗)，無需外部字典。尋找「當前位置前方視窗內」最長匹配，輸出 <相對位移, 匹配長度>；找不到則輸出原始字面值。

實例逐步演示

輸入: AABAABAAB
視窗大小: 4096 (12-bit 位移), 最大匹配長 16 (4-bit 長度)

步驟 1: 輸入 AABAABAAB, 字典=空 → 輸出 'A'
步驟 2: 輸入 ABAABAAB, 字典=A     → 輸出 'A'
步驟 3: 輸入 BAABAAB, 字典=AA    → 找到 'A' 位移 1 長 1 → 輸出 <0,1>
步驟 4: 輸入 AABAAB, 字典=AAB    → 輸出 'B'
步驟 5: 輸入 ABAAB, 字典=AABAAB  → 找到 'AAB' 位移 3 長 3 → 輸出 <0,3>
... 以此類推

關鍵點:
- 最小匹配長度通常設 3 (因 <位移,長度> 本身佔 2 bytes，<3 不划算)
- 位移 12-bit → 4KB 視窗；長度 4-bit → 最大 16 bytes
- 解壓時需 1-bit 標誌區分「字面值」vs「匹配碼」

三、LZW：動態字典編號法

LZ77 輸出 <位移,長度>，LZW 改為 字典索引：

1. 初始字典 = 所有單字元 (0~255)。
2. 讀取輸入，尋找「已在字典中」的最長字串 W。
3. 輸出 W 的索引，將 W + 下一字元 加入字典。
4. 字典動態增長，編碼端/解碼端同步重建，無需傳輸字典。

GIF、Unix compress、早期 ZIP 皆採 LZW 變體。

四、現代標準：DEFLATE (ZIP/GZIP/PNG 核心)

DEFLATE = LZ77 (滑動視窗 32KB) + 霍夫曼編碼

• LZ77 產出「字面值/長度/距離」三類符號。
• 對這三類符號分別建立霍夫曼樹 (動態/靜態區塊)。
• 區塊獨立壓縮，支援非壓縮區塊 (不可壓縮資料)。

zlib / libdeflate / Java java.util.zip 皆為 DEFLATE 實作。

五、壓縮比與速度權衡表

六、J2ME 環境下的壓縮策略

• JAR 本身已 DEFLATE：類別、資源檔打包時自動壓縮，無需再壓。
• 網路傳輸：HTTP Accept-Encoding: gzip，伺服器端壓縮，客戶端 GZIPInputStream 解壓 (MIDP 2.0+ 支援)。
• 自訂資料：若需本地壓縮 (如遊戲存檔)，建議實作極簡 LZ77 (固定 2KB 視窗、無霍夫曼)，約 2KB 代碼、< 1KB RAM，足以應付結構化資料 50%+ 壓縮率。
• 避免：LZMA、BZIP2 等大字典演算法，RAM/CPU 完全不足。

結語

理解「編碼優化 (霍夫曼) + 字典替換 (LZ77/LZW)」雙引擎架構，即可看透 ZIP/GZIP/PNG/DEFLATE 等主流格式本質。在資源受限環境 (J2ME、嵌入式)，選擇「定長視窗 LZ77 + 位元打包」自製輕量壓縮，往往比移植通用庫更務實。