0

私のキャラクターとその頻度が次のようになっているとします。

Char    Freq.
 a       1
 b       2
 c       3
 d       4
 e       5
 f       6
 g       7
 h       8

ツリーを構築するとき、ステップ 2 で次のようになります。

   [3]     [3]   [4]   [5]   [6]   [7]   [8]
   / \      c     d     e     f     g     h
  /   \
[1]   [2]
 a     b

さて、2 つの 3 があるので、それらの優先度をどのように決定できるでしょうか?

ハフマン コーディングでは、これは次のように見なされます。

[3]    [3]     [4]   [5]   [6]   [7]   [8]
 c     / \      d     e     f     g     h   
      /   \
    [1]   [2]
     a     b

なんで？

4

3 に答える 3

1

違いは何ですか？しばらく無視dするhと、最初のケースでは次のようになります

a = 00
b = 01
c = 1

そして2番目のケースでは、

a = 10
b = 11
c = 0

最終ツリーで同じ高さにある限りc、そのコードの長さは同じになります。

于 2011-02-14T08:54:52.380 に答える
0

あなたのケースは面白くありません。分岐への 0 と 1 の割り当ては任意であるため、アウトラインを選択すると同じコード、つまりどちらの方法でも同じコード長になります。

ただし、合計頻度が同じで形状が異なる 3 つ以上のグループの選択に直面する興味深いケースがあります。どのような選択をしても、全体的に同じ最適性が得られます。つまり、提供された周波数で提供されたシンボルをエンコードするための総ビット数がまったく同じになります。ただし、選択によって、異なるビット長の組み合わせを持つ異なる形状のツリーになる可能性があります。次に、必要に応じて、より深いツリーまたはより浅いツリーに到達するように、このような選択を行うことができます。

于 2013-05-29T05:37:30.907 に答える
0

私は c をより優先度の高いもの (短いコード) で使用します。これは、ハフマン ツリーの基本原則に沿ったものです。つまり、すぐに結果が得られる優先度/短いコード、より多くの解析が必要な低優先度です。

于 2011-02-14T08:21:39.780 に答える