熵编码查看源代码讨论查看历史

来自 孔夫子旧书网 的图片

熵编码是一个科技名词。

现代汉字是指楷化后的汉字正楷字形，包括繁体字和简体字。现代汉字即从甲骨文、金文、籀文、篆书，至隶书、草书、楷书、行书等演变而来。汉字为汉民族先民发明创制并作改进，是维系汉族各方言区不可或缺的纽带。现存最早可识的汉字是约公元前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个位元。

使用算术编码可以改善这个结果，使得原资讯按照熵最佳来编码。