0

わかりましたので、文字を含むペアのリストとその頻度、またはテキストで見られた回数が与えられたとします。ex '((#\a . 4) (#\b . 2) (#\c . 9)) 2つの最低周波数を見つけて、それらをツリーに結合できるようにするにはどうすればよいですか? これらを見つけるのに役立つ何らかの機能はありますか？

4

2 に答える 2

3

SICPブックのセクション§2.3.4を見ると、ハフマン符号化ツリーを最初から実装する方法についての完全な説明があります。

質問に関して、指定された形式のリストで2つの最低頻度を見つける1つの可能な方法を次に示します。

(define frequencies '((#\a . 4) (#\b . 2) (#\c . 9)))

(take
 (sort frequencies
       (lambda (x y)
         (< (cdr x) (cdr y))))
 2)

=> '((#\b . 2) (#\a . 4))
于 2012-11-02T02:53:36.840 に答える
1

頻度のソートされていないリスト表現のみを使用することは、おそらくこの問題に対する正しいアプローチではありません。その理由は次のとおりです。最小値を繰り返し見つけることが、ハフマン エンコーディング ツリーを計算するための主な操作です。この最小検索操作を繰り返すときに、リスト全体を検索し続ける必要はありません。

問題への最初の攻撃として、ソートを、最小値の検出を高速化するためのアプローチと考えてください。

ただし、この特定の問題については、コレクションを表すデータ構造であるバイナリヒープの使用を検討する必要があります。ヒープから最小要素を引き出すのが非常に安価であるという、非常に優れた特性があります。ハフマン ツリーの構築プロセス中に、新しい要素をコレクションに追加することになります。リストを何度も再利用したくありません。

Racket には、標準ライブラリのデータ/ヒープコレクションにバイナリ ヒープの実装があります。これをハフマン ツリーの構築に適用するのは非常に簡単です。以下は、ヒープを使用した基本的なアルゴリズムを実装しています。

(require data/heap)

;; ...

;; make-huffman-tree: (listof leaf) -> node
(define (make-huffman-tree leaves)
  (define a-heap (make-heap node<=?))
  (heap-add-all! a-heap leaves)
  (for ([i (in-range (sub1 (length leaves)))])
    (define min-1 (heap-min a-heap))
    (heap-remove-min! a-heap)
    (define min-2 (heap-min a-heap))
    (heap-remove-min! a-heap)
    (heap-add! a-heap (merge (+ (frequency min-1) (frequency min-2))
                             min-1 min-2)))
  (heap-min a-heap))

ここで、自由変数node<=?は、頻度によって比較する方法を知ることを目的としており、merge2 つのことを取りまとめることを目的としています。

ハフマン ツリー構成の核心は図 2 で見ることができますmake-huffman-tree。ヒープを使用して 2 つの最小要素を引き出し、それらをマージして、結果をヒープに戻します。木が1本になるまで繰り返します。

于 2012-11-02T19:23:02.557 に答える