軟體壓縮原理：為什麼熵編碼
二、熵是什麼？從資訊理論建立直覺
「熵」這個詞來自物理學的熱力學，代表系統的混亂程度。1948 年，克勞德·夏農（Claude Shannon）在論文《A Mathematical Theory of Communication》中把它引入資訊理論，賦予了全新的意義：熵是資訊不確定性的度量。夏農的貢獻在於，他把「資訊」這個模糊的概念，轉化為可以被精確計算、甚至被壓縮到極限的數學對象。
夏農熵的定義與直覺解釋
對一個離散隨機變數 X，其可能取值為 x₁, x₂, …, xₙ，對應機率為 p₁, p₂, …, pₙ，夏農熵定義為：
H(X) = − Σ pᵢ · log₂(pᵢ)
這個公式的單位是「位元」（bit）。它的直覺意義是：在平均意義下，要描述這個隨機變數的結果，最少需要多少個位元。如果某個事件必然發生（機率 1），熵為 0，因為你不需要任何位元就能描述它——結果早就知道了。如果一個公平硬幣有兩個等機率結果（各 0.5），熵為 1 位元，因為你確實需要 1 個位元來區分正反面。如果是公平的六面骰，熵約為 2.585 位元，略高於 2 位元、低於 3 位元，這也解釋了為什麼用 3 位元編碼骰子結果會有些浪費。
熵的另一個重要性質是：當所有符號等機率時，熵最大；當分布越集中（某個符號機率越接近 1），熵越小。這正好對應我們的直覺：如果資料高度可預測，它的資訊量就低，也就越容易被壓縮。
熵與可壓縮性的關係
夏農進一步提出了「無失真編碼定理」（Source Coding Theorem），指出對於一個符號來源，任何無損編碼方案的平均碼長 L，必定滿足：
L ≥ H(X)
換句話說，熵是無損壓縮的理論下限。你可以設計出讓平均碼長無限接近熵的編碼器，但永遠不可能低於熵。這條定理的重要性在於，它為所有壓縮演算法的效能提供了一把客觀的尺規：如果你的資料熵是 4.2 位元／符號，而你目前的編碼器平均用了 5.8 位元／符號，那就代表還有約 1.6 位元／符號的進步空間；但如果你的編碼器已經做到 4.25 位元／符號，那麼再怎麼優化演算法，收益也只會越來越小。
這也說明了一個常被誤解的現象：「已經壓縮過的檔案再壓縮，通常沒什麼效果」。因為像 JPEG、MP3、ZIP 這類檔案，其內容已經接近該資料的熵下限，符號分布接近均勻、缺乏明顯的統計冗餘，後續的熵編碼器自然難以再榨出什麼油水。這不是軟體不夠力，而是資訊理論在告訴你：這裡已經沒有免費的午餐了。
三、熵編碼的原理與經典演算法
理解了熵是壓縮的極限之後，下一個問題自然是：如何在實務上逼近這個極限？這就是熵編碼器的工作。熵編碼的核心思想是：根據符號出現的機率，動態分配長短不一的碼字。高頻符號配短碼，低頻符號配長碼，使得平均碼長最小化。以下介紹幾種最具代表性的熵編碼技術。
霍夫曼編碼：最經典的直覺實現
1952 年由大衛·霍夫曼（David Huffman）提出的霍夫曼編碼，是許多電腦科學課程必教的演算法。它的做法是建立一棵二元樹：把所有符號依出現頻率放進優先佇列，每次取出頻率最低的兩個節點合併成一個新節點，新節點的頻率為兩者之和，重複直到只剩一個根節點。最後從根走到葉的路徑（左為 0、右為 1）即為每個符號的碼字。
霍夫曼編碼的優點是簡單、快速、保證最優的前綴碼——在所有「每個符號對應整數個位元」的前綴碼方案中，霍夫曼編碼的平均碼長最短。它廣泛應用於 DEFLATE（ZIP、gzip 的核心）、JPEG、MP3 等格式中。然而霍夫曼編碼也有一個先天限制：每個符號最少要用 1 個位元表示。如果某個符號的機率高達 0.9，其理論資訊量只有約 0.152 位元，但霍夫曼編碼仍必須給它至少 1 個位元，這就造成了浪費。當符號機率分布極度不均勻時，霍夫曼編碼與熵之間的差距會變得明顯。
算術編碼：逼近極限的優雅解法
算術編碼（Arithmetic Coding）突破了「整數位元」的限制。它不再為每個符號分配固定碼字，而是把整段訊息映射到 [0, 1) 區間內的一個實數。每讀入一個符號，就依其機率把當前區間按比例分割，並選定該符號對應的子區間；訊息越長，區間越窄，最後只需輸出一個能唯一標識該區間的小數即可。
算術編碼的理論效率極高，平均碼長可以無限接近熵，因此在 JPEG 2000、H.264／H.265 的 CABAC、以及許多現代壓縮格式中被廣泛採用。它的代價是計算複雜度較高、對錯誤敏感（一個位元錯誤可能導致後續全部解碼失敗），且早期受到專利問題影響，推廣速度不如霍夫曼編碼。儘管如此，在需要極致壓縮率的場景中，算術編碼仍是首選。
區間編碼與現代變體：ANS 的崛起
近年來，一種名為 ANS（Asymmetric Numeral Systems，非對稱數字系統）的熵編碼技術快速竄紅。ANS 由 Jarek Duda 於 2014 年提出，其核心思想是把算術編碼的「區間」概念，轉化為整數狀態機的運算，因而兼具算術編碼的壓縮率與霍夫曼編碼的速度。ANS 已成為 zstd、LZFSE、以及部分影像與影片編碼器的關鍵元件。
ANS 的出現，某種程度上打破了過去「壓縮率與速度難以兼得」的取捨。它讓開發者能在接近熵下限的同時，維持極高的吞吐量，這也是近年壓縮軟體效能大幅提升的重要技術背景之一。對於評測軟體的人來說，一款工具是否採用 ANS 或類似的現代熵編碼器，往往是判斷其技術世代的重要線索。
四、為什麼一定要用熵編碼？它在壓縮架構中的角色
讀到這裡，你可能會問：既然前處理（如 LZ77、BWT）已經能消除大量冗餘，為什麼還需要熵編碼？直接把前處理的結果輸出不行嗎？答案是：不行，而且差距往往非常巨大。以下從兩個角度說明熵編碼為何不可替代。
前處理與熵編碼的分工
以最常見的 DEFLATE 格式為例（ZIP、gzip、PNG 都用它）。DEFLATE 的第一階段是 LZ77：它會找出重複出現的字串，並用「距離＋長度」的配對來取代，例如把「ABCABCABC」轉成「ABC(3,3)」之類的表示。這一步大幅減少了資料量，但輸出結果仍然是一連串的符號：有些是字面值（literal），有些是長度碼，有些是距離碼。
問題在於，這些符號的出現頻率極度不均勻：短距離匹配出現的頻率遠高於長距離匹配，常見字元出現的頻率遠高於罕見字元。如果我們對這些符號一律用固定位元數輸出，就等於把 LZ77 辛苦整理出來的統計結構白白浪費掉。熵編碼的作用，正是根據這些符號的實際分布，重新分配碼長，把「常見的短距離匹配」壓縮成極短的碼字，把「罕見的長距離匹配」用較長的碼字表示。DEFLATE 使用霍夫曼編碼來完成這件事，並針對字面值／長度碼與距離碼分別建立兩棵霍夫曼樹。
換句話說，前處理負責「把資料變成統計分布集中、適合編碼的形式」，熵編碼負責「把這個分布轉換成最短的位元流」。少了熵編碼，前處理的成果將大打折扣；少了前處理，熵編碼也難以發揮，因為原始資料的分布可能還不夠集中。兩者是相輔相成的關係。
熵編碼的理論極限與實務差距
實務上，熵編碼器的效能通常以「壓縮率 vs. 理論熵」來衡量。一個好的熵編碼器，其輸出位元數應該非常接近資料的熵；若差距過大，就代表編碼器效率不佳，或者前處理沒有把資料整理好。這也是為什麼我們在評測壓縮軟體時，不能只看「壓縮後檔案大小」，還要看「壓縮耗時」、「解壓耗時」、「記憶體用量」等多維指標——因為不同熵編碼器在這些面向上的取捨差異極大。
舉例來說，bzip2 使用 BWT 加上霍夫曼編碼，壓縮率通常優於 gzip，但速度慢上許多；xz 使用 LZMA（結合了區間編碼與極長的字典），壓縮率更高，但壓縮時間可能是 gzip 的數十倍；zstd 則透過 ANS 與精心設計的字典策略，在壓縮率與速度之間取得極佳平衡。這些差異的根源，很大程度上就來自熵編碼器與前處理策略的不同組合。
五、熵編碼的實務應用與軟體評測觀點
理解了原理之後，我們把視角拉回實務。對一般使用者與進階玩家而言，熵編碼的知識可以怎麼用？以下從常見格式與評測方法兩個層面來談。
常見壓縮軟體中的熵編碼器
下表整理幾種常見壓縮格式所採用的前處理與熵編碼組合，幫助你建立整體圖像：
從這份清單可以看出，幾乎所有現代壓縮格式都把熵編碼放在流程的最後一環，負責把前面各階段整理好的符號，轉換成最終的位元流。熵編碼器的好壞，往往直接決定了格式的壓縮上限。
如何評估壓縮軟體的熵編碼效率
如果你正在評測一款壓縮軟體，或想比較不同工具的優劣，可以從以下幾個角度切入：
特別提醒：不要只看「壓縮後檔案大小」就下結論。一款工具能把檔案壓得很小，可能是因為它採用了極長的字典與極慢的搜尋策略，而非熵編碼特別優秀。反之，一款壓縮率中等的工具，其熵編碼器可能已經非常接近理論極限。真正專業的評測，應該把「壓縮率」「速度」「資源用量」「相容性」放在一起看，並針對不同使用場景給出建議。
六、常見誤解與限制：熵編碼不是萬靈丹
最後，我們來釐清幾個關於熵編碼與壓縮的常見誤解，避免在評測或使用時做出錯誤判斷。
誤解一：壓縮率越高越好。 事實上，壓縮率與速度、資源用量之間存在明顯的取捨。對需要即時處理的場景（如網路傳輸、資料庫即時備份），過度追求壓縮率反而會拖累整體效能。選擇工具時，應以「總體成本」為考量，而非單看檔案大小。
誤解二：已經壓縮過的檔案可以再大幅壓縮。 如前所述，像 JPEG、MP3、ZIP 這類檔案已接近其熵下限，再壓縮通常只能獲得極小的收益，甚至可能因格式重複包裝而變大。這是資訊理論的限制，不是軟體的問題。
誤解三：熵編碼可以處理任何資料。 熵編碼的效率高度依賴「符號分布是否集中」。如果資料本身接近均勻分布（例如已加密的資料、隨機雜訊），熵編碼幾乎無法壓縮。這也解釋了為什麼加密後的檔案通常「壓不動」——加密的本質就是把資料變成高熵、無規律的形式。
誤解四：有損壓縮不需要熵編碼。 恰恰相反，有損壓縮同樣需要熵編碼。以 JPEG 為例，DCT 與量化之後產生的係數，仍需透過霍夫曼或算術編碼轉成位元流；影片編碼中的 CABAC 更是壓縮效率的關鍵。有損壓縮只是在前端容許誤差，後端的熵編碼依然不可或缺。
結語：理解熵，才能讀懂壓縮的邊界
回顧整篇文章，我們從「壓縮是什麼」出發，說明了冗餘的種類與前處理的角色；接著引入夏農熵，解釋它為何是無損壓縮的理論下限；再深入霍夫曼編碼、算術編碼、ANS 等熵編碼技術的原理與取捨；最後把視角拉回實務，談到熵編碼在現代壓縮格式中的定位，以及評測軟體時應注意的面向。
熵編碼之所以是資料壓縮的靈魂，在於它直接對應資訊理論的下限。前處理可以消除結構冗餘、統計冗餘，但最終能把這些成果「榨乾」的，仍然是熵編碼器。一款壓縮軟體的技術含量，很大程度上就體現在它如何設計前處理與熵編碼的搭配，以及如何在壓縮率、速度、資源用量之間取得平衡。
對一般使用者而言，理解這些原理或許不會讓你立刻選到「最強」的壓縮工具，但它能讓你看懂評測數據背後的意義，不再被「壓縮率提升 30%」這類行銷話術牽著走。對開發者而言，熵編碼更是理解現代資料處理管線的必經之路。下一次當你按下「壓縮」按鈕時，不妨想想：在這短短幾秒鐘裡，夏農的理論、霍夫曼的樹、算術編碼的區間，正悄悄地為你省下每一個位元。