今日はいよいよ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の結果と一致します。