熵編碼

數據壓縮技術的理論基礎就是信息論。信息論中的信源編碼理論解決的主要問題：

（1）數據壓縮的理論極限；

（2）數據壓縮的基本途徑。

根據信息論的原理，可以找到最佳數據壓縮編碼的方法，數據壓縮的理論極限是信息熵。如果要求編碼過程中不丟失信息量，即要求保存信息熵，這種信息保持編碼叫熵編碼，是根據消息出現概率的分佈特性而進行的，是無損數據壓縮編碼。 ^[1] 

常見的熵編碼有：香農(Shannon)編碼、哈夫曼(Huffman)編碼和算術編碼(arithmetic coding)。在視頻編碼中，熵編碼把一系列用來表示視頻序列的元素符號轉變為一個用來傳輸或是存儲的壓縮碼流。輸入的符號可能包括量化後的變換系數，運動向量，頭信息（宏塊頭，圖象頭，序列的頭等）以及附加信息（對於正確解碼來説重要的標記位信息）。

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

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

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

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

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

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

最佳熵編碼器應該為第一個字母使用 − log2(0.75) ≈ 0.41個位元，為第二個字母使用 − log2(0.25) = 2個位元，因此整個結果是每個字母平均使用 − 0.75 * log2(0.75) - 0.25 * log2(0.25) ≈ 0.81個位元。

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

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

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

優點：

編碼表只需計算一次，因此編碼速度高，除在解碼時所需要的機率值外結果肯定不比原文長。

缺點：

計算的機率必須附加在編碼後的文字上，這使得整個結果加長；

計算的機率是整個文字的機率，因此無法對部分地區的有序數列進行優化。 ^[3] 

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

前向動態：機率按照已經被編碼的字母來計算，每次一個字母被編碼後它的機率就增高。

反向動態：在編碼前計算每個字母在剩下的還未編碼的部分的機率。隨着編碼的進行最後越來越多的字母不再出現，它們的機率成為0，而剩下的字母的機率升高，為它們編碼的比特數降低。壓縮率不斷增高，以至於最後一個字母只需要0比特來編碼。

模型按照不同部位的特殊性優化；

在前向模型中機率數據不需要輸送。

每個字母被處理後機率要重算，因此比較慢；

計算出來的機率與實際的機率不一樣，在最壞狀態下壓縮的數據比實際原文還要長。

一般在動態模型中不使用機率，而使用每個字母出現的次數。除上述的前向和反向模型外還有其它的動態模型計算方法。比如在前向模型中可以不時減半出現過的字母的次數來降低一開始的字母的影響力。對於尚未出現過的字母的處理方法也有許多不同的手段：比如假設每個字母正好出現一次，這樣所有的字母均可被編碼。 ^[3] 

模型度説明模型顧及歷史上多少個字母。比如模型度0説明模型顧及整個原文。模型度1説明模型顧及原文中的上一個字母並不斷改變其機率。模型度可以無限高，但是對於大的原文來説模型度越高其需要的計算內存也越多。 ^[3]