Exercise 2.70 · 习题

Exercise 2.70: The following eight-symbol
alphabet with associated relative frequencies was designed to efficiently
encode the lyrics of 1950s rock songs. (Note that the “symbols” of an
“alphabet” need not be individual letters.)

A 2 NA 16
BOOM 1 SHA 3
GET 2 YIP 9
JOB 2 WAH 1

Use generate-huffman-tree (Exercise 2.69) to generate a
corresponding Huffman tree, and use encode (Exercise 2.68) to
encode the following message:

Get a job
Sha na na na na na na na na

Get a job
Sha na na na na na na na na

Wah yip yip yip yip
yip yip yip yip yip
Sha boom

How many bits are required for the encoding? What is the smallest number of

bits that would be needed to encode this song if we used a fixed-length code

for the eight-symbol alphabet?

练习 2.70：以下八个符号的字母表及其相对频率，是为高效编码 1950 年代摇滚歌曲歌词而设计的。（注意，“字母表”的“符号”不必是单个字母。）

A 2 NA 16
BOOM 1 SHA 3
GET 2 YIP 9
JOB 2 WAH 1

用 generate-huffman-tree（练习 2.69）生成对应的哈夫曼树，并用 encode（练习 2.68）对以下消息编码：

Get a job
Sha na na na na na na na na

Get a job
Sha na na na na na na na na

Wah yip yip yip yip
yip yip yip yip yip
Sha boom

编码共需多少位？如果用固定长度编码处理这个八符号字母表，编码这首歌最少需要多少位？