问题标签 [huffman-code]

假设 A 是一个数组，其中 A[0] 保存字母表中第 0 个字母的频率。

计算代码长度的最有效（*）方法是什么？不确定，但我猜效率可能取决于内存使用或所需的步骤。

我感兴趣的是数组L，其中L[0]包含字母表中第 0 个字母的代码长度（位数），其中代码来自由 A 频率数组构建的规范哈夫曼树。

对于生成的字母表不是二进制的情况，霍夫曼编码树是否有一个简单的概括？例如，如果我想通过以三进制写出一些文本来压缩它，我仍然可以为我写出的每个字符建立一个无前缀编码系统。Huffman 构造的直接概括（使用 k-ary 树而不是二叉树）是否仍能正确有效地工作？或者这种结构是否会导致一种非常低效的编码方案？

我需要能够在大量压缩文件 (.txt) 中搜索文本。压缩可能会更改为其他内容，甚至成为专有的。我想避免解压缩所有文件并压缩（编码）搜索字符串并在压缩文件中搜索。这应该可以使用 Huffman 压缩和所有文件的相同码本。我不想重新发明轮子，所以.. 任何人都知道一个库可以做这样的事情，或者 Huffman 算法已经实现和测试，或者可能是一个更好的主意？

提前致谢

我真的需要 Huffman Coding for Lossless 压缩方面的帮助。我即将参加考试，需要理解这一点，有没有人知道为理解这一点而制作的简单教程，或者有人可以解释一下。

考试中的问题可能是：

假设字母表为[A, B, C]，已知概率分布为P(A)=0.6，P(B)=0.2，P(C)=0.2。为简单起见，我们还假设编码器和解码器都知道消息的长度始终为 3，因此不需要终止符。

1. 使用霍夫曼编码对消息 ACB 进行编码需要多少位？您需要为每个符号提供 Huffman 树和 Huffman 代码。(3 分)

2. 通过算术编码对消息 ACB 进行编码需要多少位？您需要提供编码过程的详细信息。(3 分)

3. 使用上述结果，讨论算术编码相对于霍夫曼编码的优势。(1 分)

答案：

1. 霍夫曼码：A - 1, B - 01, C - 00。编码结果是10001，所以需要5位。(3 分)

2. 算术编码的编码过程： Symbol Low high range 0.0 1.0 1.0 A 0.0 0.6 0.6 C 0.48 0.6 0.12 B 0.552 0.576 0.024 最终二进制码字为0.1001，即0.5625。因此需要 4 位。(3 分)

3. 在霍夫曼编码中，每个符号的码字长度必须是整数。但它在算术编码中可以是分数。因此，算术编码通常比霍夫曼编码更有效，如上图所示。(1 分)

我正在编写 Huffman 代码，我在其中导入一个文件，为每个字符生成 Huffman 代码，然后将二进制文件输出到文件中。要导入字符，我使用读取每个字符的扫描仪，将其放入具有读取字符值和频率为 1 的节点中。然后，将该节点添加到 PriorityQueue。由于 Node 类有一个 compareTo 方法，它只比较频率，我怎样才能实现一个比较器到这个特定的 PriorityQueue，在队列中排序时比较字符？提前致谢。

文字示例：字符队列应按如下方式排序：

以下是一些片段：

这是需要自定义比较器的 PriorityQueue：

这是我使用 HashMap 创建的新方法：

我知道有很多涉及霍夫曼代码的问题，包括我自己提出的另一个问题，但我想知道实际编码文本文件的最佳方法是什么。减压似乎微不足道；遍历树，在 0 处向左，在 1 处向右，打印字符。

但是，如何进行压缩？以某种方式将字符的位表示存储在树的节点中？每次遇到字符时都在树中搜索并跟踪步骤？以哪种方式编码有关系吗？

到目前为止，我有一个霍夫曼树，其中叶节点没有与之关联的二进制值。我的麻烦是将二进制值分配给树中的每个字符。

谢谢

我现在被这个问题困扰了几天。如何使用以下站点上指定的数据构建树：

http://www.impulseadventure.com/photo/jpeg-huffman-coding.html，在主题下：

JPEG 文件中的实际 DHT

我会在这里重新解释一下，

你有 ：

1. 带有长度的表（bytesvector）
2. 带有数据的表（也包括字节向量）

现在我想用这两个参数构建一个二叉树。每次从左到右填充相应长度的数据。你越深入树，你的长度就越长。长度从 1 到 16 不等。看看该站点，它应该会变得清晰。

现在我想在 Scheme/Racket 中制作这样一棵树，这样我就可以走到树前并为每个编码值构建一个表。

我脑海中的树看起来像：

下面的解释来自维基百科关于使用包合并的长度限制霍夫曼代码。我无法理解，我对此有一些疑问。

• 我们如何打包？
• 我们如何合并？
• 我们如何识别符号位串的长度？

令L为任何代码字允许具有的最大长度。令p ₁ , ..., p _n是要编码的字母表符号的频率。我们首先对符号进行排序，使p _i ≤ p _i +1。为每个符号创建L个硬币，面额为 2 ⁻¹，...，2 ^−<em>L，每个符号的钱币值p _i。使用 package-merge 算法选择面额总数为 n - 1 的最小钱币值的硬币集合。设h _i为钱币值p _{i的硬币数}选择。最佳长度限制霍夫曼码将使用长度为h _i的位串对符号i进行编码。”

我想用霍夫曼代码对每个文件进行编码。我找到了每个符号的比特长度（它的霍夫曼代码）。

是否可以在 Java 中将字符编码到文件中：是否有任何现有的类可以逐位读取和写入文件，而不是最小尺寸的 char？

你好！

任何人都可以从这个 Internet 站点说出如何解决霍夫曼算法中的问题（如果将所有部分放在一起）：

http://www.builderau.com.au/program/python/soa/Huffman-coding-in-Python/0,2000064084,339283616,00.htm

错误：

谢谢！