Scheme - データによる抽象の構築(記号データ(例: Huffman 符号化木(最高頻度, 最低頻度の記号を符号化するのにに必要なビット数, 2のべき乗)))

計算機プログラムの構造と解釈[第2版]
(翔泳社)
ハロルド エイブルソン (著) ジュリー サスマン (著)
ジェラルド・ジェイ サスマン (著)
Harold Abelson (原著) Julie Sussman (原著)
Gerald Jay Sussman (原著) 和田 英一 (翻訳)

開発環境

• OS X Yosemite - Apple (OS)
• Emacs(Text Editor)
• Scheme (プログラミング言語)
• kscheme, Gauche, GNU Guile (処理系)

計算機プログラムの構造と解釈[第2版](ハロルド エイブルソン (著)、ジュリー サスマン (著)、ジェラルド・ジェイ サスマン (著)、Harold Abelson (原著)、Julie Sussman (原著)、Gerald Jay Sussman (原著)、和田 英一 (翻訳)、翔泳社、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の2(データによる抽象の構築)、2.3(記号データ)、2.3.4(例: Huffman 符号化木)、問題2.71.を解いてみる。

その他参考書籍

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

問題2.71.

コード(Emacs)

;; {(A 16) (B 8) (C 4) (D 2) (E 1)}
;; {(A 16) (B 8) (C 4) ({D E} 3)}
;; {(A 16) (B 8) ({C D E} 7)}
;; {(A 16) ({B C D E} 15)}
;; {({A B C D E} 31)}

;;         (E 1)
;;       ({D E} 3)
;;         (D 2)
;;     ({C D E} 7)
;;       (C 4)
;;   ({B C D E} 15)
;;     (B 8)
;; {({A B C D E} 31)}
;;   (A 16)
;; 最高頻度の記号 A 符号化するのに必要なビット数 1
;; 最低頻度の記号 E 符号化するのに必要なビット数 4

;; {(A 512) (B 256) (C 128) (D 64) (E 32) (F 16) (G 8) (H 4) (I 2) (J 1)}
;; {(A 512) (B 256) (C 128) (D 64) (E 32) (F 16) (G 8) (H 4) ({I J} 3)}
;; {(A 512) (B 256) (C 128) (D 64) (E 32) (F 16) (G 8) ({H I J} 7)}
;; {(A 512) (B 256) (C 128) (D 64) (E 32) (F 16) ({G H I J} 15)}
;; {(A 512) (B 256) (C 128) (D 64) (E 32) ({F G H I J} 31)}
;; {(A 512) (B 256) (C 128) (D 64) ({E F G H I J} 63)}
;; {(A 512) (B 256) (C 128) ({D E F G H I J} 127)}
;; {(A 512) (B 256) ({C D E F G H I J} 255)}
;; {(A 512) ({B C D E F G H I J} 511)}
;; {({A B C D E F G H I J} 1023)}

;;                   (j 1)
;;                 {({I J} 3)}
;;                   (I 2)
;;               {({H I J} 7)}
;;                 (H 4)
;;             {({G H I J} 15)}
;;               (G 8)
;;           {({F G H I J} 31)}
;;             (F 16)
;;         {({E F G H I J} 63)}
;;           (E 32)
;;       {({D E F G H I J} 127)}
;;         (D 64)
;;     {({C D E F G H I J} 255)}
;;       (C 128)
;;   {({B C D E F G H I J} 511)}
;;     (B 256)
;; {({A B C D E F G H I J} 1023)}
;;   (A 512)
;; 最高頻度の記号 A 符号化するのに必要なビット数 1
;; 最低頻度の記号 J 符号化するのに必要なビット数 9