SICP問題2.70

(問題2.69の)generate-huffman-treeを使って対応するHuffman木を生成し、(問題2.68の)encodeを使って次の通信文を符号化する

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

まずは8記号のアルファベットと相対頻度

(define test-pair (list '(A 2) '(BOOM 1) '(GET 2) '(JOB 2) '(NA 16) '(SHA 3) '(YIP 9) '(WAH 1)))
; test-pair

符号化。

(define test-lyric '(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))
; test-lyric
(encode test-lyric (generate-huffman-tree test-pair))
; (1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 0 1 1)

符号化に必要なビット数は

(length (encode test-lyric (generate-huffman-tree test-pair)))
; 84

ということで84bit。
8記号アルファベットの固定長符号の場合は、一文字表現するのに 3 bit 必用で歌詞の長さが

(length test-lyric)
; 36

だから、
3 * 36 = 108 bit