我正在做一个项目，我比较不同类型的文本压缩方法，如霍夫曼和算术的静态和自适应形式。我使用文本中每个字母出现的次数为两者制作了一个概率表。现在，对于自适应形式，接收者不需要概率表，但对于静态形式，我们需要将这个概率表也传输给接收者以解码消息。现在，表的这种存储将需要一些额外的位，在比较时应该考虑到这一点。
我的问题是:
- 存储概率表(在文件中)的最佳解决方案是什么?
- 这样做所需的最小位数是多少?(我知道这取决于文本，但是否有某种方法可以找到存储表所需的最小位)。
非常感谢。
根据概率，为符号分配代码长度。为了创建代码，接收方需要一个元组列表:(位计数，符号计数)，后面是要分配给代码的符号顺序。现在您可以试试如何对它们进行编码。
对符号列表进行编码可以利用这样一个事实:每传输一个符号，后续符号所需的比特数就会减少。在这里，尽早指定使用某些(例如)8位符号子集的选项会有所帮助。码字变长了,它可能是方便的有一个编码的符号,而不是发送每一个用跑步的方式来表达——也许少几个符号,表达的"洞"可以在一些的比特数取决于运行的长度,或者开始的象征,长度和向量(注意表达的比特数长度取决于开始符号和符号的数量,并且不需要为范围内的第一个和最后一个发送位!)
霍夫曼码表的编码本身就是一个完整的博弈。然后，对于短消息，表可能是一个严重的开销……在这种情况下，(少量)常用的表可能会提供更好的压缩。
您还可以对每个符号的代码长度使用霍夫曼编码，并按符号顺序发送这些编码。一个重复计数机制，其霍夫曼在这里可以帮助，以及一种跳过未使用符号(即零码长的符号)运行的方法。当然，您可以添加一个第一级表来指定这个的编码!
另一种方法是若干位向量，每个码字长度对应一个向量。从具有最多符号的码字长度开始，发出长度和位向量，然后是具有较小位向量的下一个最多代码长度…等等......同样，对运行和范围进行编码的方法可以减少所需的位数，并且随着操作的进行，所需的位数也会减少。
问题是，比较代码表的大小有多敏感?显然，如果它非常敏感，那么调查运用狡猾可以做些什么是很重要的。但是，任何给定方案的有效性都将取决于它对被压缩的"典型"数据的适应程度。
传递0阶表(即只有单个标记且没有预读的表)的一种常用方法是简单地按频率递减顺序添加所有可能的符号。概率通常不需要存储，因为编码只需要有序的符号集合，而不需要它们的实际概率。
对于编码8位令牌的压缩方案，并假设所有令牌至少在理论上是可能的，这将意味着256字节的开销。对于只有一个字节子集是可能的情况(例如，仅由大写字母和数字组成的消息)，表当然要更小。
有多种方法可以存储霍夫曼或算术解压缩器需要的概率信息，以便将压缩信息解码为原始明文(精确副本)。
正如Mark Adler在一个相关问题中提到的(将代码表存储在霍夫曼压缩后的压缩文件中，并从该表中构建解压缩树)，
你不需要传递概率或树。所有的[霍夫曼]解码器需要的是分配给每个符号的比特数，以及a将位值分配给同意的每个符号的规范方法由编码器和解码器组成。参见规范霍夫曼代码。
我假设你正在使用面向字节的霍夫曼代码，每个压缩代码解码成256个可能的字节之一。
也许存储这些位长度的最简单方法是一个恰好256位长度的穷举表，每个可能的字节一个。例如，表中的第65个条目给出了字母"A"(第65个ASCII字符)的位长度，可能是1(当A非常常见时)到12(当A非常罕见时)，或者0(表示A从未出现在此文本中)。每个长度可以轻松地容纳1个字节，因此该表有256个字节长。(几乎总是最大长度为15位或更少，所以通常每个长度可以很容易地容纳到半个字节，给出一个总是正好128字节长的表——但是处理"病态"数据文件，欺骗霍夫曼算法将一些明文字节分配给超过15位的符号，可能会很棘手。)有些系统专门检查最大长度是否超过15位，并人为地改变霍夫曼树以强制所有长度最多为15位-有时称为约束深度霍夫曼树或长度限制霍夫曼编码。同样，JPEG标准将霍夫曼码长度限制为16位)。
更紧凑(更难以描述)的方法用于存储JPEG图像中的4个位长度的霍夫曼表和在可变长度表中使用的DEFLATE流中的许多霍夫曼表，其长度随特定数据而变化-但所有这些方法都首先将要存储的概率信息减少到仅存储符号的位长度。(也许您可以直接使用DEFLATE实现，而不是从头开始编写和调试一些东西?)
我的理解是，算术编码通常使用精度更高的概率信息，至少对于最常见的符号，比霍夫曼码。