問題2-69〜70

SICP

まずは、Huffman符号化木を生成するための手続きを書きます。以下は、本書に掲載されていた例文で、記号とその重み付けの組み合わせリストから、Huffman-treeの葉の要素の並びを生成するロジックです。

(define (adjoin-set x set)
  (cond ((null? set) (list x))
        ((< (weight x) (weight (car set))) (cons x set))
        (else (cons (car set)
                    (adjoin-set x (cdr set))))))

(define (make-leaf-set pairs)
  (if (null? pairs)
      '()
      (let ((pair (car pairs)))
        (adjoin-set (make-leaf (car pair)
                               (cadr pair))
                    (make-leaf-set (cdr pairs))))))

(define sample
  '((A 4) (B 2) (C 1) (D 1) (E 3)))

(make-leaf-set sample)  
;=>((leaf d 1) (leaf c 1) (leaf b 2) (leaf e 3) (leaf a 4))

ここで重要なのが、adjoin-setのおかげで、重み付けの小さい方から記号が並んでくれることです。問題2-69では、これを利用して、Huffman符号化木を生成します。

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

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

leaf-setの先頭二つの要素を組み合わせて部分的な木を作成します。重み付けの小さい要素同士をくっつけるわけです。それとleaf-setの残りの部分を組み合わせて、新たなleaf-setとし、successive-mergeに再投入します。leaf-setの要素数が二つだけになったら、単純にmake-code-treeを行い、その結果が最終的なHuffman-treeとなります。leaf-setの要素数が一つだけの場合は、そのままそれを返すようなロジックも入れてあります。この処理の結果は、以下のように印字されます。

(generate-huffman-tree sample)
;=>(((leaf b 2) ((leaf d 1) (leaf c 1) (d c) 2) (b d c) 4) ((leaf e 3) (leaf a 4) (e a) 7) (b d c e a) 11)

次の問題2-70では、上記の手続きを利用して1950年代のロックの歌の叙情詩を効率よく符号化する方法を学ぶことができます。各記号の重み付けを以下のように表現します。

(define rock-music
  '((A 2) (BOOM 1) (GET 2) (JOB 2) (NA 16) (SHA 3) (YIP 9) (WAH 1)))

この重み付け情報からHuffman-treeを生成すると、以下のようなツリーができます。

(generate-huffman-tree rock-music)
;=>
(((leaf b 2) ((leaf d 1) (leaf c 1) (d c) 2) (b d c) 4) ((leaf e 3) (leaf a 4) (e a) 7) (b d c e a) 11)
((leaf na 16)
 ((leaf yip 9)
  (((leaf a 2) ((leaf wah 1) (leaf boom 1) (wah boom) 2) (a wah boom) 4)
   ((leaf sha 3) ((leaf job 2) (leaf get 2) (job get) 4) (sha job get) 7)
   (a wah boom sha job get)
   11)
  (yip a wah boom sha job get)
  20)
 (na yip a wah boom sha job get)
 36)

正しく動いているかどうかを確認します。

(define rock-huffman-tree (generate-huffman-tree rock-music))

(decode (encode '(Get a job) rock-huffman-tree) rock-huffman-tree)
;=>(get a job)

このHuffman-treeを利用して、歌詞を符号化してみます。

(encode '(Get a job) rock-huffman-tree)
;=>(1 1 1 1 1 1 1 0 0 1 1 1 1 0)  ;14bits / 3words
(encode '(Sha na na na na na na na na) rock-huffman-tree)
;=>(1 1 1 0 0 0 0 0 0 0 0 0)  ;12bits / 9words
(encode '(Get a job) rock-huffman-tree)
;=>(1 1 1 1 1 1 1 0 0 1 1 1 1 0)  ;14bits / 3words
(encode '(Sha na na na na na na na na) rock-huffman-tree)
;=>(1 1 1 0 0 0 0 0 0 0 0 0)  ;12bits / 9words 
(encode '(Wah yip yip yip yip yip yip yip yip yip) rock-huffman-tree)
;=>(1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0)  ;23bits / 10words
(encode '(Sha boom) rock-huffman-tree)
;=>(1 1 1 0 1 1 0 1 1)  ;9bits / 2words

8記号を固定長符号で表現しようとすると3ビット必要になりますが、この可変長符号を利用すれば、naとかyipが出てくる場所はかなりのビット節約になっているようです。