2014年5月7日水曜日

Scheme - データによる抽象の構築(記号データ(例: Huffman 符号化木(可変長符号と固定長符号による符号化に必要なビット数の比較)))

その他参考書籍

コード(BBEdit, Emacs)

sample.scm

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

;; これまでに書いた手続き

(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)
(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)) ")")

```

```\$ ./sample.scm

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)

\$
```