開発環境
- 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。
0 コメント:
コメントを投稿