编码

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

使用整数比特（bit）

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

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

改进

使用整数比特的方法往往无法获得使用熵计算的比特数，因此其压缩并非一定最佳。

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

但扩展取样位数可以稍微弥补该破绽：上例的 p ( A A ) = 0 . 5625 {\displaystyle \mathrm {p} (AA)=0{.}5625} 、 p ( A B ) = 0 . 1875 {\displaystyle \mathrm {p} (AB)=0{.}1875} 、 p ( B A ) = 0 . 1875 {\displaystyle \mathrm {p} (BA)=0{.}1875} 、 p ( B B ) = 0 . 0625 {\displaystyle \mathrm {p} (BB)=0{.}0625} ，以霍夫曼编码算法得结果为：每两个字母平均用 ( 0.5625 ∗ ∗ --> 1 + 0.1875 ∗ ∗ --> 2 + 0.1875 ∗ ∗ --> 3 + 0.0625 ∗ ∗ --> 3 ) = 1.6875 {\displaystyle (0.5625*1+0.1875*2+0.1875*3+0.0625*3)=1.6875} 个比特，即平均每个字母用0.84375个比特来代表，向最佳熵值踏近了一步。

最佳熵编码器应该为第一个字母使用 − − --> log 2 ⁡ ⁡ --> ( 0 . 75 ) ≈ ≈ --> 0 . 41 {\displaystyle -\log _{2}(0{.}75)\approx 0{.}41} 个比特，为第二个字母使用 − − --> log 2 ⁡ ⁡ --> ( 0 . 25 ) = 2 {\displaystyle -\log _{2}(0{.}25)=2} 个比特，因此整个结果是每个字母平均使用 − − --> 0 . 75 ∗ ∗ --> log 2 ⁡ ⁡ --> ( 0 . 75 ) − − --> 0 . 25 ∗ ∗ --> log 2 ⁡ ⁡ --> ( 0 . 25 ) ≈ ≈ --> 0.81 {\displaystyle -0{.}75*\log _{2}(0{.}75)-0{.}25*\log _{2}(0{.}25)\approx 0.81} 个比特。

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

模型

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

静态模型

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

优点

缺点

动态模型

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

前向动态：概率按照已经被编码的字母来计算，每次一个字母被编码后它的概率就增高

反向动态：在编码前计算每个字母在剩下的还未编码的部分的概率。随着编码的进行最后越来越多的字母不再出现，它们的概率成为0，而剩下的字母的概率升高，为它们编码的比特数降低。压缩率不断增高，以至于最后一个字母只需要0比特来编码

优点

缺点

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

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

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

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

模型度

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

熵作为相似性的量度

除了使用熵编码作为压缩数字数据一种方法外，熵编码器也可以用来测量数据流和已经存在的类的数据之间的相似程度。这是通过对每类数据产生一个熵编码器/压缩器；通过将未压缩的数据提供给每个压缩机，据该压缩机产生的最佳压缩分类。具有最佳压缩率的编码器可能是用与未知数据最相似的数据训练的编码器。

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。