6.1 LZ77與LZ78#

概念說明#

LZ77（Ziv & Lempel, 1977）的核心洞察：文字中剛出現過的片段，之後常會再出現。壓縮器維護一個滑動視窗（例如最近 32 KB 的已編碼內容），讀到位置 i 時，往回在視窗裡找最長的匹配片段；若找到長度 L、距離 d 的匹配，就輸出三元組 (d, L, 下一個字元)；找不到匹配則輸出 (0, 0, 字元)。解壓時視窗裡就有原文，直接「往前 d 個位置抄 L 個字元」即可還原——不需要字典，字典就是文字本身。

兩個巧妙的細節：其一，L 可以超過 d，即匹配可以與自己重疊，例如 "aaaaaa" 在位置 1 起可以用 (1, 5) 表示「重複抄前一個字元五次」，這讓 LZ77 對連續重複特別有效；其二，輸出的 (d, L) 是整數對，之後可以再用熵編碼（Huffman／算術）壓一遍——DEFLATE 就是這樣兩層合體。

LZ78（1978）改用顯式字典：從空字典開始，每次讀入「目前字典中最長的匹配詞 w + 一個新字元 c」，輸出（詞 w 的索引, c），並把 w+c 加入字典。每個條目只建一次，解壓端同步建同一本字典。LZ78 的字典會無限成長，實務上需定期清空或限制大小。

兩者比較：LZ77 視窗有限但天然「忘舊」、局部性好；LZ78 字典可涵蓋全文的長距離重複，但建字典的輸出開銷較大。LZSS（Lempel-Ziv-Storer-Szymanski, 1982）是 LZ77 的改良：用 1 個位元旗標區分「字面值」與「(d,L) 對」，省掉每個三元組都塞第三欄字元的浪費；多數實務系統（DEFLATE、LZ4、zstd）都是 LZSS 系。

應用版圖：DEFLATE（zip/gzip/PNG）、LZ4（超快解壓、遊戲與即時系統）、zstd（現代均衡之王）、LZX、LZMA（7-zip、xz）、Brotli（網頁）。而 LZ77 與第3章後綴結構的關聯也很深：找最長匹配正是後綴樹/後綴陣列的拿手好戲，高性能壓縮器用雜湊鏈或二元樹索引視窗內容來加速匹配搜尋。

演算法步驟#

LZ77 編碼： 1. 初始化視窗為空、游標 i = 0。 2. 在 s[max(0, i−W) : i] 中搜尋 s[i:] 的最長前綴匹配，得距離 d 與長度 L（L ≤ 最大匹配長度上限，如 258）。 3. 輸出 (d, L, s[i+L])（若 i+L 超出結尾則只輸出 (d, L)）；游標前進 L+1。 4. 重複直到結尾。

LZ77 解碼： 1. 對每個 (d, L, c)：從輸出末端往前 d 位元組起，逐字元複製 L 個（允許重疊複製：邊抄邊擴充），再附加 c。

LZ78 編碼： 1. 字典空，索引 0 代表「空詞」。 2. 找「字典中最長的匹配詞 w」；讀下一字元 c，輸出 (idx(w), c)；把 w+c 以新索引加入字典。 3. 重複。

Python 程式碼範例#

def lz77_encode(s, window=20, max_len=15):
    out, i = [], 0
    while i < len(s):
        best_d, best_l = 0, 0
        for d in range(1, min(i, window) + 1):        # 樸素搜尋
            l = 0
            while (l < max_len and i + l < len(s)
                   and s[i - d + l] == s[i + l]):
                l += 1
            if l > best_l:
                best_d, best_l = d, l
        nxt = s[i + best_l] if i + best_l < len(s) else ""
        out.append((best_d, best_l, nxt))
        i += best_l + 1
    return out

def lz77_decode(tokens):
    out = []
    for d, l, c in tokens:
        for _ in range(l):
            out.append(out[-d])          # 重疊複製：邊抄邊長
        out.append(c)
    return "".join(out)

def lz78_encode(s):
    dic, out, i, nxt = {"": 0}, [], 0, 1
    while i < len(s):
        w = ""
        while i < len(s) and w + s[i] in dic:
            w += s[i]; i += 1
        c = s[i] if i < len(s) else ""
        out.append((dic[w], c))
        dic[w + c] = nxt; nxt += 1; i += 1
    return out

def lz78_decode(tokens):
    dic, out = {0: "", 1: None}, []      # 首條目僅佔位，見下
    dic, out, nxt = {}, [], 1
    for idx, c in tokens:
        w = dic.get(idx, "") + c
        out.append(w)
        dic[nxt] = w; nxt += 1
    return "".join(out)

s = "演算法_演算法分析_演算法設計_演算法"
tok = lz77_encode(s)
print(tok)
assert lz77_decode(tok) == s
print("LZ77 壓縮後 token 數:", len(tok), "原長:", len(s))
print(lz78_decode(lz78_encode("abracadabra abracadabra")))

複雜度分析#

LZ77（樸素）：每位置找匹配 O(W×L)，總最壞 O(n²W)；實務用雜湊鏈（把 3-gram 雜湊到位置串列）或後綴樹加速到近線性；gzip 用雜湊鏈＋貪婪匹配，LZ4 更激進地只找一個匹配以追求速度。
解碼：每 token O(L)，總 O(輸出長)——解壓通常比壓縮快 3～10 倍，這是 LZ 系的共同優勢。
LZ78：編碼每輪需「最長字典匹配」，trie 查詢 O(|w|)，總 O(n)；空間隨字典線性成長。
理論：Ziv-Lempel 定理——對平穩遍歷源，LZ77/LZ78 的每符號位元數漸近收斂到熵；壓縮率上限受視窗大小約束（視窗越大越能捕捉長距離重複）。

練習#

實作 LZSS：輸出以 1-bit 旗標前綴的「字面值」或「(d,L) 對」，統計同一段文字上 LZ77 三元組與 LZSS 的位元數差異。
把 lz77_encode 的匹配搜尋改用 3-gram 雜湊鏈（dict: hash → 位置串列），在 1 萬字文字上量測加速比，並驗證輸出與樸素版一致（允許匹配長度同時取不同但不影響解碼正確性）。
實驗視窗大小 W = 64、256、1024、4096 對中文新聞文本壓縮率的影響，畫出曲線並解釋「為何報酬遞減」。