sicp每日一题[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   GET 2   SHA 3   WAH 1
BOOM 1   JOB 2   NA  16  YIP 9

Use generate-huffman-tree (Exercise 2.69) to generate a corresponding Huffmantree 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.68 和 2.69 的函数就行，但是我却遇到了好几个麻烦，第一个是大小写问题，我在生成霍夫曼树的时候，用的都是题目中默认的大写字母，但是要翻译的歌词却是既有大写又有小写，所以在 encode-symbol 函数的 (eq? symbol (symbol-leaf tree)) 这一步就会跳出，我尝试了好几个方法也没找到怎么解决，最后直接把歌词改成全大写了。解决了大小写问题，我又遇到了相同的提示，一步步调试之后终于发现了问题，我练习 2.68 的 encode-symbol 本身就有问题，改完之后终于成功了。最后就是统计了一下长度，如果使用固定长度的编码，那么每个“符号”至少需要3个字符，程序如下所示：

(define (encode-symbol symbol tree)
  (if (leaf? tree)
      (if (eq? symbol (symbol-leaf tree))
          '()
          (error "bad symbol: The symbol is not in the tree at all!" symbol))
      (let ((left (left-branch tree)))
        (if (element-of-set? symbol (symbols left))
            (cons 0 (encode-symbol symbol left))
            (cons 1 (encode-symbol symbol (right-branch tree)))))))


(define pairs '((A 2) (GET 2) (SHA 3) (WAH 1) (BOOM 1) (JOB 2) (NA 16) (YIP 9)))
(define rock-tree (generate-huffman-tree pairs))
(define rock-song '(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))
(define encoded-rock-song (encode rock-song rock-tree))
(length encoded-rock-song)
(* 3 (length rock-song))

; 结果如下，由于编码后的内容是竖着的，太占地方了，就不贴了
84
108