1

I am doing a project where I compare different types of Text compression methods such as Huffman and Arithmetic for both static and adaptive form. I make a probability table for both using the number of occurrence of each letter in the text. Now, for adaptive form, the receiver does not need the Probability table but for the static form, we need to transmit this probability table as well to the receiver for decoding the message. Now this storing of the table will need some extra bits, which should be taken into account while comparing.

So my question here is:

  1. What is the best solution for storing the probability table (in a file).
  2. What is the minimum number of bits required to do that? (I know it depends on the text, but is there some way to find the minimum bits required to store the table).

Thank you very much.

4

3 回答 3

0

从概率中，您将代码长度分配给符号。为了创建代码，接收器需要一个元组列表：（位计数，符号计数），然后是按顺序分配给代码的符号。现在您可以尝试如何对它们进行编码。

对符号列表进行编码可以使用这样一个事实，即对于传输的每个符号，跟随符号所需的位数都会减少。尽早指定使用（例如）8 位符号的某些子集的选项可以在这里提供帮助。随着代码字越来越长，对一系列符号进行编码可能会很方便，而不是传输每个符号——也许可以用一种方式来表达一个符号，而不是几个符号，其中“孔”可以表示为一些位数取决于运行的长度 - 或起始符号，长度和位向量（注意表示长度的位数取决于起始符号和剩余符号的数量，并且有无需为范围内的第一个和最后一个发送一点！）

霍夫曼码表的编码本身就是一个完整的游戏。然后对于短消息，该表可能是一个严重的开销......在这种情况下，（少量）常用的表可能会提供更好的压缩。

您还可以对每个符号的代码长度使用 Huffman 编码，并按符号顺序发送它们。重复计数机制及其 Huffman 可以在这里提供帮助，以及跳过未使用符号（即代码长度为零的符号）的运行的方法。当然，您可以添加一级表来指定此编码！

另一种方法是多个位向量，每个码字长度一个向量。从具有最多符号的代码字长度开始，发出长度和位向量，然后是具有较小位向量的下一个人口最多的代码长度......等等。同样，对运行和范围进行编码的方法可以减少所需的位数，并且随着您的继续，这些所需的位数也会减少。

问题是，对代码表大小的比较有多敏感？显然，如果它非常敏感，那么调查应用狡猾可以做什么很重要。但是任何给定方案的有效性将取决于它与被压缩的“典型”数据的匹配程度。

于 2014-07-27T00:32:52.217 回答
-1

传达 0 阶表（即只有单个标记且没有前瞻表）的一种常见方法是简单地将所有可能的符号以频率递减的顺序添加到前面。通常不需要存储概率，因为编码只需要有序的符号集，而不需要它们的实际概率。

对于编码 8 位令牌的压缩方案，并假设所有令牌至少在理论上都是可能的，这将意味着 256 字节的开销。对于只有字节子集可能的情况（例如，仅由大写字母和数字组成的消息），该表当然会更小。

于 2014-07-26T19:31:06.847 回答
-1

有多种方法可以存储 Huffman 或算术解压缩器所需的概率信息，以便将压缩信息解码为原始明文（精确副本）。

正如 Mark Adler 在相关问题中提到的（在 Huffman 压缩后将代码表存储在压缩文件中并从该表中构建解压缩树），

您不需要传输概率或树。所有 [Huffman] 解码器需要的是分配给每个符号的比特数，以及编码器和解码器都同意的将比特值分配给每个符号的规范方法。请参阅规范霍夫曼代码。

我假设您使用的是面向字节的霍夫曼代码，每个压缩代码都解码为 256 个可能的字节之一。

也许存储这些位长度的最简单方法是一个包含 256 个位长度的详尽表，每个可能的字节都有一个。例如，表中的第 65 个条目给出了字母“A”（第 65 个 ASCII 字符）的位长，它可能是 1（当 A 非常常见时）到可能是 12（当 A 非常罕见时），或 0（表示 A 在此文本中从未出现）。每个长度很容易放入 1 个字节，因此该表的长度为 256 个字节。

（几乎总是最大长度为 15 位或更少，因此通常每个长度都可以轻松放入半个字节，给出一个总是正好 128 个字节长的表——但处理欺骗霍夫曼的“病态”数据文件算法为一些明文字节分配一个超过 15 位的符号可能会很棘手。一些系统专门检查最大长度是否超过 15 位，并人为地更改霍夫曼树以强制所有长度最多为 15 位——有时称为受限深度霍夫曼树或长度受限霍夫曼编码。同样，JPEG 标准将霍夫曼代码长度限制为 16 位）。

更紧凑（并且更难以描述）的方法用于存储JPEG 图像中的 4 个 Huffman 位长表，以及在可变长度表中的 DEFLATE 流中使用的许多 Huffman 表，其长度随特定数据而变化——但它们都首先将要存储的概率信息减少到符号的比特长度。（也许您可以只使用 DEFLATE 实现，而不是从头开始编写和调试一些东西？）

我的理解是，算术编码通常使用比霍夫曼编码更高精度的概率信息，至少对于最常见的符号是这样。请告诉我您是否找到一种有效的方式将该信息传输给接收者。

于 2019-07-31T17:34:26.797 回答