熵編碼法

熵編碼法是一種獨立於媒介的具體特徵的進行無失真數據壓縮的方案。

一種主要類型的熵編碼方式是對輸入的每一個符號，建立並分配一個唯一的字首碼，然後，通過將每個固定長度的輸入符號替換成相應的可變長度字首無關（prefix-free）輸出碼字替換，從而達到壓縮數據的目的。每個碼字的長度近似與概率的負對數成比例。因此，最常見的符號使用最短的碼。

根據香農的信源編碼定理，一個符號的最佳碼長是 −log_bP，其中 b 是用來輸出的碼的數目，P 是輸入符號出現的概率。

霍夫曼編碼和算術編碼是兩種最常見的熵編碼技術。如果預先已知數據流的近似熵特性（尤其是對於訊號壓縮），可以使用簡單的靜態碼。這些靜態碼，包括通用密碼（如Elias gamma coding或斐波那契編碼）和哥倫布編碼（比如元編碼或Rice編碼）。

一般熵編碼器與其它編碼器聯合使用。比如LHA首先使用LZ編碼，然後將其結果進行熵編碼。Zip和Bzip的最後一級編碼也是熵編碼。

編碼

使用長度不同的位元串對字母進行編碼有一定的困難。尤其是，幾乎所有幾率的熵都是一個有理數。

使用整數位元（bit）

霍夫曼編碼建議了一種將位元進位成整數的演算法，但這個演算法在特定情況下無法達到最佳結果。為此有人加以改進，提供最佳整數碼元數。這個演算法使用二叉樹來設立一個編碼。這個二叉樹的終端節點代表被編碼的字母，根節點代表使用的位元。

除這個對每個要編碼的數據產生一個特別的表格的方法外還有使用固定的編碼表的方法。比如加入要編碼的數據中符號出現的概率符合一定的規則的話就可以使用特別的變長編碼表。這樣的編碼表具有一定的係數來使得它適應實際的字母出現概率。

改進

使用整數位元的方法往往無法獲得使用熵計算的位元數，因此其壓縮並非一定最佳。

比如字母列由兩個不同的字母組成，其中一個字母的可能性是 $\mathrm {p} (A)=0{.}75$ ，另一個字母的可能性是 $\mathrm {p} (B)=0{.}25$ 。以上演算法的結果是每個字母應該用一個位元來代表，因此其結果的位元數與字母數相同。

但擴充取樣位數可以稍微彌補該破綻：上例的 $\mathrm {p} (AA)=0{.}5625$ 、 $\mathrm {p} (AB)=0{.}1875$ 、 $\mathrm {p} (BA)=0{.}1875$ 、 $\mathrm {p} (BB)=0{.}0625$ ，以霍夫曼編碼演算法得結果為：每兩個字母平均用 $(0.5625*1+0.1875*2+0.1875*3+0.0625*3)=1.6875$ 個位元，即平均每個字母用0.84375個位元來代表，向最佳熵值踏近了一步。

最佳熵編碼器應該為第一個字母使用 $-\log _{2}(0{.}75)\approx 0{.}41$ 個位元，為第二個字母使用 $-\log _{2}(0{.}25)=2$ 個位元，因此整個結果是每個字母平均使用 $-0{.}75*\log _{2}(0{.}75)-0{.}25*\log _{2}(0{.}25)\approx 0.81$ 個位元。

使用算術編碼可以改善這個結果，使得原資訊按照熵最佳來編碼。

模型

要確定每個字母的位元數演算法需要儘可能精確地知道每個字母的出現概率。模型的任務是提供這個數據。模型的預言越好壓縮的結果就越好。此外模型必須在壓縮和恢復時提出同樣的數據。在歷史上有許多不同的模型。

靜態模型

靜態模型在壓縮前對整個文字進行分析計算每個字母的概率。這個計算結果用於整個文字上。

優點
- 編碼表只需計算一次，因此編碼速度高
- 除在解碼時所需要的概率值外結果肯定不比原文長
缺點
- 計算的概率必須附加在編碼後的文字上，這使得整個結果加長
- 計算的概率是整個文字的概率，因此無法對部分地區的有序數列進行最佳化

動態模型

在這個模型里概率隨編碼過程而不斷變化。多種演算法可以達到這個目的：

前向動態：概率按照已經被編碼的字母來計算，每次一個字母被編碼後它的概率就增高
反向動態：在編碼前計算每個字母在剩下的還未編碼的部分的概率。隨着編碼的進行最後越來越多的字母不再出現，它們的概率成為0，而剩下的字母的概率升高，為它們編碼的位元數降低。壓縮率不斷增高，以至於最後一個字母只需要0位元來編碼
優點
- 模型按照不同部位的特殊性最佳化
- 在前向模型中概率數據不需要輸送
缺點
- 每個字母被處理後概率要重算，因此比較慢
- 計算出來的概率與實際的概率不一樣，在最壞狀態下壓縮的數據比實際原文還要長

一般在動態模型中不使用概率，而使用每個字母出現的次數。

除上述的前向和反向模型外還有其它的動態模型計算方法。

比如在前向模型中可以不時減半出現過的字母的次數來降低一開始的字母的影響力。

對於尚未出現過的字母的處理方法也有許多不同的手段：比如假設每個字母正好出現一次，這樣所有的字母均可被編碼。

模型度

模型度說明模型顧及歷史上多少個字母。比如模型度0說明模型顧及整個原文。模型度1說明模型顧及原文中的上一個字母並不斷改變其概率。模型度可以無限高，但是對於大的原文來說模型度越高其需要的計算主記憶體也越多。

熵作為相似性的量度

除了使用熵編碼作為壓縮數字數據一種方法外，熵編碼器也可以用來測量數據流和已經存在的類的數據之間的相似程度。這是通過對每類數據產生一個熵編碼器/壓縮器；通過將未壓縮的數據提供給每個壓縮機，據該壓縮機產生的最佳壓縮分類。具有最佳壓縮率的編碼器可能是用與未知數據最相似的數據訓練的編碼器。

外部連結

On-line textbook: Information Theory, Inference, and Learning Algorithms，David MacKay著，提供一個可訪問的香農理論和數據壓縮的介紹，包括霍夫曼編碼和算術編碼。
Source Coding Book （頁面存檔備份，存於互聯網檔案館）, by Wiegand and Schwarz