読者です 読者をやめる 読者になる 読者になる

(wat-aro)

無職から有職者にランクアップしました

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