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.71.を解いてみる。

その他参考書籍

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

問題 2.71.

コード(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)))

(define huffman-ten (huffman-n 10
                               '(a b c d e f g h i j)
                               (expts 10)))

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

入出力結果(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)
((((((((((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 f 32) (a b c d e f) 63) (leaf g 64) (a b c d e f g) 127) (leaf h 128) (a b c d e f g h) 255) (leaf i 256) (a b c d e f g h i) 511) (leaf j 512) (a b c d e f g h i j) 1023)
                                                                                                                                                                                                                                                            (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)
                                                                                                                ((a b c d e f) 63)
                                                                                                                                            (leaf f 32)
                                                                                    ((a b c d e f g) 127)
                                                                                                                (leaf g 64)
                                                        ((a b c d e f g h) 255)
                                                                                    (leaf h 128)
                            ((a b c d e f g h i) 511)
                                                        (leaf i 256)
((a b c d e f g h i j) 1023)
                            (leaf j 512)
$

このようなn個の記号のHuffman木で、最高頻度の記号を符号化するのに必要なビット数は1。最低頻度の記号を符号化するのに必要なビット数はn-1。