compression - 霍夫曼树是如何传播的？

Question

我试图了解 DEFLATE 算法的工作原理。我找到了 UC Davis 发布的这份文件。我不明白它谈论霍夫曼树如何传播的部分

可能要理解 DEFLATE 规范中最棘手的部分是当数据用专门的树压缩时，树与数据一起被编码的方式。

正如前面所讨论的，这些树是通过它们的码长传输的。代码长度全部放在 0 到 15 之间的数字序列中（创建的霍夫曼树必须保持不超过 15 的代码长度；这是棘手的部分，而不是限制元素顺序的部分） .

并非所有元素都必须指定代码长度；如果字母表的最后一个元素的代码长度为 0，那么它们可以并且可能应该被忽略。将传输两个字母表中每个字母表中的元素数量，因此修剪后的字母表组合成一个序列。

首先，codelength到底是什么意思，为什么可以为0？

我也不太了解运行长度压缩，他们在最后一段之后提到了它。

一旦这个代码长度序列被组装起来，它就会被一种称为运行长度压缩的形式压缩。当一行中的多个元素具有相同的码长（通常为 0）时，可以使用特殊符号来指示具有该码长的元素的数量。我们的序列现在是 0 到 18 之间的数字序列（可能有额外的位形成整数来修改基值，就像长度和距离代码的情况一样）。

为这个 0-18 的字母表创建了一个 Huffman 树。叹。0-18 码和额外位的序列是用霍夫曼码代替 0-18 元素准备的。

标签： compressionhuffman-codedeflate

Answer 1

代码长度是该符号的代码长度（以位为单位）。

零码长意味着该符号不会出现在压缩数据中，因此该符号没有代码。

在这种情况下，游程编码意味着重复码长的序列，例如“7、7、7、7、7、7”，被“7，重复最后一个长度5次”代替。