軟體壓縮原理：為什麼字典編碼
哈夫曼編碼：讓高頻符號走捷徑
1952 年，David Huffman 提出了著名的哈夫曼編碼。它的核心思想非常優雅：根據符號出現的頻率建立一棵二元樹，頻率越高的符號越靠近樹根，編碼越短；頻率越低的符號越遠離樹根，編碼越長。這樣一來，整體平均碼長就會逼近資訊理論中的「熵」（Entropy），達到接近理論極限的壓縮效果。
舉例來說，若一段文字中字母 e 出現的機率是 30%，那麼它可能被編成 2 個位元的碼；而罕見的字母 z 出現機率只有 0.1%，可能被編成 10 個位元的碼。經過這樣的重新編碼，整份資料的總位元數就能顯著下降。哈夫曼編碼的優點是實作簡單、解碼速度快，至今仍是許多壓縮格式的標準配備。
然而，哈夫曼編碼有一個根本限制：它只看「單一符號」的出現頻率，看不到「字串」層級的重複。對於「the」這種由三個字母組成、在英文中重複出現數百次的高頻字串，哈夫曼編碼只能分別對 t、h、e 三個字母編碼，無法把「the」當成一個整體來處理。換句話說，哈夫曼編碼處理的是統計冗餘，卻對結構冗餘束手無策。
此外，哈夫曼編碼還有幾個實務上的痛點：它需要先統計整份資料的符號頻率，才能建立編碼表；編碼表本身也必須儲存在壓縮檔中，形成額外開銷；而且在符號種類很多、分布很平均的情況下，壓縮效果會大打折扣。這些限制，正好為字典編碼的出場鋪好了舞台。
變長編碼的極限與字典編碼的互補性
算術編碼（Arithmetic Coding）是另一個處理統計冗餘的強大工具，它能突破哈夫曼編碼「整數位元」的限制，把每個符號映射到 [0,1) 區間中的一個小區段，理論上可以更逼近熵的極限。但算術編碼的計算複雜度較高，早期也有專利爭議，因此在一般用途的壓縮軟體中，哈夫曼編碼仍然是更常見的選擇。
但不論是哈夫曼編碼還是算術編碼，它們都有一個共同的盲點：它們把資料視為一連串獨立的符號，而忽略了符號之間的「順序關係」與「重複模式」。而真實世界的資料——無論是文字、程式碼、還是二進位檔案——往往充滿了大量重複的片段。這正是字典編碼的切入點：它不改變符號的編碼方式，而是改變「看待資料的單位」，把重複的字串壓縮成單一的「引用」。從這個角度來看，字典編碼與熵編碼並非競爭關係，而是互補的兩把利器。
三、字典編碼的核心思想：以重複換空間
字典編碼的基本原理可以用一句話概括：「如果某段字串之前出現過，就不要重新寫一遍，而是記錄一個指向它的引用。」這個引用通常包含兩個資訊：一是「距離」（Distance），表示要往回追溯多少個字元才能找到該字串；二是「長度」（Length），表示要複製多少個字元。解壓縮時，程式只要根據這兩個數字，把之前的內容複製過來即可，完全不需要額外儲存重複的字串本身。
想像你在抄寫一本書，發現某一段話和前面某一段完全一樣。你不會傻傻地再抄一遍，而是會寫「同上，見第 37 頁第 2 段」。字典編碼做的就是這件事，只是它把「頁碼」換成了「距離」、把「段」換成了「長度」，並且用二進位有效率地編碼這兩個數字。
三種字典編碼的範式
依照字典的建立方式與使用方式，字典編碼大致可以分成三種範式：
這三種範式各有取捨：靜態字典壓縮率高但缺乏彈性；動態字典能自我調適但需要額外維護字典結構；滑動視窗實作簡單、速度快，但只能參照最近一段資料，對長距離重複的掌握較弱。實務上的壓縮器往往會混用多種策略，或加入更複雜的資料結構（如雜湊表、二元樹、後綴陣列）來加速比對。
字典編碼與熵編碼的分工
值得一提的是，字典編碼的輸出本身通常還會再經過一層熵編碼。舉例來說，LZ77 產生的「距離-長度對」與「字面符號」（Literal）仍然是位元序列，這些位元序列的分布往往極不平均（例如距離值常集中在某些範圍），因此可以用哈夫曼編碼或算術編碼再壓縮一次。這種「先字典、後熵編碼」的兩階段架構，正是 DEFLATE、LZX、Zstandard 等現代格式的共同設計。
換句話說，字典編碼負責「消除結構冗餘」，熵編碼負責「消除統計冗餘」，兩者相輔相成。這也解釋了為什麼單靠字典編碼通常無法達到最佳壓縮率——你還需要一個好的熵編碼器來收拾殘局。
四、經典字典編碼演算法深度剖析
理解了字典編碼的核心思想後，我們來看看幾個最具影響力的經典演算法。它們不僅是學術史上的里程碑，更是今日無數壓縮工具的技術基礎。
LZ77：滑動視窗與距離-長度對
1977 年，Lempel 與 Ziv 發表的 LZ77 是字典編碼的開山之作。它的核心概念是「滑動視窗」：壓縮器維護一個大小固定的視窗（例如 32 KB），視窗內是最近處理過的資料。每當要編碼新的資料時，壓縮器會在視窗中搜尋與當前位置相符的最長字串；找到後，就輸出一組「（距離，長度）」對，否則就輸出一個「字面符號」（Literal）。
舉個簡化的例子：假設資料是「ABCABCABC」，視窗大小足夠。壓縮器讀到第一個「ABC」時，因為視窗中還沒有可參照的內容，所以輸出三個字面符號 A、B、C。接著讀到第二個「ABC」時，發現視窗中位置 0 開始有「ABC」，於是輸出「（距離=3，長度=3）」，表示「往回 3 個字元，複製 3 個字元」。第三個「ABC」同理，也能用一個短短的距離-長度對來表示。原本 9 個字元，最後可能只需幾個位元組就能表達。
LZ77 的優點是結構簡單、不需要額外的字典儲存空間（字典就是視窗本身）、解壓縮速度極快。它的缺點則是：只能參照視窗內的重複，對於距離很遠的重複無能為力；而且「距離」與「長度」的數值分布不均，需要良好的熵編碼來進一步壓縮。儘管如此，LZ77 的影響力無庸置疑——今日幾乎所有主流的通用壓縮格式，其核心都源自 LZ77 或其變體。
LZ78：顯式字典的建立
1978 年，Lempel 與 Ziv 再接再厲發表了 LZ78。與 LZ77 不同，LZ78 不採用滑動視窗，而是建立一本「顯式字典」：每當遇到一個沒見過的字串，就把它加入字典，並給它一個編號。壓縮時輸出的是「（字典索引，下一個字元）」的組合，解壓縮端則依照相同規則重建字典。
LZ78 的優點是它能夠捕捉任意距離的重複——只要字串曾經出現過並被加入字典，之後無論隔多遠都能參照。這在某些具有長距離重複特性的資料上，壓縮率會優於 LZ77。然而，LZ78 的字典會不斷成長，記憶體需求較高；而且字典的維護與查找需要額外的資料結構。這些特性使得 LZ78 在通用壓縮領域的普及度不如 LZ77，但它卻是後續 LZW 演算法的直接前身。
LZW：從專利風雲到 GIF 與 TIFF
1984 年，Terry Welch 在 LZ78 的基礎上提出了 LZW（Lempel-Ziv-Welch）演算法。LZW 最關鍵的改進，是不需要在壓縮檔中儲存字典——解壓縮端可以根據已解出的資料，即時重建出與壓縮端完全相同的字典。這個「字典自我生成」的特性，讓 LZW 的實作變得極為精簡，也讓它成為早期電腦系統中最受歡迎的壓縮方法之一。
LZW 後來被廣泛應用於 GIF 影像格式、TIFF 檔案、PDF 中的部分串流、以及 Unix 的 compress 指令。然而，LZW 也因為專利問題而聲名大噪：Unisys 公司曾對 LZW 演算法主張專利，導致 1990 年代許多軟體開發者被迫移除 GIF 支援或支付授權金。這場專利風波間接催生了 PNG 格式的誕生（PNG 採用了無專利爭議的 DEFLATE），也成為開源社群與軟體專利制度之間最著名的衝突案例之一。
不論專利爭議如何，LZW 在技術上的貢獻是明確的：它證明了「字典可以在壓縮與解壓縮兩端同步生成」，大幅降低了字典編碼的實作門檻。這個思想至今仍影響著許多串流壓縮協定的設計。
五、字典編碼在現代壓縮格式中的角色
談完經典演算法，我們把視角拉回現代。今日我們使用的壓縮格式，幾乎沒有一個是「純粹」的字典編碼，而是把字典編碼與熵編碼、甚至更先進的上下文模型結合在一起。以下幾個代表性格式，正好可以說明字典編碼在不同場景下的應用方式。
DEFLATE：LZ77 與哈夫曼編碼的黃金組合
DEFLATE 是 Phil Katz 在 1990 年代初期為 PKZIP 所設計的壓縮格式，後來被標準化為 RFC 1951，並廣泛應用於 ZIP、GZIP、PNG、以及 HTTP 傳輸中的 Content-Encoding。它的架構正是「先 LZ77、後哈夫曼」的兩階段設計：先用 LZ77 找出重複字串並輸出距離-長度對，再用哈夫曼編碼對字面符號、距離與長度進行熵編碼。
DEFLATE 的成功有幾個關鍵：第一，它完全免費、無專利爭議，因此在開源社群中迅速普及；第二，它的壓縮率與速度取得了極佳的平衡，適合一般用途；第三，它的實作相對簡單，幾乎所有程式語言都有成熟的函式庫。時至今日，DEFLATE 仍然是網際網路上最常見的壓縮格式之一，你每次開啟網頁時，伺服器很可能就是用 GZIP（DEFLATE 的一種封裝）把內容壓縮後傳送給你的。
不過，DEFLATE 也有其時代限制：它的視窗大小固定為 32 KB，對於大型檔案或長距離重複的掌握較弱；哈夫曼編碼的靜態或動態表頭也有一定的額外開銷。這些限制，正好成為新一代格式改進的切入點。
現代格式：Zstandard、Brotli、LZ4 的演進
近年來，壓縮技術出現了幾個明顯的演進方向：更高的壓縮率、更快的速度、以及更好的「字典訓練」能力。以下三個格式特別值得關注：
從這三個格式可以看出，字典編碼在現代壓縮領域並沒有被淘汰，而是持續演化。滑動視窗變得更聰明、字典訓練變得更自動化、與熵編碼的整合變得更緊密。字典編碼的核心思想——「用引用取代重複」——始終沒有改變，改變的只是實作的巧思與工程的最佳化。
字典訓練：針對小檔案與特定領域的最佳化
近年來一個很重要的發展是「字典訓練」（Dictionary Training）。傳統的滑動視窗對於小檔案（例如幾 KB 的 JSON 設定檔或 API 回應）效果有限，因為視窗內根本沒有足夠的歷史資料可供參照。為了解決這個問題，現代的壓縮工具（如 Zstandard、Brotli）允許使用者先從一批代表性樣本中「訓練」出一本字典，壓縮時把這本字典一併載入，讓小檔案也能享受到字典編碼的好處。
這個技術在實務上非常有用。例如，一個微服務架構每天要傳輸數百萬筆小型的 JSON 訊息，若能針對這些訊息的結構訓練一本字典，整體的網路頻寬與儲存成本就能顯著下降。字典訓練讓字典編碼從「通用壓縮」進一步走向「領域特化壓縮」，這是近年壓縮技術最重要的實務進展之一。
六、字典編碼的極限、挑戰與實務考量
雖然字典編碼威力強大，但它並不是萬靈丹。在實務應用中，工程師必須面對一連串的取捨與挑戰，才能讓壓縮系統真正發揮效益。
壓縮率與速度的永恆拉鋸
壓縮演算法最核心的取捨，就是「壓縮率」與「速度」之間的平衡。想要更高的壓縮率，通常需要更徹底的搜尋（例如在更大的視窗中尋找更長的重複字串）、更複雜的熵編碼模型、或更多的記憶體。但這些都會拖慢壓縮與解壓縮的速度。反之，若追求極致速度，就必須犧牲部分壓縮率，例如使用較小的視窗、較簡單的比對策略。
這也是為什麼市場上會同時存在多種壓縮格式：DEFLATE 適合通用場景、Zstandard 提供可調的壓縮等級、LZ4 專攻極速解壓、Brotli 針對網頁內容最佳化。沒有一種格式能在所有場景都勝出，選擇的關鍵在於理解你的資料特性與效能需求。
記憶體、字典大小與專利問題
字典編碼的另一個實務挑戰是記憶體。滑動視窗越大，能捕捉的重複距離越遠，壓縮率通常越好；但視窗越大，壓縮與解壓縮時需要的記憶體也越多。對於嵌入式系統或行動裝置，記憶體是珍貴資源，因此往往必須使用較小的視窗。動態字典（如 LZW）則更麻煩，因為字典會不斷成長，需要額外的記憶體管理機制。
此外，專利問題也是歷史上的重要考量。LZW 的專利爭議讓許多開發者轉向 DEFLATE；而某些進階的壓縮技術（如算術編碼的早期專利）也曾經影響格式的普及。時至今日，主流的開源壓縮格式多半已經沒有專利障礙，但企業在選擇壓縮方案時，仍應留意授權條款。
資料特性決定成敗
最後，字典編碼的效果高度依賴資料本身的特性。對於充滿重複模式的資料（如程式碼、日誌檔、資料庫備份），字典編碼往往能達到極佳的壓縮率；但對於已經壓縮過的資料（如 JPEG、MP3、ZIP 檔）或高熵的隨機資料（如加密後的內容），字典編碼幾乎無用武之地，甚至可能因為額外的表頭而讓檔案略微變大。這也是為什麼好的壓縮工具會先偵測資料特性，再決定是否啟用壓縮，或選擇合適的壓縮等級。
實務上，許多系統會採用「自適應」策略：先嘗試壓縮，若壓縮後沒有變小，就直接儲存原始資料。這種「壓縮無效就放棄」的機制，可以避免對不可壓縮資料做白工。
七、結論：字典編碼為何歷久不衰
回顧整篇文章，我們從壓縮的本質談起，理解了冗餘是壓縮的前提；接著說明了熵編碼如何處理統計冗餘，以及它在結構冗餘上的盲點；然後深入剖析字典編碼的核心思想——用「引用」取代「重複」，並依序介紹了 LZ77、LZ78、LZW 三個經典演算法；最後說明了字典編碼在 DEFLATE、Zstandard、Brotli、LZ4 等現代格式中的角色，以及實務上的取捨與挑戰。
那麼，為什麼字典編碼能夠成為無損壓縮的骨幹，並且歷久不衰？我認為有三個關鍵原因：
第一，它直接對應了真實世界資料的結構特性。無論是文字、程式碼、還是二進位檔案，重複模式都是最普遍、最容易利用的冗餘形式。字典編碼正是針對這個特性設計的，因此適用範圍極廣。
第二，它的核心思想極其簡潔，卻有無窮的實作變化。「用引用取代重複」這個概念簡單到可以用一句話說完，但透過不同的視窗策略、字典結構、比對演算法與熵編碼搭配，可以變化出無數種效能特性各異的壓縮器。這種「簡單核心、豐富變化」的特性，正是它能持續演進的原因。
第三，它與其他技術的相容性極佳。字典編碼可以和哈夫曼編碼、算術編碼、FSE、甚至機器學習模型結合，形成多階段的壓縮管線。這種模組化的特性，讓它能不斷吸收新技術，而不會被時代淘汰。
對於軟體開發者與資訊工作者而言，理解字典編碼不僅是理解一個演算法，更是理解「如何用更精簡的方式描述資料」這一套思維。當你在設計 API、撰寫日誌、選擇壓縮格式、甚至最佳化資料庫儲存時，這套思維都能派上用場。下一次當你看到一個 ZIP 檔或網頁的 Content-Encoding 標頭時，不妨想想背後那套已經演進了近半世紀的字典編碼技術——它安靜地運作著，卻實實在在地支撐著我們每天使用的數位世界。
壓縮技術的演進不會停止。隨著 AI 與大型語言模型的興起，學界也開始探索以神經網路為基礎的壓縮方法（如基於語言模型的文字壓縮），試圖突破傳統演算法的極限。但可以預見的是，在可預見的未來裡，字典編碼仍將是無損壓縮不可或缺的基石。理解它，就是理解現代數位基礎建設的重要一環。