熵編碼法是一種進行無損數據壓縮的技術，在這個技術中一段文字中的每個字母被一段不同長度的比特(Bit)所代替。與此相對的是LZ77或者LZ78等數據壓縮方法，在這些方法中原文的一段字母列被其它字母取代。
基本介紹
- 中文名：熵編碼法
- 學科：電子工程
技術介紹,編碼,模型,靜態模型,動態模型,模型度,
技術介紹
熵編碼法是一種進行無損數據壓縮的技術，在這個技術中一段文字中的每個字母被一段不同長度的比特(Bit)所代替。與此相對的是LZ77或者LZ78等數據壓縮方法，在這些方法中原文的一段字母列被其它字母取代。
要使得所有的字母可以在壓縮後互相區別需要一定數量的比特，因此每個字母被取代的比特數不能無限小。
每個字母按照其出現的可能性所獲得的最佳比特數取決於熵。
編碼
使用長度不同的比特串對字母進行編碼有一定的困難。尤其是，幾乎所有幾率的熵都是一個有理數。
使用整數比特(bit)
哈夫曼編碼建議了一種將比特進位成整數的算法，但這個算法在特定情況下無法達到最佳結果。為此有人加以改進，提供最佳整數比特數。這個算法使用二叉樹來設立一個編碼。這個二叉樹的終端節點代表被編碼的字母，根節點代表使用的比特。
除這個對每個要編碼的數據產生一個特別的表格的方法外還有使用固定的編碼表的方法。比如加入要編碼的數據中符號出現的機率符合一定的規則的話就可以使用特別的變長編碼表。這樣的編碼表具有一定的係數來使得它適應實際的字母出現機率。
模型
要確定每個字母的比特數算法需要儘可能精確地知道每個字母的出現機率。模型的任務是提供這個數據。模型的預言越好壓縮的結果就越好。此外模型必須在壓縮和恢復時提出同樣的數據。在歷史上有許多不同的模型。
靜態模型
靜態模型在壓縮前對整個文字進行分析計算每個字母的機率。這個計算結果用於整個文字上。
優點
編碼表只需計算一次，因此編碼速度高
除在解碼時所需要的機率值外結果肯定不比原文長
缺點
計算的機率必須附加在編碼後的文字上，這使得整個結果加長
計算的機率是整個文字的機率，因此無法對部分地區的有序數列進行最佳化
動態模型
在這個模型里機率隨編碼過程而不斷變化。多種算法可以達到這個目的：
前向動態：機率按照已經被編碼的字母來計算，每次一個字母被編碼後它的機率就增高
反向動態：在編碼前計算每個字母在剩下的還未編碼的部分的機率。隨著編碼的進行最後越來越多的字母不再出現，它們的機率成為0，而剩下的字母的機率升高，為它們編碼的比特數降低。壓縮率不斷增高，以至於最後一個字母只需要0比特來編碼
優點
模型按照不同部位的特殊性最佳化
在前向模型中機率數據不需要輸送
缺點
每個字母被處理後機率要重算，因此比較慢
計算出來的機率與實際的機率不一樣，在最壞狀態下壓縮的數據比實際原文還要長
一般在動態模型中不使用機率，而使用每個字母出現的次數。
除上述的前向和反向模型外還有其它的動態模型計算方法。
比如在前向模型中可以不時減半出現過的字母的次數來降低一開始的字母的影響力。
對於尚未出現過的字母的處理方法也有許多不同的手段：比如假設每個字母正好出現一次，這樣所有的字母均可被編碼。
模型度
模型度說明模型顧及歷史上多少個字母。比如模型度0說明模型顧及整個原文。模型度1說明模型顧及原文中的上一個字母並不斷改變其機率。模型度可以無限高，但是對於大的原文來說模型度越高其需要的計算記憶體也越多。
