6.3 Deflate與zip的原理#

概念說明#

DEFLATE（Phil Katz, 1993，PKZIP 2.0 與 RFC 1951）是 LZ77（實為 LZSS）＋Huffman 的兩層合體，至今仍是 zip、gzip、PNG、Java JAR、HTTP compression 的基礎。設計哲學：第一層（LZSS）處理重複，第二層（Huffman）處理偏斜——兩種冗餘各由最擅長的機制吃掉。

第一層：在 32 KB 滑動視窗內找最長匹配。為了速度，gzip 用雜湊鏈：把每個 3-byte 串雜湊到桶，桶內是「最近出現位置」的鏈表，匹配時沿鏈找，命中即貪婪輸出；還有「懶惰匹配」策略——當前匹配若比下一位置的短，就改輸出字面值，讓下一位置用更長匹配，實測提升壓縮率。輸出兩種 token：字面值/長度（0–255 為字面值，256–285 為長度碼 3–258）與距離（0–29 為距離碼，對應 1–32768 的非均勻編碼）。長度與距離都用「範圍碼＋額外位元」編碼，減少符號數。

第二層：對 token 流做 Huffman 編碼，而且三套表並用——字面/長度一套、距離一套、（動態模式下）碼長本身再用一套「碼長的碼長」壓縮。這是 DEFLATE 精髓：連描述壓縮規則的資料也壓縮。碼表有兩種模式：固定表（small block 免傳表）與動態表（先送規範式 Huffman 碼長序列，用 RLE＋第 19 個碼長符號壓縮）。實作使用 規範式 Huffman（canonical Huffman）：只存碼長，碼本身由「長度排序、逐碼 +1」的確定規則重建，節省大量檔頭。

容器層：zip 是檔案容器——每個檔案獨立 DEFLATE 壓縮（local file header + compressed data + central directory），支援隨機存取單檔解壓；gzip 是單流容器（RFC 1952：10-byte 檔頭 + DEFLATE 資料 + CRC32/ISIZE 尾）；PNG 把 DEFLATE 包在 zlib 流（RFC 1950）裡再按掃描線過濾。CRC32 在尾端做完整性驗證（注意：是完整性不是安全性，需 SHA 系列才防竄改）。

極限與後繼者：DEFLATE 約在「速度—壓縮率」曲線的中間。LZMA（7z/xz）用更大的字典與區間編碼，壓縮率高但慢；LZ4 犧牲壓縮率換極速（解壓 GB/s 級）；Zstandard（zstd） 以 FSE（ANS 系熵編碼）＋改良 LZ 取代 Huffman，多級壓縮等級兼顧兩端，是當今推薦的預設；Brotli 針對 HTTP 內建字典（常見詞預載），網頁傳輸略優於 gzip。理解 DEFLATE 後，這些後繼者的差異只是「每個組件換更好的版本」。

演算法步驟#

對輸入做 LZSS：雜湊鏈找視窗內最長匹配（長度 3–258），貪婪＋懶惰輸出 token 流。
統計 token 頻率，為「字面/長度」與「距離」各建規範式 Huffman 碼（碼長 ≤ 15）。
動態模式下，把兩套碼長序列做 RLE，用第三套 Huffman 編碼後置於塊頭。
依 32768-byte 塊（BTYPE=01 固定表 / 10 動態表）序列化：塊頭 →（動態：碼表）→ token 位元流。
最後一塊 BFINAL=1；解壓反向：讀塊頭、重建碼表、Huffman 解碼 token、依 (d,L) 從已輸出緩衝區複製（允許重疊）、字面值直接輸出。

Python 程式碼範例#

import zlib, time
from collections import Counter

raw = open(__file__, "rb").read() if False else (
    b"DEFLATE combines LZ77 matching with Huffman coding. " * 300)

# 1) 純 zlib（= DEFLATE + zlib 容器）
t0 = time.perf_counter()
z = zlib.compress(raw, 9)
t1 = time.perf_counter()
print(f"原始 {len(raw)} B -> 壓縮 {len(z)} B "
      f"({len(z)/len(raw):.1%}), {len(zlib.decompress(z)) == len(raw)} 還原成功")

# 2) 壓縮過的資料再壓一次：幾乎不變 => 冗餘已被吃完
z2 = zlib.compress(z, 9)
print(f"二次壓縮: {len(z2)} B ({len(z2)/len(z):.1%})")

# 3) 觀察 DEFLATE 的兩層性：先手動 LZSS 風格去重，再壓縮效果差異
lines = raw.split(b"DEFLATE")[1:]
z3 = zlib.compress(b"".join(lines[:5]), 9)
print("小樣本壓縮率:", f"{len(z3)/len(b''.join(lines[:5])):.1%}",
      "（樣本越小，Huffman 檔頭開銷占比越大）")

# 4) 壓縮等級 1..9 的時間-空間權衡
for lvl in (1, 6, 9):
    t0 = time.perf_counter()
    c = zlib.compress(raw, lvl)
    dt = time.perf_counter() - t0
    print(f"level {lvl}: {len(c):6d} B, {dt*1000:6.2f} ms")

複雜度分析#

壓縮：LZSS 雜湊鏈版本近 O(n×k)（k = 沿鏈搜尋上限，gzip 預設 128，等級越高越大）；Huffman 建表 O(|Σ| log|Σ|)；整體gzip -1~ -9 覆蓋從線性到數倍線性。
解壓：O(n)——每 token 常數工作，Huffman 解碼可用查表法每步 O(1)；這是「壓一次、解多次」場景（下載、軟體發布）的理想性質。
空間：視窗 32 KB＋雜湊鏈表，僅數百 KB——DEFLATE 在 1990 年代的機器上就能跑，是它長盛的原因之一。
壓縮率量尺：英文文本約 35–40%、重複性 XML/JSON 可達 20% 以下、已壓縮資料（JPEG、zip）≈100%——冗餘守恆，二次壓縮無利可圖。

練習#

用 zlib.compressobj 的 strategy=zlib.Z_FIXED（固定 Huffman 表）與預設動態表壓同一檔案，量化「動態碼表」帶來的增益；再對很小（50 B）的輸入重做，觀察碼表開銷何時反噬。
實作規範式 Huffman：輸入碼長表（如 3×2, 4×1, 5×2, …），依 DEFLATE 規則生成實際碼，驗證「同長度連續、長度 +1 時左移一位」的性質。
比較 zlib（DEFLATE）、lz4.block、zstandard（若可安裝）在 1 MB 文本上的壓縮率、壓縮時間、解壓時間，畫出「時間—空間」散布圖，指出三者在曲線上的位置與適用場景。