Scheme: SICPの練習問題(2.68)

飛んでたりする。いや、これ以前もちゃんとやってますよ(^^;

以前Huffman符号のことを(LHAの話か？)をちらっと書いて、あきらめたとも書いたがその話題だったのでついつい。
とりあえず、Huffman符号木について。木自体はこんな感じ。

{A B C D E F G H} 17
               *
             /   \
           A 8     * {B C D E F G H} 9
                 /     \
     {B C D} 5 *           \
             /   \             \
           B 3     * {C D} 2      * {E F G H} 4
                 /   \        /       \ 
               C 1   D 1    * {E F} 2     * {G H} 2
                          /   \         /     \
                        E 1  F 1      G 1     H 1

いまいち二分木に見えないのはご愛嬌。
ここではなのか、一般的になのか、左に行けば１、右にいけば０となっている。数字は重み(多分、頻出度)

デコードは、ビット列から文字列を復元するので、先頭からビット見て行って葉にたどり着いたところで一文字復元完了という感じ。
エンコードは逆。上から木を舐めて、葉にたどり着くまでもビットを記録するって感じ。

っで、２．６８の解凍

(define (encode-symbol symbol tree)
  (define (has-symbol? symbol tree)
    (if (leaf? tree)
 (eq? symbol (symbol-leaf tree))
      (or (has-symbol? symbol (left-branch tree))
   (has-symbol? symbol (right-branch tree)))))
  (if (leaf? tree) ; 葉ならシンボルを見つけた
      '()
    (let ((left (left-branch tree))
   (right (right-branch tree)))
      (cond ((has-symbol? symbol left)
      (cons 0 (encode-symbol symbol left)))
     ((has-symbol? symbol right)
      (cons 1 (encode-symbol symbol right)))
     (else (error "error"))))))

最初はcondの中でifを使って変な場合分けをしてlistを返してappendしていたが、解答はすっきりconsを使ってた。いまいちこの辺の使い方がまだ身について無い感じ。う～ん。
まぁ、でもHuffman符号の具体的なやり方がわかったということでちと満足。
(もやもやとは分かっていたが、木の作り方とかいまいちだった)