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必要.