gzip 當作語言模型：DEFLATE 如何生成文字

gzip 可以作為語言模型，但僅限於有限且雜訊較多的方式

重點： 透過將候選延伸的壓縮大小視為其機率的代理指標，gzip 背後的 DEFLATE 算法可透過束搜尋（beam search）生成文字，展現了壓縮與預測之間的等價性，儘管輸出仍遠不如神經語言模型那般連貫。

壓縮即預測

每一個壓縮器都隱含地定義了一個機率分佈。

資訊理論告訴我們，符號的最佳碼長為 \-\log_2 p
，其中 $p$ 是模型所分配的機率。壓縮器對某個符號使用較少位元，表示它假設該符號的機率較高。gzip 使用 DEFLATE 算法，維持一個 32 KiB 的滑動窗格，並將重複的字節序列以反向引用取代。當某個延續與近期字節相似時，DEFLATE 會幾乎不增加額外位元來編碼它，這意味著壓縮器「預期」了該延續。

評分規則：

score(candidate) = len(gzip(context + candidate))

較短的壓縮長度代表較高的預測機率。透過用大型語料庫（例如 tiny Shakespeare）預先初始化壓縮器，任何與語料庫相似的延續都會獲得較低的分數。

使用束搜尋生成文字

一種天真的貪心方法——選擇使壓縮長度最小的下一個字節——會失敗，因為 gzip 只報告整數位元長度。加入單一字節通常不會改變壓縮大小，導致大量平局和雜訊梯度。

束搜尋解決方案：

  1. 提示（Prompt） – 用戶提供的提示會與語料庫窗格串接，並視為初始上下文的一部分。
  2. 上下文（Context） – 每次搜尋步驟中，gzip 看到的是 corpus_window + recent_tail，其中 recent_tail 是已生成輸出的最後 tail 個字節。
  3. 擴展（Expand） – 每個束候選會由語料庫中出現的每個字節進行擴展。所有擴展均以壓縮長度規則進行評分。
  4. 修剪（Prune） – 僅保留最頂尖的 beam_width 候選（最具壓縮性的）。重複此過程固定 horizon 個字節。
  5. 確認（Commit） – 輸出最佳完整片段（或根據溫度參數比例採樣），並向前滑動窗格。

將上下文限制在最近的 tail 個字節，可防止模型陷入只複製自身近期輸出的平凡循環，因為 DEFLATE 給較近的匹配提供更便宜的編碼。

生成輸出的樣貌

在 tiny Shakespeare 語料庫上運行工具 gzipt，提示為 "MENENIUS:\n"，產生如下結果：

MENENIUS:
'Though all at once canq

MARCIUS:
Pray now, nocamest thou to a morsel .

LARTIUS:
Hence, and
I' the end admire, where G
again; and after it ag .

文字並非流暢的莎士比亞風格，但明顯重用了來源中的片段與標點模式，證實 gzip 的壓縮模型確實捕捉到了語料庫的一些統計規律。

其他壓縮器的行為

作者也試驗了 bzip2 和 Zstandard (zstd)：

  • bzip2 – 產生長串交替符號（例如 xyxyxy…）。這反映出其依賴 Burrows‑Wheeler Transform，偏好高度重複的模式而非有意義的語言。
  • zstd – 主要產生空白字元，偶爾穿插字母，因為其行程編碼使單一重複字節非常便宜，而空格與換行符在莎士比亞語料庫中是成本最低的字面值。

這些結果顯示，底層壓縮算法的性質會強烈影響生成文字的風格。

社群見解

"你可以這樣用 gzip 分類測試檔的主題：gzip -9 sports.txt testfile.txt … 測試檔屬於壓縮後 .gz 檔案最小的那個主題。" – jll29 (HN)

"可能序列的空間比搜尋範圍大了許多數量級。因此結果僅能提供 gzip 作為『合理性檢測器』效能的下界。" – mg (HN)

"我很好奇這個方法用 bzip2 和 zstd 會如何…… bzip2 產生的序列不像人類語言；zstd 將單一重複字節編碼為近乎免費的行程序列，而空格與換行符是最便宜的字面值。" – networked (作者留言)

這些評論強化了兩點：(1) 基於壓縮的分類是一種已知技術，(2) 條搜尋方法大幅優於天真的貪心搜尋，但搜尋空間仍天文數字般龐大，因此該方法僅能提供 gzip 預測能力的啟發式估計。

局限與開放問題

  • 連貫性 – 輸出缺乏神經語言模型的長期語意一致性。DEFLATE 僅回溯 32 KiB，無法捕捉情節或角色弧線。
  • 搜尋品質 – 條搜尋仍是啟發式方法；無法保證找到全局最優（最具壓縮性）的延續。
  • 速度與表達力的權衡 – gzip 與輸入大小呈線性增長，運行速度比現代 LLM 快數個數量級，但這種速度是以表達力為代價。
  • 與 LLM 作為壓縮器的比較 – 有些評論者好奇大型語言模型相較於 gzip 能多好地壓縮文字，突顯了一個互補的研究方向。

這項研究的重要性

此實驗提供了 壓縮-預測等價定理 的具體示範：任何無損壓縮器皆可轉化為預測器，反之亦然。雖然 gzip 的預測能力相當基礎，但此方法開啟了探索非神經語言模型、以壓縮算法作為機率估計代理的基準，以及在大規模 AI 時代重新審視經典算法的新途徑。

Sources

相關