SICP 読書ノート#18 - 2.3.4 Huffman符号化木(2) (pp.94-99)

「§2.3.4 Huffman符号化木」について。

テキストの説明がかなりわかりやすく、楽しく読めました。

問題 2.67

テキストのコードを写経し実行してみる。

(define sample-tree
  (make-code-tree (make-leaf 'A 4)
                  (make-code-tree
                   (make-leaf 'B 2)
                   (make-code-tree (make-leaf 'D 1)
                                   (make-leaf 'C 1)))))

(define sample-message '(0 1 1 0 0 1 0 1 0 1 1 1 0))

テスト。

racket@> (decode sample-message sample-tree)
=> '(A D A B B C A)

問題 2.68

encode手続きはメッセージのシンボル毎を順次に処理するものとして与えられている。

そこでencode-symbolを実装せよ。

encode-symbolは与えられたシンボルから木を辿って符号化するだけ。

与えられたシンボルが木に含まれているかどうかは、treeのsymbolsプロパティに含まれるかで判断すればよいので、

(define (encode-symbol symbol tree)
   (if (null? (memq symbol (symbols tree)))
      #f
      (encode-symbol-1 symbol tree nil)))

encode-symbol-1は実際に木を辿って符号化する手続き。左の枝にあれば0を、右の枝にあれば1を逐次追加していく。

(define (encode-symbol-1 symbol tree bits)
  (cond ((leaf? tree)
         bits)
        ((memq symbol (symbols (left-branch tree)))
         (encode-symbol-1 symbol
                          (left-branch tree)
                          (append bits (list 0))))
        (else
         (encode-symbol-1 symbol
                          (right-branch tree)
                          (append bits (list 1))))))

テスト。元のメッセージとデコード→エンコードしたメッセージを比較する。

racket@> (equal?
          sample-message
          (encode (decode sample-message sample-tree) sample-tree))
=> #t

上手く動いた。

問題 2.69

前回のエントリでは、単に順番にマージしていく点が間違っていた。

「Huffman木の生成」の章にもあるように、常に最小の重みのペアをマージしていけばよい。

(define (generate-huffman-tree pairs)
  (successive-merge (make-leaf-set pairs)))

(define (successive-merge tree)
  (cond ((null? tree) nil)
        ((null? (cdr tree)) (car tree))
        (else
         (successive-merge
          (adjoin-set (make-code-tree (car tree) (cadr tree))
                      (cddr tree))))))

ここでadjoin-setが登場。最初は何のために使うのかわからなかったけど、納得。

テスト。

racket@> (define sample-tree-2
           (generate-huffman-tree '((A 4) (B 2) (D 1) (C 1))))

racket@> (equal?
          sample-message
          (encode (decode sample-message sample-tree-2) sample-tree-2))
=> #t

OK。

問題 2.70

Racketのシンボルは大文字/小文字の区別をつけるので、すべて大文字にして考える。

(define word-pairs
  (list '(A 2)
        '(BOOM 1)
        '(GET 2)
        '(JOB 2)
        '(NA 16)
        '(SHA 3)
        '(YIP 9)
        '(WAH 1)))

(define song-lyrics
  '(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))

として、

racket@> (define word-tree (generate-huffman-tree word-pairs))

racket@> (equal?
          song-lyrics
          (decode (encode song-lyrics word-tree) word-tree))
=> #t

ちゃんと動いている。

よって、符号化に必要なビット数は

racket@> (length (encode song-lyrics word-tree))
=> 84

八記号アルファベット (the eight-symbol alphabet) とは、 8 = 2³ つまり 3ビットで表されるアルファベットのことかと思われるので、八記号アルファベットの場合は、84 * 3 = 108ビットが必要。

問題 2.71、2.72

パスします。

次回は「§2.4 抽象データの多重表現」から。

@uents blog

Code wins arguments.