一个符号序列但三个字母的霍夫曼编码
Huffman coding for one-symbol sequence but three alphabets
我正在解决一本关于压缩的书中的练习，它说如果我们有字母表 [A,B,C] 和概率 P(A)=0.5,P(B)=0.4,P(C )=0.1 用霍夫曼和算术编码 BBB 需要多少位。
现在书上有一段说"BBB requires 6 bits with huffman but only 4 bits with arithmetic"，我已经验证算术需要4位，但不知道为什么霍夫曼需要6位。
我这样解决了 huffman 问题：
B(3)
P1(3)
EOF(0) B(3)
所以 B 只用一位编码!!
我想也许我应该像这样包括整个字母表：
A(0),C(0),B(3)
P1(0) B(3)
A(0) C(0)
P2(3)
P1(0) B(3)
A(0) C(0)
B 仍然需要 1 位（但是 A 和 C 需要 2 位，仍然没有 6 位！！）。
我做错了什么？
A 的概率比 B 高，所以 B 不能比 A 分配更少的比特。霍夫曼码给 B 两个比特，因此给 BBB 六个比特。
我想出来了，因为 P(B)=0.4 所以我们有 3 个字母，我们有 3*0.4=1.2 大约是 1，P(A)=0.5 和 3*0.5=1.5 介于1 和 2，P(C)=0.1 和 0.1*3=0.3 大约为 0。
因此，如果我们对它们进行排序，我们会得到：
A(1 或 2),B(1),C(0)
树是：
A(1 或 2) P1(1)
B(1) C(0)
P2（2 或 3）
A(1 或 2) P1(1)
B(1) C(0)
最后一个B需要2位所以BBB需要6位编码，问题解决:) .
我正在解决一本关于压缩的书中的练习，它说如果我们有字母表 [A,B,C] 和概率 P(A)=0.5,P(B)=0.4,P(C )=0.1 用霍夫曼和算术编码 BBB 需要多少位。
现在书上有一段说"BBB requires 6 bits with huffman but only 4 bits with arithmetic"，我已经验证算术需要4位，但不知道为什么霍夫曼需要6位。
我这样解决了 huffman 问题：
B(3)
P1(3)
EOF(0) B(3)
所以 B 只用一位编码!!
我想也许我应该像这样包括整个字母表：
A(0),C(0),B(3)
P1(0) B(3)
A(0) C(0)
P2(3)
P1(0) B(3)
A(0) C(0)
B 仍然需要 1 位（但是 A 和 C 需要 2 位，仍然没有 6 位！！）。
我做错了什么？
A 的概率比 B 高，所以 B 不能比 A 分配更少的比特。霍夫曼码给 B 两个比特，因此给 BBB 六个比特。
我想出来了，因为 P(B)=0.4 所以我们有 3 个字母，我们有 3*0.4=1.2 大约是 1，P(A)=0.5 和 3*0.5=1.5 介于1 和 2，P(C)=0.1 和 0.1*3=0.3 大约为 0。
因此，如果我们对它们进行排序，我们会得到：
A(1 或 2),B(1),C(0)
树是：
A(1 或 2) P1(1)
B(1) C(0)
P2（2 或 3）
A(1 或 2) P1(1)
B(1) C(0)
最后一个B需要2位所以BBB需要6位编码，问题解决:) .