熵編碼法
![本頁使用了標題或全文手工轉換](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
熵編碼法是一種獨立於介質的具體特徵的進行無損數據壓縮的方案。
一種主要類型的熵編碼方式是對輸入的每一個符號,創建並分配一個唯一的前綴碼,然後,通過將每個固定長度的輸入符號替換成相應的可變長度前綴無關(prefix-free)輸出碼字替換,從而達到壓縮數據的目的。每個碼字的長度近似與概率的負對數成比例。因此,最常見的符號使用最短的碼。
根據香農的信源編碼定理,一個符號的最佳碼長是 −logbP,其中 b 是用來輸出的碼的數目,P 是輸入符號出現的概率。
霍夫曼編碼和算術編碼是兩種最常見的熵編碼技術。如果預先已知數據流的近似熵特性(尤其是對於信號壓縮),可以使用簡單的靜態碼。這些靜態碼,包括通用密碼(如Elias gamma coding或斐波那契編碼)和哥倫布編碼(比如元編碼或Rice編碼)。
一般熵編碼器與其它編碼器聯合使用。比如LHA首先使用LZ編碼,然後將其結果進行熵編碼。Zip和Bzip的最後一級編碼也是熵編碼。
編碼
[編輯]使用長度不同的比特串對字母進行編碼有一定的困難。尤其是,幾乎所有幾率的熵都是一個有理數。
霍夫曼編碼建議了一種將位元進位成整數的演算法,但這個演算法在特定情況下無法達到最佳結果。為此有人加以改進,提供最佳整數位元數。這個演算法使用二元樹來設立一個編碼。這個二叉樹的終端節點代表被編碼的字母,根節點代表使用的位元。
除這個對每個要編碼的數據產生一個特別的表格的方法外還有使用固定的編碼表的方法。比如加入要編碼的數據中符號出現的機率符合一定的規則的話就可以使用特別的變長編碼表。這樣的編碼表具有一定的係數來使得它適應實際的字母出現機率。
改進
[編輯]使用整數比特的方法往往無法獲得使用熵計算的比特數,因此其壓縮並非一定最佳。
比如字母列由兩個不同的字母組成,其中一個字母的可能性是,另一個字母的可能性是。以上算法的結果是每個字母應該用一個比特來代表,因此其結果的比特數與字母數相同。
但擴展取樣位數可以稍微彌補該破綻:上例的、、、,以霍夫曼編碼算法得結果為:每兩個字母平均用個比特,即平均每個字母用0.84375個比特來代表,向最佳熵值踏近了一步。
最佳熵編碼器應該為第一個字母使用個比特,為第二個字母使用個比特,因此整個結果是每個字母平均使用個比特。
使用算術編碼可以改善這個結果,使得原信息按照熵最佳來編碼。
模型
[編輯]要確定每個字母的比特數算法需要儘可能精確地知道每個字母的出現機率。模型的任務是提供這個數據。模型的預言越好壓縮的結果就越好。此外模型必須在壓縮和恢復時提出同樣的數據。在歷史上有許多不同的模型。
靜態模型
[編輯]靜態模型在壓縮前對整個文字進行分析計算每個字母的機率。這個計算結果用於整個文字上。
- 優點
- 編碼表只需計算一次,因此編碼速度高
- 除在解碼時所需要的機率值外結果肯定不比原文長
- 缺點
- 計算的機率必須附加在編碼後的文字上,這使得整個結果加長
- 計算的機率是整個文字的機率,因此無法對部分地區的有序數列進行優化
動態模型
[編輯]在這個模型里機率隨編碼過程而不斷變化。多種算法可以達到這個目的:
- 前向動態:機率按照已經被編碼的字母來計算,每次一個字母被編碼後它的機率就增高
- 反向動態:在編碼前計算每個字母在剩下的還未編碼的部分的機率。隨着編碼的進行最後越來越多的字母不再出現,它們的機率成為0,而剩下的字母的機率升高,為它們編碼的比特數降低。壓縮率不斷增高,以至於最後一個字母只需要0比特來編碼
- 優點
- 模型按照不同部位的特殊性優化
- 在前向模型中機率數據不需要輸送
- 缺點
- 每個字母被處理後機率要重算,因此比較慢
- 計算出來的機率與實際的機率不一樣,在最壞狀態下壓縮的數據比實際原文還要長
一般在動態模型中不使用機率,而使用每個字母出現的次數。
除上述的前向和反向模型外還有其它的動態模型計算方法。
比如在前向模型中可以不時減半出現過的字母的次數來降低一開始的字母的影響力。
對於尚未出現過的字母的處理方法也有許多不同的手段:比如假設每個字母正好出現一次,這樣所有的字母均可被編碼。
模型度
[編輯]模型度說明模型顧及歷史上多少個字母。比如模型度0說明模型顧及整個原文。模型度1說明模型顧及原文中的上一個字母並不斷改變其機率。模型度可以無限高,但是對於大的原文來說模型度越高其需要的計算內存也越多。
熵作為相似性的量度
[編輯]除了使用熵編碼作為壓縮數字數據一種方法外,熵編碼器也可以用來測量數據流和已經存在的類的數據之間的相似程度。這是通過對每類數據產生一個熵編碼器/壓縮器;通過將未壓縮的數據提供給每個壓縮機,據該壓縮機產生的最佳壓縮分類。具有最佳壓縮率的編碼器可能是用與未知數據最相似的數據訓練的編碼器。
外部連結
[編輯]- On-line textbook: Information Theory, Inference, and Learning Algorithms,David MacKay著,提供一個可訪問的香農理論和數據壓縮的介紹,包括霍夫曼編碼和算術編碼。
- Source Coding Book (頁面存檔備份,存於網際網路檔案館), by Wiegand and Schwarz
|