Scheme - 記号データ(Huffman 符号化木を生成する手続き)

計算機プログラムの構造と解釈
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.69を解いてみる。

その他参考書籍

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

問題 2.69

コード

sample.scm

(define (successive-merge set)
  (if (= (length set) 1)
      (car set)
      (let ((left (cadr set))
            (right (car set)))
        (let ((tree (make-code-tree left right)))
          (successive-merge (adjoin-set tree (cddr set)))))))
      

(define pairs1 (list '(A 4) '(B 2) '(C 1) '(D 1)))

(define pairs2 (list '(A 8) '(H 1) '(B 3) '(G 1) '(C 1)
                     '(F 1) '(D 1) '(E 1)))

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

1 ]=> (generate-huffman-tree pairs1)

;Value 2: ((((leaf c 1) (leaf d 1) (c d) 2) (leaf b 2) (c d b) 4) (leaf a 4) (c d b a) 8)

1 ]=> (generate-huffman-tree pairs2)

;Value 3: ((((leaf b 3) ((leaf h 1) (leaf g 1) (h g) 2) (b h g) 5) (((leaf c 1) (leaf f 1) (c f) 2) ((leaf d 1) (leaf e 1) (d e) 2) (c f d e) 4) (b h g c f d e) 9) (leaf a 8) (b h g c f d e a) 17)