Scheme - データによる抽象の構築(記号データ(例: Huffman 符号化木(最低頻度、記号を符号化するのに必要なステップ数の増加の程度)))

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)
異なる出版社で予約受付中

開発環境

• OS X Mavericks - Apple(OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Scheme (プログラミング言語)
• Gauche (処理系)

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の2(データによる抽象の構築)、2.3(記号データ)、2.3.4(例: Huffman 符号化木)、Huffman木の表現、復号化手続き、重みつき要素の集合、問題 2.72.を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs
• プログラミングGauche (Kahuaプロジェクト (著), 川合 史朗 (監修), オライリージャパン)

問題 2.72.

アルファベットの最高頻度の記号を符号化するのに必要なステップ数の増加の程度はΦ(1)。

アルファベットの最低頻度の記号を符号化するのに必要なステップ数の増加の程度は、各節での記号を探索するのに必要なステップ数を考量して、

1 + 2 + ・・・ + n = n(n + 1)/2

より、Φ(n^2)。

コード(BBEdit, Emacs)

sample.scm

#!/usr/bin/env gosh
;; -*- coding: utf-8 -*-

;; これまでに書いた手続き
(load "./huffman.scm")

(define (expts m)  (map (lambda (n)
                          (expt 2 (- n
                                     1)))
                        (enumerate-interval 1
                                            m)))

(define (huffman-n n symbols weights)
  (define (inner m symbols weights)
    (if (> m n)
        '()
        (cons (list (car symbols)
                    (car weights))
              (inner (+ m 1)
                     (cdr symbols)
                     (cdr weights)))))
  (generate-huffman-tree (inner 1
                                symbols
                                weights)))

(define huffman-five (huffman-n 5
                                '(a b c d e)
                                (expts 5)))

(print huffman-five)
(print-huffman-tree huffman-five "                ")

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

$ ./sample.scm
(((((leaf a 1) (leaf b 2) (a b) 3) (leaf c 4) (a b c) 7) (leaf d 8) (a b c d) 15) (leaf e 16) (a b c d e) 31)
                                                                (leaf a 1)
                                                ((a b) 3)
                                                                (leaf b 2)
                                ((a b c) 7)
                                                (leaf c 4)
                ((a b c d) 15)
                                (leaf d 8)
((a b c d e) 31)
                (leaf e 16)
$