熵編碼法

维基百科，自由的百科全书

熵編碼法是一种进行无损失数据压缩的技术，在这个技术中一段文字中的每个字母被一段不同长度的比特所代替。与此相对的是LZ77或者LZ78等数据压缩方法，在这些方法中原文的一段字母列被其它字母取代。

要使得所有的字母可以在压缩后互相区别需要一定数量的比特，因此每个字母被取代的比特数不能无限小。

每个字母按照其出现的可能性所获得的最佳比特数取决于熵。

一般熵編碼器与其它编码器联合使用。比如LHA首先使用LZ编码，然后将其结果进行熵編碼。Zip和Bzip的最后一级编码也是熵編碼。

[编辑] 编码

使用不同长度的比特来对字母进行编码造成一定的困难，尤其是因为对几乎所有几率的熵是一个有理数。

[编辑] 使用整数比特

哈夫曼编码建议了一种将比特数进位成整数的算法，但这个算法在一定情况下达不到最佳结果。为此有人对这个算法进行改进，使得它总是能够提供最佳整数比特数。这个算法使用二叉树来设立一个编码。这个二叉树的终端节点代表被编码的字母，根节点代表使用的比特。

除这个对每个要编码的数据产生一个特别的表格的方法外还有使用固定的编码表的方法。比如加入要编码的数据中符号出现的几率符合一定的规则的话就可以使用特别的变长编码表。这样的编码表具有一定的系数来使得它适应实际的字母出现几率。

[编辑] 改进

使用整数比特的方法往往获不得使用熵计算的比特数因此其压缩不最佳。

比如字母列由两个不同的字母组成，其中一个字母的可能性是 $p(A) = 0,75$ ，另一个字母的可能性是 $p(B) = 0,25$ 。以上算法的结果是每个字母应该用一个比特来代表，因此其结果的比特数与字母数相同。

最佳熵編碼器应该为第一个字母使用 $-\log_2(0{,}75)\approx 0{,}41$ 个比特，为第二个字母使用 $- log 2 (0,25) = 2$ 个比特，因此整个结果是每个字母平均使用 $-0{,}75*\log_2(0{,}75)-0{,}25*\log_2(0{,}25)\approx 0.81$ 个比特。

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

[编辑] 模型

要确定每个字母的比特数算法需要尽可能精确地知道每个字母的出现几率。模型的任务是提供这个数据。模型的预言越好压缩的结果就越好。此外模型必须在压缩和恢复时提出同样的数据。在历史上有许多不同的模型。

[编辑] 静态模型

静态模型在压缩前对整个文字进行分析计算每个字母的几率。这个计算结果用于整个文字上。

优点
- 编码表只需计算一次，因此编码速度高
- 除在解码时所需要的几率值外结果肯定不比原文长
缺点
- 计算的几率必须附加在编码后的文字上，这使得整个结果加长
- 计算的几率是整个文字的几率，因此无法对部分地区的特殊纪律进行优化

[编辑] 动态模型

在这个模型里几率随编码过程而不断变化。多种算法可以达到这个目的：

前向动态：几率按照已经被编码的字母来计算，每次一个字母被编码后它的纪律就增高
反向动态：在编码前计算每个字母在剩下的还未编码的部分的几率。随着编码的进行最后越来越多的字母不再出现，它们的几率成为0，而剩下的字母的几率升高，为它们编码的比特数降低。压缩率不端增高，以至于最后一个字母只需要0比特来编码
优点
- 模型按照不同部位的特殊性优化
- 在前向模型中几率数据不需要输送
缺点
- 每个字母被处理后几率要重算，因此比较慢
- 计算出来的几率与实际的几率不一样，在最坏状态下压缩的数据比实际原文还要长

一般在动态模型中不使用几率，而使用每个字母出现的次数。

除上述的前向和反向模型外还有其它的动态模型计算方法。

比如在前向模型中可以不时减半出现过的字母的次数来降低一开始的字母的影响力。

对于尚未出现过的字母的处理方法也有许多不同的手段：比如假设每个字母正好出现一次，这样所有的字母均可被编码。

[编辑] 模型度

模型度说明模型顾及历史上多少个字母。比如模型度0说明模型顾及整个原文。模型度1说明模型顾及原文中的上一个字母并不断改变其几率。模型度可以无限高，但是对于大的原文来说模型度越高其需要的计算内存也越多。

来自“http://zh.wikipedia.org../../../%E7%86%B5/%E7%B7%A8/%E7%A2%BC/%E7%86%B5%E7%B7%A8%E7%A2%BC%E6%B3%95.html”

页面分类: 熵 | 无损压缩算法