无损压缩的霍夫曼编码
我真的需要有关无损压缩的霍夫曼编码的帮助。我即将进行考试，需要了解这一点，有谁知道可以理解这一点的简单教程，或者有人可以解释一下。
考试中的问题很可能是：
假设字母表是[A,B,C]，已知的概率分布是P(A)=0.6， P(B)=0.2并且P(C)=0.2。为了简单起见，我们还假设编码器和解码器都知道 消息的长度始终为 3，因此不需要终止符。
通过霍夫曼编码对消息 ACB 进行编码需要多少位？你需要 提供每个符号的霍夫曼树和霍夫曼代码。 (3分)
通过算术编码对消息 ACB 进行编码需要多少位？你需要 提供编码过程的详细信息。 (3 分)
利用上述结果，讨论算术编码相对于霍夫曼编码的优点。 (1分)
答案：
霍夫曼代码：A - 1、B - 01、C - 00。 编码结果为10001，因此需要5位。 （3 分）
算术编码的编码过程： 符号 低 高范围 0.0 1.0 1.0 0.0 0.6 0.6 0.48 0.6 0.12 乙 0.552 0.576 0.024 最终的二进制码字是0.1001，也就是0.5625。因此需要4位。 （3分）
在霍夫曼编码中，每个符号的码字长度必须是整数。但它 在算术编码中可以是分数。因此算术编码通常更有效 与哈夫曼编码相比，如上结果所示。 (1分)
I really need help with Huffman Coding for Lossless compression. I have an exam coming up and need to understand this, does anyone know of easy tutorials made to understand this, or could someone explain.
The questions in the exam are likely to be:
Suppose the alphabet is [A, B, C], and the known probability distribution is P(A)=0.6,
P(B)=0.2 and P(C)=0.2. For simplicity, let’s also assume that both encoder and decoder know
that the length of the messages is always 3, so there is no need for a terminator.
How many bits are needed to encode the message ACB by Huffman Coding? You need to
provide the Huffman tree and Huffman code for each symbol. (3 marks)How many bits are needed to encode the message ACB by Arithmetic Coding? You need to
provide details of the encoding process. (3 marks)Using the above results, discuss the advantage of Arithmetic Coding over Huffman coding.
(1 mark)
Answers:
Huffman Code: A - 1, B - 01, C - 00.
The encoding result is 10001, so 5 bits are needed. (3 marks)The encoding process of Arithmetic Coding:
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
The final binary codeword is 0.1001, which is 0.5625. Therefore 4 bits are needed. (3 marks)In Huffman Coding, the length of the codeword for each symbol has to be an integer. But it
can be fractional in Arithmetic Coding. Therefore Arithmetic Coding is often more efficient
than Huffman Coding, as the results shown above. (1 mark)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
http://en.wikipedia.org/wiki/Huffman_coding
如果您查看树（顶部右）您会看到每个父节点都是其下面两个节点的总和。节点处的值是字母的频率。二进制序列中的每一位都是树中的右/左分支。
这有帮助吗？
我对算术编码一无所知，但它看起来很聪明。
http://en.wikipedia.org/wiki/Huffman_coding
If you look at the tree (top right) you'll see that each parent node is the sum of the two below it. The values at the nodes are the frequencies of the letters. Each bit in the binary sequence is a right/left branch in the tree.
Does that help?
I don't really have a clue about Arithmetic coding, but it looks quite clever.
哈夫曼树是一棵二叉树，其节点代表在根附近被压缩的流中分布最高的值，以及距离根越来越远分布递减的值，从而允许用更短的位对更常见的值进行编码字符串，而不太常见的值则编码为较长的字符串。
霍夫曼树的构造如下：
A Huffman tree is a binary tree with the nodes representing the values with the highest distribution in the stream being compressed near the root and the values with decreasing distribution further and further away from the root, thus allowing more common values to be encoded in shorter bit strings while less common values are encoded in longer strings.
A Huffman tree is constructed as follows:
基本的霍夫曼实现就可以了。但是，如果您从头开始构建，您的工具箱中可能需要超过 1 个其他数据结构以使事情变得更容易，例如 minHeap 和位向量。编码和解码的基本算法非常简单。没有与算术编码比较的信息。
实现示例
Basic huffmann implementation can be quite ok. But, if you are building from scratch you may need more than 1 other datastructure in your toolbox to make things easier such as a minHeap and a bit vector. The basic algorithms for encoding and decoding are pretty simple. No info on comparison with arithmetic coding.
An implementation example