6.2 LZW與GIF#

概念說明#

LZW（Lempel-Ziv-Welch，Terry Welch, 1984）是 LZ78 的實用化改版，改動只有一個但影響深遠：把「新詞」從「字典詞＋新字元」改成「字典詞＋詞的首字元」，因此每步輸出只有一個字典索引，沒有字面字元。字典初始時就預載所有單一字元（如 ASCII 0–255），所以任何輸入都能起步，輸出天生就是索引串流，很適合硬體與影像資料。

流程直覺：不斷延長當前字串 w 直到 w+c 不在字典中；輸出 dic[w] 的索引，把 w+c 以下一個可用編號登錄，令 w = c 續跑。解碼端有個著名的 KwKwK 難題：當解碼端收到「尚未定義的索引」時（發生在輸入形如 "ababab..." 的自指重複），答案是「該條目 = 上一個條目 + 上一條目的首字元」——解碼器必須特判這一情形。這個小陷阱是 LZW 實作最容易出錯的地方。

GIF（Graphics Interchange Format, 1987, CompuServe）選用 LZW 壓縮索引色影像：先把像素值（調色盤索引，每像素 2～8 位元）排成序列，LZW 碼從 2^(最小碼長) 起步、碼長隨字典成長逐步加 1（可變碼長），並用兩個保留碼：CLEAR（清空字典重新開始，防止字典滿了之後效率凍結）與 EOI（結束）。GIF 的 LZW 變體碼長增長順序與標準略有出入（先發長碼再登錄），是著名的實作地雷（「GIF interlace 之外的另一個坑」）。

專利風波：LZW 在美國（Unisys, 1983 起申請）與其他國家有專利，1994 年 Unisys 開始向 GIF 工具作者收權利金，引發社群反彈，促成了無專利的 PNG（用 DEFLATE）誕生並取代 GIF 成為網路標準（直到動畫需求讓 GIF 復活）。這段歷史是「軟體專利如何形塑技術選擇」的經典案例；LZW 專利已於 2003–2004 全部到期，如今可自由實作。

LZW 的其他應用：Unix compress（.Z 檔）、TIFF 影像選項、早期 PDF 的 LZW 濾波器（後被 FlateDecode 取代）。相較 Huffman／算術編碼，LZW 是「單層」方案——自帶建模，不需要另一層熵編碼即可工作，簡潔但平均壓縮率略遜於兩層式 DEFLATE。

演算法步驟#

LZW 編碼： 1. 字典 ← 所有單一字元（索引 0..255），下個新索引 = 256。 2. w = ""；依序讀字元 c：若 w+c 在字典中，w ← w+c；否則輸出 dic[w]，登錄 dic[w+c] = 新索引，w ← c。 3. 結束時輸出 dic[w]（若非空）。 4. （GIF 變體）字典到達碼長上限時輸出 CLEAR 碼重置；碼長隨索引成長動態 +1。

LZW 解碼： 1. 同步建字典（初始單字元）。 2. 讀首索引，輸出其詞，記 prev = 該詞。 3. 讀下一索引 code： - 若 code 在字典：詞 entry = dic[code]。 - 若 code == 下個新索引（KwKwK）：entry = prev + prev[0]。 4. 輸出 entry；登錄 dic[新索引] = prev + entry[0]；prev ← entry。

Python 程式碼範例#

def lzw_encode(s):
    dic = {chr(i): i for i in range(256)}
    nxt, out, w = 256, [], ""
    for c in s:
        wc = w + c
        if wc in dic:
            w = wc
        else:
            out.append(dic[w])
            dic[wc] = nxt; nxt += 1
            w = c
    if w:
        out.append(dic[w])
    return out

def lzw_decode(codes):
    dic = {i: chr(i) for i in range(256)}
    nxt = 256
    prev = dic[codes[0]]
    out = [prev]
    for code in codes[1:]:
        if code in dic:
            entry = dic[code]
        elif code == nxt:                     # KwKwK 情形
            entry = prev + prev[0]
        else:
            raise ValueError("壞碼流")
        out.append(entry)
        dic[nxt] = prev + entry[0]; nxt += 1
        prev = entry
    return "".join(out)

s = "演算法演算法分析演算法設計演算法演算法"
# LZW 字典預載 0..255 單位元組，中文先轉 UTF-8 位元組（GIF 等實務同樣以位元組為單位）
b = s.encode("utf-8").decode("latin-1")     # 每字元 = 一個位元組
codes = lzw_encode(b)
print(codes[:15], "…")
assert lzw_decode(codes).encode("latin-1").decode("utf-8") == s
print(f"輸出索引數: {len(codes)}（原 {len(b)} 位元組）")
for t in ["ababababab", "the quick the quick the quick", "abcabcabcabc"]:
    c = lzw_encode(t)
    print(t[:20], "->", len(c), "碼")

複雜度分析#

編碼：字典用 trie 時每步 O(1) 延伸、失配時 O(|w|) 重新開始，總 O(n)；用 dict 存「字串→索引」（本例）最壞 O(n×|w|)，教學可、工程要換 trie 或雜湊。
解碼：每碼 O(1) 查表＋O(|entry|) 輸出，總 O(n)；空間 O(字典條目×平均詞長)。
壓縮率：對重複性文字常達 50% 上下；弱點是「字典冷啟動」與「字典滿後停滯」，故 GIF 用 CLEAR 碼週期性重置。
與 DEFLATE 對照：LZW 單層、快而簡；DEFLATE 兩層、壓縮率更高——可對同一檔案分別以本節程式與 zlib 量化比較。

練習#

在 lzw_decode 中刻意輸入 "abababab" 的編碼，逐步列印字典成長過程，標出 KwKwK 發生的那一步，並用註解解釋為何 prev + prev[0] 是正確條目。
實作 GIF 式可變碼長：起始碼長 = ⌈log₂ 258⌉，索引增長到 2^碼長時碼長 +1，字典滿（4096）時送 CLEAR 重置；對一段影像索引序列編碼，統計總位元數。
用 zlib.compress 與你的 LZW 比較同一份 10 KB 文字的壓縮率與時間，寫 200 字分析 DEFLATE 兩層設計（LZ77＋Huffman）為何勝出。