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

その他参考書籍

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

問題 2.70.

コード(BBEdit, Emacs)

sample.scm

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

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

(define message '(get a job
                      sha na na na na na na na na
                      get a job
                      sha na na na na na na na na
                      wah yip yip yip yip yip yip yip yip yip
                      sha boom))

(define pairs1 (list '(a 2)
                     '(boom 1)
                     '(get 2)
                     '(job 2)
                     '(na 16)
                     '(sha 3)
                     '(yip 9)
                     '(wah 1)))

(define pairs2 (list '(a 000)
                     '(boom 001)
                     '(get 010)
                     '(job 011)
                     '(na 100)
                     '(sha 101)
                     '(yip 110)
                     '(wah 111)))

(define huffman-tree (generate-huffman-tree pairs1))

(define bits1 (encode message
                      huffman-tree))

(define (find-bit symbol)
  (define (inner pairs)
    (let ((pair (car pairs)))
      (if (eq? (car pair)
               symbol)
          (cadr pair)
          (inner (cdr pairs)))))
  (inner pairs2))

(define bits2 (map (lambda (symbol)
                     (find-bit symbol))
                   message))

(print "叙情詩: " message)
(print "Huffman木: " huffman-tree)
(print "可変長符号: " bits1)
(print "固定長符号(3ビット/記号): " bits2)
(print "叙情詩を符号化するのに必要なビット数")
(print "可変長符号(Huffman木)の場合: " (length bits1))
(print "固定長符号の場合(最小ビット数): " (* 3 (length bits2))
       "(" (* 3 (length message)) ")")

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

$ ./sample.scm
叙情詩: (get a job sha na na na na na na na na get a job sha na na na na na na na na wah yip yip yip yip yip yip yip yip yip sha boom)
Huffman木: ((leaf na 16) ((leaf yip 9) (((leaf a 2) ((leaf wah 1) (leaf boom 1) (wah boom) 2) (a wah boom) 4) ((leaf sha 3) ((leaf job 2) (leaf get 2) (job get) 4) (sha job get) 7) (a wah boom sha job get) 11) (yip a wah boom sha job get) 20) (na yip a wah boom sha job get) 36)
可変長符号: (1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 0 1 1)
固定長符号(3ビット/記号): (10 0 11 101 100 100 100 100 100 100 100 100 10 0 11 101 100 100 100 100 100 100 100 100 111 110 110 110 110 110 110 110 110 110 101 1)
叙情詩を符号化するのに必要なビット数
可変長符号(Huffman木)の場合: 84
固定長符号の場合(最小ビット数): 108(108)
$