SICPを読む(80) 問題2.69 ハフマン符号化木(3)
今度は木の生成
問題 2.69
何も考えずにやるとこうかな。
(define (successive-merge leaf-set) (define (iter set tree) (if (null? set) tree (iter (cdr set) (make-code-tree (car set) tree)))) (iter (cdr leaf-set) (car leaf-set)))
あっさりすぎ?
ツリーというよりリストなんだけど。最後だけ二股に分かれてるリスト。一個以上無いとエラーです。
SICPのサンプルを作ってみます。
(define my-tree (generate-huffman-tree '((A 4) (B 2) (D 1) (C 1)))) ; ((leaf A 4) ((leaf B 2) ((leaf D 1) (leaf C 1) (D C) 2) (B D C) 4) (A B D C) 8) (define my-encode (encode '(A D A B B C A) my-tree)) ; (0 1 1 0 0 1 0 1 0 1 1 1 0) (decode my-encode my-tree) ; (A D A B B C A)
なんか違うっぽい
回答を見ると、adjoin-setを使うらしい。adjoin-setは重みで判断してるんだった。つまり、ツリーでも関係なく使えるんだ。ふむふむ。
しかし、眠いので寝る。また明日やる。
再開
回答を見るとこうだ。
(define (successive-merge set) (if (null? (cdr set)) (car set) (successive-merge (adjoin-set (make-code-tree (car set) (cadr set)) (cddr set)))))
「全く意味がわからない」
デバッグしまくった結果、次の事がわかった。
「畳み込みながらソーティング」
うはぁ、スゲーーーーーーーーーー。感動した感動。
動きをまとめると
((A 8) (B 3) (C 1) (D 1) (E 1) (F 1) (G 1) (H 1))
について考える。
adjoin-setはリストを重み順でソートする。重い方がツリーの一番上に来た方がいいから重い方が右に来る。
((H 1) (G 1) (F 1) (E 1) (D 1) (C 1) (B 3) (A 8))
ここまでが準備段階。
ここから畳み込みに入る。前から2つのデータをツリーにする。
(H G 2)
畳み込んだ。ソーティング。
((F 1) (E 1) (D 1) (C 1) (H G 2) (B 3) (A 8))
(F E 2), (D C 2)も畳み込んでソーティング
((H G 2) (F E 2) (D C 2) (B 3) (A 8))
繰り返す。
((D C 2) (B 3) (H G E F 4) (A 8)) ((H G E F 4) (D C B 5) (A 8)) ((A 8) (H G E F D C B 9)) ((A H G E F D C B 17))
畳み込みながらソーティングすることで重さ順にツリーを生成出来る。
すげぇ。すげぇよ。感動した。感動。
感動が伝わらないというのが残念で仕方がない。ハフマンすげぇよ。天才。