用于无损压缩的Huffman编码
提问于 2011-04-15 03:57:39
我真的需要帮助霍夫曼编码的无损压缩。我有一个考试即将到来，需要理解这一点，谁知道容易教程，以理解这一点，或谁可以解释。
考试中的问题很可能是：
假设字母表为A，B，C，已知概率分布为P(A)=0.6，P(B)=0.2，P(C)=0.2。为了简单起见，我们还假设编码器和解码器都知道消息的长度总是3，所以不需要终止符。
- 通过Huffman编码编码消息ACB需要多少位？您需要为每个符号提供Huffman树和Huffman代码。(3分)
- 通过算术编码对消息ACB进行编码需要多少位？您需要提供编码过程的详细信息。(3分)
- 利用上述结果，讨论了算术编码相对于Huffman编码的优越性。(1标记)
答案：
- 哈夫曼代码:A-1，B-01，C-00.编码结果为10001，因此需要5位。(3分)
- 算术编码的编码过程:符号低、高范围、0.01.0A0.00.6C、0.480.60.12B、0.552、0.576、0.024最后二进制码字为0.1001，即0.5625。因此，需要4位。(3分)
- 在Huffman编码中，每个符号的码字长度必须是整数。但是在算术编码中它可以是分数的。因此，算术编码通常比Huffman编码更有效，如上面所示。(1标记)
回答 3
Stack Overflow用户
发布于 2011-04-15 07:01:39
Stack Overflow用户
发布于 2011-12-07 09:43:33
Huffman树是一种二叉树，其节点表示流中分布最高的值在根附近被压缩，而值的分布越来越远离根，从而允许以较短的位字符串编码更多的公共值，而在较长的字符串中编码较少的公共值。
赫夫曼树的构造如下：
- 在源流中构建一个实体表，其中包含它们的分布。
- 选择表中具有最低分布的两个条目。
- 从这两个条目中创建一个树节点。
- 从表中删除刚才使用的条目。
- 向表中添加一个新条目，将刚刚删除的节点以及树节点的组合分布添加到表中。
- 如果表中还有多个条目，请转到步骤2。
- 表中留下的条目是根。
Stack Overflow用户
发布于 2011-12-07 09:16:01
基本的huffmann实现可以很好。但是，如果您是从头开始构建的，您可能需要工具箱中的其他一个以上的数据结构来简化工作，比如minHeap和位向量。编码和解码的基本算法非常简单。没有与算术编码相比较的信息。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/5676353
复制相关文章
腾讯云开发者
