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