0

リーフノードを作成するmake-leaf-setというプロシージャと、最も低いものから高いものへと並べ替える別のプロシージャがあります。

(define (make-leaf-set pairs)
   (if (null? pairs)
    '()
    (let ((pair (car pairs)))
      (adjoin-set (make-leaf (car pair)
                             (cdr pair))
                (make-leaf-set (cdr pairs))))))


(define (adjoin-set x set)
  (cond ((null? set) (list x))
    ((< (weight x) (weight (car set))) (cons x set))
    (else (cons (car set)
                (adjoin-set x (cdr set))))))


"Predefined dotted paires"
(define pairs '((a . 2) (b . 5) (c . 1) (d . 3) (e . 1) (f . 3)))
=> ((leaf e 1) (leaf c 1) (leaf a 2) (leaf f 3) (leaf d 3) (leaf b 5))

ペアは使用すると完全に機能します（make-leaf-setペア）。すべてが並べ替えられます。また、make-code-treeと呼ばれる別の手順を使用します

(define (make-code-tree left right)
  (list left
        right
    (append (symbols left) (symbols right))
    (+ (weight left) (weight right))))

(define (symbols tree)
  (if (leaf? tree)
     (list (symbol-leaf tree))
     (caddr tree)))

(define (weight tree)
   (if (leaf? tree)
     (weight-leaf tree)
     (cadddr tree)))
  • 目標は、ペアのリストを取得してからハフマンツリーを作成するプロシージャを作成することです。

始めに私はこれを思いついた

(define (grow-huffman-tree list)
  (successive-merge (make-leaf-set list) '()))

 (define (successive-merge par tree)
   (if (null? par)
      tree
   (append (make-code-tree (car par) (cadr par)) tree)))

座っていると、最初の2つの要素がマージされ、が与えられ((leaf e 1) (leaf c 1) (e c) 2)ます。しかし、私はそれがすべての葉をマージしてハフマンツリーのように構築されるようにしたいので、他の葉をこのツリーにマージすることはできません。呼び出そうとすると(successive-merge (cdr par) tree)、要素d3でエラーが発生します...

4

1 に答える 1

1

小さい初期の例から始めて、それぞれの小さい例に対して何を行うか (そして、それが本当に適切なヘルパー ルーチンであるかどうかによってはgrow-huffman-tree、おそらく) を検討することをお勧めします。successive-merge

たとえば、次の行が次の行にあるとは信じられませんsuccessive-merge。

(append (make-code-tree (car par) (cadr par)) tree)

まったく意味をなさない可能性があります。(しかし、繰り返しますが、クラスのインスタンスがどのように解釈されるべきかを含むデータ定義がtreeなければ、何がナンセンスで何が「賢い」かを言うのは難しいです。

また、「ハフマン ツリー」の「ツリー」という言葉は非常に関連性があることにも注意してください。Listof X;を構築したくありません。代わりにTreeof X が必要です。したがって、次のように出力されるデータが表示されている場合:

 ((obj 1 2) (obj 3 4) (obj 5 6) ... (obj 100 101))

それは通常、興味深い木とは見なされません。それは通常、リストであると考えられていました。(厳密に言えば、ツリーとして解釈できます。非常に大きな分岐因子を持つ非常に浅いツリーです。)

ツリー構造のより一般的な例は、次のような出力になります。

 (node a 1 (node b 2 (leaf 17)
                     (node d (leaf 26)
                             (leaf 17)))
           (node c 6 (leaf 18)
                     (leaf 1)))
于 2013-03-13T02:34:36.407 に答える