SICP §2.3.4（Haffman 符号化木 その４ [復号化手続き]）

昨日は会社のキックオフ会で帰宅が遅くなってしまったのでアップできなんだ。。

では前エントリを元に、「語頭符号」のコードをどうやって「復号化」するかを考えていこう。

(define (decode bits tree)
  (define (decode-1 bits current-branch)
    (if (null? bits)
	'()
	(let ((next-branch
	       (choose-branch (car bits) current-branch)))
	  (if (leaf? next-branch)
	      (cons (symbol-leaf next-branch)
		    (decode-1 (cdr bits) tree))
	      (decode-1 (cdr bits) next-branch)))))
  (decode-1 bits tree))

(define (choose-branch bit branch)
  (cond ((= bit 0) (left-branch branch))
	((= bit 1) (right-branch branch))
	(else
	 (error "bad bit -- CHOOSE-BRANCH" bit))))

これがSICPに記載されていたサンプルコード。再帰で実装してるね。で、最近はあんまり問題を解いてなくてつまらんかったから、サンプルコードの写経する前に自分で書いてみた。俺様コードは反復で実装。

(define (decode bits tree)
  (let loop ((rest bits)
	     (branch tree)
	     (ans '()))
    (cond (;枝が葉だったらその葉の記号を解のリストへ連結し、
	   ;ビットの続きを木のルートから再帰チェック。
	   (leaf? branch)
	   (loop rest tree (cons (symbol-leaf branch) ans)))
	  (;ビットリストが空になったら集積してきた記号のリストを返却。
	   (null? rest)
	   (reverse ans))
	  (;ビットリストの先頭が0なら左の枝で、
	   ;先頭が1なら右の枝でビットリストを再帰チェック。
	   (eq? 0 (car rest))
	   (loop (cdr rest) (left-branch branch) ans))
	  ((eq? 1 (car rest))
	   (loop (cdr rest) (right-branch branch) ans))
	  ;いずれでもなかった場合はエラーとみなす。
	  (else
	   (error "Error...")))))

次は「重み」の概念かぁ〜。長えなぁ。。