SICP 問題 2.69（Huffman木の生成）

Scheme SICP

問題

次の手続きは引数として記号と頻度の対のリストをとり、（どの記号も一つの対以外には現れない。）Huffmanアルゴリズムに従い、Huffman木を生成する。

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

make-leaf-set は上（SICP §2.3.4（Haffman 符号化木　その５　[重み付き要素の集合]））にある手続きで、対のリストを葉の順序づけられた集合へ変換する。successive-merge は自分で書く手続きで、make-code-tree を使い、集合の最小重みの要素を順に合体させ、要素が一つになったら止める。それが目的の Huffman木である。（この手続きは多少ややこしいが、複雑ではない。複雑な手続きを設計していると思ったら確実にどこか違っている。順序付けられた集合の表現を使っている事を活用しなければならない。）


解答

なんだかエラクご丁寧にアドバイスされてるな。
問題文中にも挿入したが、make-leaf-setの使い方をもう一度確認しておこう。


引数としての入力情報は、



( (A 4) (B 2) (C 1) (D 1))
のようなシンボルと対のリスト。なので実際に評価する場合はこんな感じになる。


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

( (leaf D 1) (leaf C 1) (leaf B 2) (leaf A 4))

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

( (leaf D 1) (leaf C 1) (leaf B 2) (leaf A 4))

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

( (leaf D 1) (leaf C 1) (leaf B 2) (leaf A 4))

gosh>
重みに従って対をあべこべに並べても、出力される結果は必ず重みが「小さいもの→大きいもの」の順になっている。


で、今から実装する successive-merge 手続は、この評価結果から Huffman 木を生成する手続きになるわけだ。内部では make-code-tree 手続きを使用して、かつロジック自体はシンプルなんてことまでかかれている。お膳立てはばっちり。

じゃ、考えてみよう。


・・・ってこれって今までのエントリでも「そのうち出てくるんじゃね？」って言ってた「Huffman木を作る方法」じゃん。


つまりここでやろうとしていることって、SICP §2.3.4（Haffman 符号化木　その２　[Haffman 木の生成]）でやってたことをコードに落とそうって話じゃねぇの？

だとしたら基本方針としては、

  1. リストの要素が１個だったらその要素を返却。
  2. リストの先頭とその次の要素で枝を作成し、３つめ以降の要素群（順序づけられている）に順序づけて追加する。
  3. 先頭に戻る。
これでいけんじゃね？
重みでソートかける手続きってもうどっかで定義してたっけ・・・？
あ、ソートつうか adjoin-set 手続きを定義してあったな。これを使えばいいのか。

(define (successive-merge leafs)
  (let loop ((leaf&branch leafs))
    (if (eq? 1 (length leaf&branch)) ;リストの要素が１個だったら
	(car leaf&branch)            ;その要素を返却
	;そうでなければリストの先頭とその次の要素で枝を作成し、
	;作成した枝を３つめ以降の要素に昇順になるように追加。
	;そのリストを使って再帰処理。
	(let ((first (car leaf&branch))
	      (second (cadr leaf&branch))
	      (rest (cddr leaf&branch)))
	  (loop (adjoin-set (make-code-tree first second) rest))))))

では実験。データの確認がしやすいので、SICP §2.3.4（Haffman 符号化木　その２　[Haffman 木の生成]）で使ってたリスト、



( (A 8) (B 3) (C 1) (D 1) (E 1) (F 1) (G 1) (H 1))
を使っちゃおう。


gosh> (generate-huffman-tree '((A 8) (B 3) (C 1) (D 1) (E 1) (F 1) (G 1) (H 1)))

((leaf A 8) ((((leaf H 1) (leaf G 1) (H G) 2) ((leaf F 1) (leaf E 1) #0=(F E) 2) (H G . #0#) 4) (((leaf D 1) (leaf C 1) (D C) 2) (leaf B 3) #1=(D C B) 5) #2=(H G F E . #1#) 9) (A . #2#) 17)

gosh>
お。同一オブジェクトの表現が見づらいので display 手続きで。


gosh> (display (generate-huffman-tree '((A 8) (B 3) (C 1) (D 1) (E 1) (F 1) (G 1) (H 1))))

((leaf A 8) ((((leaf H 1) (leaf G 1) (H G) 2) ((leaf F 1) (leaf E 1) (F E) 2) (H G F E) 4) (((leaf D 1) (leaf C 1) (D C) 2) (leaf B 3) (D C B) 5) (H G F E D C B) 9) (A H G F E D C B) 17)#

gosh>
出てきた結果をチェック！枝オブジェクトの要素を全部縦にならべてみた。


((leaf A 8)

 ((((leaf H 1)

    (leaf G 1)

    (H G)

    2)

   ((leaf F 1)

    (leaf E 1)

    (F E)

    2)

   (H G F E)

   4)

  (((leaf D 1)

    (leaf C 1)

    (D C)

    2)

   (leaf B 3)

   (D C B)

   5)

  (H G F E D C B)

  9)

 (A H G F E D C B)

 17)
お〜、合ってるじゃん。