乐正

Actions speak louder than words.

Sicp-ex2-71

问题

假定我们有一棵n个符号的字母表的Huffman树,其中各符号的相对频度分别是$1, 2, 4, \cdots, 2^{n-1}$。请对$n=5$和$n=10$勾勒出有关的树的样子。对于这样的树(对于一般的n), 编码出现最频繁的符号用多少个二进制位?最不频繁的符号呢?

解答

当$n=5$时,各符号的相对频度分别是1, 2, 4, 8 和 16。两个元素频度低的作为左子树、 频度高的作为右子树,记为(1 2)。这时,需要组合的符号分别是(1 2), 4, 8, 16。 再取前两个元素组成新的树,((1 2) 4)。以此类推,最终的树是((((1 2) 4) 8) 16)

同理,当$n=10$时,组成的树是类似的。

其中,编码出现最频繁的符号占用1个二进制位;最不频繁的符号占用$n-1$个二进制位。

draft

« sicp-ex2-70 sicp-ex2-72 »

Comments