第6章 文字壓縮二：字典式壓縮#

統計式壓縮（第5章）問的是「每個符號的機率是多少」；字典式壓縮問的是「哪段字串剛剛出現過」。1977 與 1978 年，Abraham Lempel 與 Jacob Ziv 發表兩篇論文，開創了 LZ77 與 LZ78 兩大路線：前者用滑動視窗，把「往回找相同片段」化為一對數字（距離、長度）；後者動態建立字典，把重複片段化為字典索引。它們不依賴任何先驗機率模型，卻能漸近達到熵極限（Ziv-Lempel 定理），且對「重複多的資料」效果極佳——這正是程式碼、HTML、文件與遊戲貼圖的共性。

本章路線：6.1 節講 LZ77 與 LZ78 的原理與實作；6.2 節講 LZ78 的實用化後裔 LZW 與它驅動的 GIF 格式（以及 Unisys 專利風波如何改寫歷史）；6.3 節講 DEFLATE——LZ77 與 Huffman 的合體，也就是 zip、gzip、PNG 共同的核心，兼談 zstd、LZ4 等現代變體。

學完本章，讀者應能解釋「為什麼 zip 壓縮過的檔案再壓一次幾乎不變」、看懂 gzip 的兩層結構，並理解壓縮與前一章熵理論在 LZ77 上的漂亮會合：滑動視窗的匹配長度分布本身就能用算術編碼進一步壓縮。