2

私は文字のストリームをビットエンコードするためのハフマンコードを研究しており、最適なコードは完全なバイナリツリーで表され、各文字はリーフで表され、すべての内部ノードには正確に2つの子が含まれることを読みました。

ここで完全な二分木が最適な選択である理由を知りたいですか?言い換えれば、ここで完全な二分木の利点は何ですか?

4

3 に答える 3

3

これは選択ではなく、等価です。

最適なハフマン コードは、有限ステート マシンによってデコードされます。

  • 各状態には正確に 2 つの出口があります (次のビットは0または1です)
  • 各状態には 1 つのエントリがあります
  • 出力シンボルを含むすべての状態は停止状態であり、
  • すべての停止ステートには出力シンボルが含まれます

これは、検索ツリーに相当します。

  • すべての内部ノードには正確に 2 つの子があります
  • すべてのノードには親が 1 つだけあります
  • 出力シンボルを含むすべてのノードはリーフ ノードであり、
  • すべてのリーフ ノードには出力シンボルが含まれます

出力シンボルを含まない停止状態/葉ノードを持つ非最適なハフマン コードもあります。このような二分木は完全ではありません。

于 2012-09-17T08:12:01.710 に答える
0

なぜ完全な二分木なのかと尋ねました。それは実際には3つの質問です。

「フル」について質問している場合は、正しく生成されたハフマン コードに対してフルである必要があります。

「バイナリ」について質問している場合、ハフマン コードで遭遇するすべてのビットには 0 または 1 の 2 つの可能性があるため、各ノードには 2 つの分岐が必要です。

ただし、「ツリー」について質問している場合は、コードをツリーとして表す必要はまったくありません。コードを完全に表現するだけでなく、ツリーよりも圧縮ストリームでの短い表現と高速なデコードの両方を容易にする多くの表現があります。

例としては、正規のハフマン コードを使用し、各ビット長でのシンボルの数と、対応するシンボルのリストとして単純に表します。これはpuff.c コードで使用されます。または、一度に数ビットを段階的にデコードするテーブルのセットを生成できます。これはzlib の inflateで使用されます。他にもあります。

于 2018-05-15T23:27:10.737 に答える