Question

假设用于通信的电文仅由1234这4个字符组成，字符出现的频率为1：0.5、2：0.1、3：0.3、4：0.1……

假设用于通信的电文仅由1234这4个字符组成，字符出现的频率为1：0.5、2：0.1、3：0.3、4：0.1，请回答以下问题。
（1）如果字符编码为等长编码，则给出一种编码方案
（2）请依据字符出现的频率大小，画出哈夫曼树并给出编码方案
请详细一点，讲一下为什么，谢谢！

Answer 1

长编码编码方案：
假设我们采用长度不同的编码方案，可以将1编码为0，2编码为10，3编码为110，4编码为111。这种编码方案被称为长编码，虽然编码方案简单，但编码长度不一，导致编码效率不高。例如，对于电文1234，采用长编码进行编码后，其编码长度为7，即000110111。
哈夫曼编码方案：
为了提高编码效率，可以采用哈夫曼编码来进行编码。首先，需要根据字符出现的频率大小建立哈夫曼树，然后根据哈夫曼树给字符分配编码。哈夫曼树是一种二叉树，每个叶子节点代表一个字符，节点的权值表示该字符出现的频率大小。
建立哈夫曼树的步骤如下：
将字符按照频率从小到大排序，每个字符可以看作一个权值为该字符频率的节点；
选择两个权值最小的节点作为左右孩子节点，将它们的权值相加得到一个新节点的权值；
将新节点加入到排序后的节点序列中，重新排序；
重复步骤2-3，直到序列中只剩下一个节点，这个节点就是哈夫曼树的根节点。
根据题目中的字符出现频率，可以建立哈夫曼树，如下图所示：
1:0.5
/ \
2:0.1 3:0.3
/ \
4:0.1 x
从哈夫曼树的根节点到叶子节点的路径可以表示字符的编码，例如从根节点到1的路径为0，从根节点到2的路径为10，从根节点到3的路径为11，从根节点到4的路径为110。这种编码方式被称为哈夫曼编码，它的编码长度为1+2+2+3=8。
因为哈夫曼编码满足“无前缀性”，即任意一个字符的编码都不是另一个字符编码的前缀，所以可以方便地对编码进行解码。同时，由于哈夫曼编码满足“最优编码”，即整个电文的编码长度最短，所以也可以实现高效的压缩。

Answer 2

平均码长=(4*0.09+3*0.15+4*0.04+4*0.07+2*0.28+4*0.08+2*0.21+3*0.18)/1.1=2.81哈夫曼树及每个字符