gpt-3.5-turbo-0301· OpenAI
WildChat-4.8M (AI2)
假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字母构成,他们在电文中出现的频度分别为{0.31,0.16,0.10,0.08,0.11,0.20,0.04}…
- User
假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字母构成,他们在电文中出现的频度分别为{0.31,0.16,0.10,0.08,0.11,0.20,0.04}
1.请为这7个字母设置哈夫曼编码 2. 整个哈夫曼树的WPL是多少 3. 对这7个字母进行等长编码,至少需要几位二进制数,哈夫曼编码比等长编码使电文总长度压缩了多少?
- Assistant
- 根据哈夫曼编码构造规则,首先将出现频率最小的两个字母合并,得到新的频率为0.04+0.08=0.12的节点。然后再将出现频率最小的两个节点合并,得到频率为0.12+0.10=0.22的节点,以此类推,直到将所有节点合并成一个根节点。最后将左子树标记为0,右子树标记为1,得到哈夫曼编码:
a:10 b:110 c:1110 d:11110 e:011 f:00 g:11111
-
整个哈夫曼树的WPL是: 0.312 + 0.163 + 0.104 + 0.085 + 0.113 + 0.202 + 0.04*5 = 2.36
-
等长编码要用log2(7)≈2.81位二进制数。所以至少需要3位二进制数来表示每个字母。而哈夫曼编码的总长度为: 0.312 + 0.163 + 0.104 + 0.085 + 0.113 + 0.202 + 0.04*5 = 2.36 每个字母平均需要 2.36/7 = 0.337ms,相对等长编码来说压缩了: (3-0.337)/3 ≈ 0.887,即约为 88.7%