c - 哈夫曼编码表在实践中是如何构建的？

Question

我的问题很具体。看得出来哈夫曼编码的理论很容易理解。但是，它似乎创建了通常不与字节边界对齐的代码。我遇到的教程中尚未涉及缓解此特定问题的实用方法。

有两个问题:

(1) 一旦文件被编码，生成的霍夫曼代码文件的文件末尾可能不会在字节边界对齐。我们怎么知道我们已经到达压缩文件中霍夫曼编码数据的末尾？

(2) 假设文件中包含一个huffman表来帮助解压，那么在实际中又遇到字节边界不对齐时，如何创建这样的表？符号本身可能是 8 位或 16 位。然而，霍夫曼码可以是任意位数。现在，如果我们为每个代码包含一个霍夫曼代码，我们还必须包含它的位数，以便解码器可以使用霍夫曼表来创建二叉树或其他一些数据结构以帮助解压缩。

霍夫曼编码和算术编码似乎在很多压缩系统中使用，因此这个问题不断出现。

我试图了解这是如何在 JPEG 中完成的，并将使用 FPGA 中的 Nios II 软核处理器在 C 中构建编码器，以将 JPEG 文件从相机保存到 SD 卡中。

Answer 1

1. 附加符号被定义为结束代码。遇到该代码时，您已到达流的末尾。除非后面有其他某种比特流，否则通常所做的是丢弃最后一个字节中的所有剩余比特以转到下一个字节边界。

2. 根据压缩代码描述的重要性，有多种不同复杂程度的方法。您可以通过一种方式阅读 RFC 1951 中的 deflate 描述，以及 RFC 7932 中的 brotli 描述。在这两种情况下，代码本身都不会被发送。而是发送每个符号的代码长度，并且代码本身是根据长度和符号顺序规范地构造的。在 deflate 中，为每个符号发送长度，为未编码的符号发送长度为零。这一系列长度以游程长度编码，然后本身是霍夫曼编码。 用于解码代码长度的霍夫曼代码首先发送，它使用每个长度 (3) 的固定位数发送，并再次规范地构造。 (查找 Canonical Huffman 代码。)当不使用预定义的 Huffman 代码时，JPEG 还有另一种编码代码长度的方法。