読者です 読者をやめる 読者になる 読者になる

@uents blog

Code wins arguments.

SICP 読書ノート#17 - 2.3.4 Huffman符号化木(1) (pp.94-99)

SICP Scheme

おおよそ理解できてるつもりだけど、問題 2.69が上手く解けない。

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

(define (successive-merge leafs)
  (if (null? leafs)
      nil
      (successive-merge-1 (cdr leafs) (car leafs))))

(define (successive-merge-1 leafs tree)
  (if (null? leafs)
      tree
      (successive-merge-1 (cdr leafs)
                          (make-code-tree (car leafs) tree))))

確認。

racket@> (equal? (generate-huffman-tree (list '(A 4) '(B 2) '(D 1) '(C 1)))
                 sample-tree)
#t

動いてる。

ただしこれだと右に偏った木になってしまう。

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

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

図2.18(p95)のように、ある程度左右のバランスが獲れるようにするにはどうすればいいんだろう?


※「SICP読書ノート」の目次はこちら