0

我真的需要 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 分)

4

3 回答 3

2

http://en.wikipedia.org/wiki/Huffman_coding

如果您查看树（右上角），您会看到每个父节点都是其下方两个节点的总和。节点处的值是字母的频率。二进制序列中的每个位都是树中的右/左分支。

这有帮助吗？

我对算术编码一无所知，但它看起来很聪明。

于 2011-04-15T15:01:39.240 回答
1

霍夫曼树是一棵二叉树，其节点表示流中分布最高的值，在根附近被压缩，而在离根越远的地方越靠近分布的值越小，因此可以用更短的位对更常见的值进行编码字符串，而不太常见的值被编码为更长的字符串。

哈夫曼树的构造如下：

  1. 在源流中构建实体表及其分布。
  2. 选择表中分布最低的两个条目。
  3. 从这两个条目中创建一个树节点。
  4. 从表中删除刚刚使用的条目。
  5. 向表中添加一个新条目，其中包含刚刚删除的节点以及树节点的组合分布。
  6. 如果表格中还有多个条目，请转到步骤 2。
  7. 表中留下的条目是您的根。
于 2011-12-07T17:43:33.357 回答
0

基本的霍夫曼实现可以很好。但是，如果您是从头开始构建，您的工具箱中可能需要超过 1 个其他数据结构来使事情变得更容易，例如 minHeap 和位向量。编码和解码的基本算法非常简单。没有与算术编码比较的信息。

一个实现示例

于 2011-12-07T17:16:01.893 回答