ハフマンその２

SICP

問題 2.70

まず符号化がバグってたので直しました。
encode 手続きは本書に載ってるものそのままです。

(define (encode message tree)
  (if (null? message)
      '()
      (append (encode-symbol (car message) tree)
              (encode (cdr message) tree))))

(define (encode-symbol letter tree)
  (define (iter t direction)
    (cond ((leaf? t) direction)
          ((memq letter (symbols (left-branch t)))
           (iter (left-branch t) (append direction '(0))))
          ((memq letter (symbols (right-branch t)))
           (iter (right-branch t) (append direction '(1))))
          (else
           (print "bad letter -- ENCODE-SYMBOL" letter))))
  (iter tree '()))

符号化用の木と通信文を用意します。

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

(define message2-70 '(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))

符号化します。結果の表示が省略されてしまうので print しておきます。

gosh> (print (encode message2-70 tree2-70))
(1 1 1 1 1 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 1 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 0)
#<undef>

符号化に必要なビット数はいくつ？

gosh> (length (encode message2-70 tree2-70))
84

84 ビットでした。
符号化したものを復号化してみます。

gosh> (print (decode (encode message2-70 tree2-70) tree2-70))
(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)
#<undef>

きちんと復号化できました。

固定長符号の場合は、8 種類あるので 2^3 種類ですから、最低でも一つの単語あたり 3 ビット必要になります。

gosh> (* 3 (length message2-70))
108

本書に載っている歌を固定長符号を使って符号化する場合は、108 ビット必要です。
ハフマン符号を使うと 24 ビットも短縮できることがわかります。