私は文字のストリームをビットエンコードするためのハフマンコードを研究しており、最適なコードは完全なバイナリツリーで表され、各文字はリーフで表され、すべての内部ノードには正確に2つの子が含まれることを読みました。
ここで完全な二分木が最適な選択である理由を知りたいですか?言い換えれば、ここで完全な二分木の利点は何ですか?
私は文字のストリームをビットエンコードするためのハフマンコードを研究しており、最適なコードは完全なバイナリツリーで表され、各文字はリーフで表され、すべての内部ノードには正確に2つの子が含まれることを読みました。
ここで完全な二分木が最適な選択である理由を知りたいですか?言い換えれば、ここで完全な二分木の利点は何ですか?
これは選択ではなく、等価です。
最適なハフマン コードは、有限ステート マシンによってデコードされます。
これは、検索ツリーに相当します。
出力シンボルを含まない停止状態/葉ノードを持つ非最適なハフマン コードもあります。このような二分木は完全ではありません。
なぜ完全な二分木なのかと尋ねました。それは実際には3つの質問です。
「フル」について質問している場合は、正しく生成されたハフマン コードに対してフルである必要があります。
「バイナリ」について質問している場合、ハフマン コードで遭遇するすべてのビットには 0 または 1 の 2 つの可能性があるため、各ノードには 2 つの分岐が必要です。
ただし、「ツリー」について質問している場合は、コードをツリーとして表す必要はまったくありません。コードを完全に表現するだけでなく、ツリーよりも圧縮ストリームでの短い表現と高速なデコードの両方を容易にする多くの表現があります。
例としては、正規のハフマン コードを使用し、各ビット長でのシンボルの数と、対応するシンボルのリストとして単純に表します。これはpuff.c コードで使用されます。または、一度に数ビットを段階的にデコードするテーブルのセットを生成できます。これはzlib の inflateで使用されます。他にもあります。