Gzip/Zlib/PNG 核心壓縮算法 Deflate 源碼級深度解析

基於 gzip-1.2.4 源碼，從 LZ77 + Huffman 雙階段原理到滑動窗口、哈希鏈、延遲匹配的工程化實現

1. Deflate 雙階段壓縮管線

原始數據
    │
    ▼
┌─────────┐     LZ77 編碼 (滑動窗口 + 重複串替換)
│  LZ77   │ ──────────────────► 字面量 + <長度,距離> 對
└─────────┘
    │
    ▼
┌──────────┐    Huffman 編碼 (最優前綴碼)
│ Huffman  │ ──────────────────► 位流
└──────────┘
    │
    ▼
壓縮數據 (zlib/gzip/PNG 封裝格式)

2. LZ77 滑動窗口機制 (gzip 核心)

2.1 窗口結構

• 窗口大小：32KB (gzip 默認)，循環緩衝區 window[32768]。
• 指針：strstart 指向當前待編碼位置，lookahead 為可用數據長度。
• 最小匹配長：MIN_MATCH = 3。因 <長度,距離> 對需 23 位 (長度 8 位 + 距離 15 位)，3 字節 = 24 位，始有壓縮收益。

2.2 哈希鏈加速匹配查找

核心數據結構：

// 全局靜態數組
ush *head;   // head[hash] = 最新匹配該哈希值的窗口位置 (鏈表頭)
Pos *prev;   // prev[window_pos] = 同哈希值的前一個位置 (鏈表節點)

哈希函數 (取窗口前 3 字節)：

#define H_SHIFT  ((HASH_BITS + MIN_MATCH - 1) / MIN_MATCH) // 5
#define HASH(h, c) (((h) << H_SHIFT) ^ (c)) & HASH_MASK

// 初始化
ins_h = 0;
for (i = 0; i < MIN_MATCH - 1; i++) 
    UPDATE_HASH(ins_h, window[i]); // 預計算前 2 字節哈希

// 主循環每步
UPDATE_HASH(ins_h, window[strstart + MIN_MATCH - 1]); // 納入第 3 字節
prev[strstart & WMASK] = head[ins_h]; // 入鏈
head[ins_h] = strstart;               // 更新鏈頭

查找最長匹配：

match = head[ins_h]; // 最新候選
best_len = 0;
while (match != NIL && strstart - match <= MAX_DIST) {
    // 比較 window[strstart...] 與 window[match...]
    if (window[match + best_len] == window[strstart + best_len]) {
        // 延伸匹配...
    }
    match = prev[match & WMASK]; // 遍歷鏈表
}

2.3 延遲匹配策略

發現匹配後不立即輸出，而是嘗試 strstart+1 位置的匹配：

if (best_len >= MIN_MATCH) {
    // 保存當前匹配
    match_length = best_len;
    match_start = match;
    
    // 前瞻一步
    strstart++; lookahead--;
    UPDATE_HASH(ins_h, window[strstart + MIN_MATCH - 1]);
    // 再次查找...
    if (new_best_len > match_length) {
        // 新匹配更長，輸出字面量 window[strstart-1]，採用新匹配
    } else {
        // 原匹配更優，輸出 <長度,距離>
    }
}

效果：避免「貪婪匹配」導致錯過更長匹配，提升壓縮率 ~2-3%。

3. Huffman 編碼實現

3.1 兩棵樹：字面量/長度樹 + 距離樹

• 字面量/長度樹：256 字面量 (0-255) + 29 長度符號 (257-285) + 1 結束符 (256) = 286 符號。
• 距離樹：30 距離符號 (0-29)。

3.2 動態樹構建流程

1. 統計頻率：掃描 LZ77 輸出序列，累計各符號出現次數 dyn_ltree[], dyn_dtree[]。
2. 構建最優樹：gen_bitlen 計算各符號編碼長度，gen_codes 生成標準 Huffman 碼 (按長度排序賦碼)。
3. 生成壓縮樹描述：將樹結構本身壓縮輸出 (用預定義順序傳遞編碼長度，再用另一層 Huffman 編碼)。

3.3 位流輸出

// 位級寫入緩衝區
ulg bi_buf;  // 32 位緩衝器
int bi_valid; // 有效位數

void send_bits(int code, int len) {
    bi_buf |= (code << bi_valid);
    bi_valid += len;
    while (bi_valid >= 8) {
        put_byte(bi_buf & 0xff);
        bi_buf >>= 8;
        bi_valid -= 8;
    }
}

4. gzip 源碼關鍵入口流程

main()
  → treat_file()           // 打開文件
    → zip()                // 壓縮入口
      → bi_init()          // 位流初始化
      → ct_init()          // Huffman 樹初始化 (靜態/動態)
      → lm_init()          // LZ77 初始化 (head 清零, strstart=0, 預讀 2 字節)
      → deflate()          // 核心壓縮循環
        → longest_match()  // 哈希鏈查找最長匹配
        → ct_tally()       // 統計符號頻率 / 輸出字面量或 
        → flush_block()    // 塊滿時構建動態樹並輸出
      → bi_windup()        // 刷新剩餘位
      → put_bytes()        // 輸出 gzip 尾部 CRC-32 + 原始長度

5. 關鍵優化技巧總結

6. 從源碼學習的建議路徑

1. 下載 gzip-1.2.4.tar.gz，閱讀 deflate.c、trees.c、bits.c。
2. 在 deflate() 主循環設置斷點，觀察 strstart、match_length、bi_buf 變化。
3. 修改 MIN_MATCH 為 2/4，觀察壓縮率與速度變化。
4. 對比 zlib (deflate.c 同源) 的 compress()/uncompress() 封裝層。
5. 研究 PNG 如何在 IDAT chunk 中使用 zlib 流 (濾波器 + Deflate)。

Deflate 是「理論優雅、工程極致」的經典之作，深入其源碼是理解無損壓縮、流式編碼、位級操作的最佳教材。