2.3.4 Example: Huffman Encoding Trees
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-16.html#%_sec_2.3.4
重要な応用って気がするけど、あんまり理解できていないような気がするなぁ。
今のところ、先に進む方を優先しているのだけど、いつかちゃんと振り返らないと。
問題2.67
ここは打ち込むだけなので特になし。
(define sample-tree (make-code-tree (make-leaf 'A 4) (make-code-tree (make-leaf 'B 2) (make-code-tree (make-leaf 'D 1) (make-leaf 'C 1))))) (define sample-message '(0 1 1 0 0 1 0 1 0 1 1 1 0))
問題2.68
Encodeを書く問題。ここは、ほぼ答えを見てしまった>
http://oss.timedia.co.jp/show/SICP/ex-2.68
(define (encode message tree) (if (null? message) '() (append (encode-symbol (car message) tree) (encode (cdr message) tree)))) (define (encode-symbol symbol tree) (if (leaf? tree) '() (let ((left-tree (left-branch tree)) (right-tree (right-branch tree))) (cond ((symbol-exist? symbol left-tree) (cons 0 (encode-symbol symbol left-tree))) ((symbol-exist? symbol right-tree) (cons 1 (encode-symbol symbol right-tree))) (else (error "Invalid symbol -- ENCODE-SYMBOL" symbol)))))) (define (symbol-exist? symbol tree) (if (leaf? tree) (eq? symbol (symbol-leaf tree)) (or (symbol-exist? symbol (left-branch tree)) (symbol-exist? symbol (right-branch tree)))))
問題2.69
ここは面白いね。すでに順序づけられているので、何も考えずに木をマージしていけばいい。
(define (generate-huffman-tree pairs) (sucessive-merge (make-leaf-set pairs))) (define (sucessive-merge pairs) (if (= (length pairs) 1) (car pairs) (sucessive-merge (adjoin-set (make-code-tree (car pairs) (cadr pairs)) (cddr pairs)))))
問題2.70
(define song-tree (generate-huffman-tree '((a 2) (boom 1) (get 2) (job 2) (na 16) (sha 3) (yip 9) (wah 1)))) (define lilycs '(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))
出てきたビットの数を数えると、84Bit。
固定長の場合、1文字あたりに3ビットを割り当てるので、36文字だと、108Bit。
問題2.71
省略
問題2.72
省略