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))

畳み込みながらソーティングすることで重さ順にツリーを生成出来る。

すげぇ。すげぇよ。感動した。感動。


感動が伝わらないというのが残念で仕方がない。ハフマンすげぇよ。天才。