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

省略