理系学生日記

おまえはいつまで学生気分なのか

忍者TOOLS

問題2-69 (2.3.4 Example: Huffman Encoding Trees)

今日はいよいよHuffman符号木をつくる。ワクワクはするんですけど、だんだんと1問解くのにかかる時間が増えています。
今の1日1問ペースを2日1問とかにできたらなーと妄想して喜んでいますが、そんなことすると1日目を休んで結局2日目で同じ事になるので意味が無いですね。


ヒントとして与えられているのがこれ。結局successive-mergeを作ればいいみたいです。make-leaf-setは既にあるし。

(define (generate-huffman-tree pairs)
  (successive-merge (make-leaf-set pairs)))

考えた順ですけど、make-leaf-setはleafを作って、各文字の出現頻度の昇順に並べてくれる。

(make-leaf-set '((A 4) (B 2) (C 1) (D 1))) ; ((leaf D 1) (leaf C 1) (leaf B 2) (leaf A 4))

なので、最初の要素と次の要素が出現頻度の低い文字2つになる。これを組み合わせて部分木にすればいい!!
で、部分木にしたあと、それをまた出現頻度の低い順に並べる。ってわけでsuccessive-mergeはこうした。adjoin-treeが並べ替えをしてくれるヤツです。

(define (successive-merge leaf-set)
  (if (null? (cdr leaf-set)) 
      (car leaf-set)
      (let ((first-second (make-code-tree (car leaf-set)      ;1番目と2番目を部分木にする
					  (cadr leaf-set))))  
	(successive-merge (adjoin-tree first-second (cddr leaf-set))))))

adjoin-treeはadjoin-setとかとかわらないですね。ただsetの中にはtreeとleafが混じっているので、そこに気をつける。

(define (adjoin-tree tree set)
  (if (null? set) (list tree)
      (let ((first (car set)))
	(let ((min (if (leaf? first)
		       (weight-leaf first)
		       (weight first))))
	  (if (< (weight tree) min)
	      (cons tree set)
	      (cons (car set) (adjoin-tree tree (cdr set))))))))

これで、generate-huffman-treeができた。

(encode '(A D A B B C A) (generate-huffman-tree '((A 4) (B 2) (C 1) (D 1))))
; (0 1 1 0 0 1 0 1 0 1 1 1 0)

この出力は、昨日のencodeの結果と一致します。