SICPを読む(79) 問題2.68 ハフマン符号化木(2)

符号化に挑戦。

問題 2.68

符号木を元に、(A D A B B C A)を符号化せよ。という問題。

ムズそうなので方針を練ります。

方針

符号化でのポイントは、履歴を返すという所。

葉が見付かったら、'()を返します。見付からなかったら#fを返します。

枝の検索も同じように枝の先がリストならばconsして返します。見付からなければ#fを返します。

最後まで検索して、#fならばエラーとなります。

コーディング

妄想方針を元にコーディング

(define (encode-symbol symbol tree)
  (define (iter tree)
    (if (leaf? tree)
      (if (eq? (symbol-leaf tree) symbol)
          '()
          #f)
      (let ((left (iter (left-branch tree)))) ; try-left
        (if (list? left)
            (cons 0 left)
            (let ((right (iter (right-branch tree)))) ; try-right
              (if (list? right)
                  (cons 1 right)
                  #f))))))
  (let ((res (iter tree)))
    (if res
        res
        (error "not found"))))

テストぉ〜

(encode-symbol 'A data) ; (0)
(encode-symbol 'B data) ; (1 0)
(encode-symbol 'C data) ; (1 1 1)
(encode-symbol 'D data) ; (1 1 0)
(encode-symbol 'E data) ; not found.

(encode '(A D A B B C A) data) ; (0 1 1 0 0 1 0 1 0 1 1 1 0)

上手くいっている様子。

最初は両方の枝を見たところでエラーを返してしまった。実は上手くいっているようで上手くいってなかった。ツリーを複雑化すると検索出来ずに終わってしまうデータが出る。全ての葉を見てからエラーを判断しなければならないので、エラー処理はトップレベルでしなければならない。ツリーの検索はムジィ。

それにしてもこんなに難しい問題があっさり解けてしまうようになるというのは凄いことだと思う。