Scheme - Huffman 符号化木(encode, decode)

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: MIT/GNU Scheme

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション)の2(データによる抽象の構築)、2.3(記号データ)、2.3.4(例: Huffman 符号化木)、Huffman 木の生成、Huffman 木の表現、複合化手続き、重みつき要素の集合の問題 2.67、問題 2.68を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題 2.67、問題 2.68

コード

sample.scm

(define (encode-symbol symbol tree)
  (cond ((null? tree) (error "bad tree" tree))
        ((leaf? tree) '())
        ((memq symbol (symbols (left-branch tree)))
         (cons 0 (encode-symbol symbol (left-branch tree))))
        ((memq symbol (symbols (right-branch tree)))
         (cons 1 (encode-symbol symbol (right-branch tree))))
        (else (error "bad symbol" symbol))))

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

1 ]=> (decode sample-message sample-tree)

;Value 2: (a d a b b c a)

1 ]=> (encode '(a d a b b c a) sample-tree)

;Value 3: (0 1 1 0 0 1 0 1 0 1 1 1 0)