問題2.70

(define rock-1950-tree
  (generate-huffman-tree '((A 2) (NA 16) (BOOM 1) (SHA 3) (GET 2) (YIP 9) (JOB 2) (WAH 1))))

(define 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 ))

(encode song rock-1950-tree)

;; -> (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)
;; -> 84 bit

;; 固定長の最小bitは
;; 8個しか記号がないので、3bitで対応できる。
;; (* 3 (length song)) -> 108 bitである。

;; Huffman符号化木を使うことにより、77.7%に圧縮できている。