2015/10/27
SICP 問題 2.70
gosh> (define q-pairs '((A 2) (BOOM 1) (GET 2) (JOB 2) (NA 16) (SHA 3)
(YIP 9) (WAH 1)))
q-pairs
gosh> (define q-tree
(successive-merge (make-leaf-set q-pairs)))
q-tree
gosh> (define 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))
message
gosh> (encode message q-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)
gosh> (length (encode message q-tree))
84
gosh> (decode (encode message q-tree) q-tree)
(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)
符号化には84bit必要. 八記号アルファベットの固定長符号の場合は
gosh>(length message)
36
36 * (log2 8) = 108 なので108bit必要.