熵編碼檢視原始碼討論檢視歷史

來自 孔夫子舊書網 的圖片

熵編碼是一個科技名詞。

現代漢字是指楷化後的漢字正楷字形，包括繁體字和簡體字。現代漢字即從甲骨文、金文、籀文、篆書，至隸書、草書、楷書、行書等演變而來。漢字為漢民族先民發明創製並作改進，是維繫漢族各方言區不可或缺的紐帶。現存最早可識的漢字是約公元前1300年殷商的甲骨文和稍後的金文， 再到秦朝的小篆 和隸書， 至漢魏隸書盛行，到了漢末隸書楷化為正楷，盛行於魏晉南北朝，至今通行。

名詞解釋

熵編碼即編碼過程中按熵原理不丟失任何信息的編碼。信息熵為信源的平均信息量（不確定性的度量）。常見的熵編碼有：香農(Shannon)編碼、哈夫曼(Huffman)編碼和算術編碼(arithmetic coding)。

研究背景

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

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

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

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

常見方案

常見的熵編碼有：香農(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個位元。

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