ハフマンエンコードは常に最適ですか？

Question

エンコーディングの要件 接頭辞無料 木が完全でなければならないため、大きな木になります。データの固定長さの非エンコードされたストレージがデータをエンコードするよりも効率的になるしきい値はありますか？

Answer 1

エントロピー H(A) この問題はそうです 1.998. 。この問題のハフマンコーディングと固定長のコーディングの両方に、CODEWORDの長さがあります 2. 。そして、FYI Huffmanエンコードを使用しているコーディングは間違っています。 Huffman Encodingは、この問題の固定長と同様のコードも生成します。貪欲なアプローチを使用します。それで a CODEを取得しません 0 しかし、代わりにそれは得られます 00. 。 Huffman Codingを使用して生成するツリーを作り直します。あなたが得るべき木は次のとおりです：

Answer 2

はい、それは常に最適です。

いいえ、固定された長さの非エンコードデータを使用するためにより少ないスペースを使用するしきい値はありません。

私はウェブ上で多くの証拠を見つけましたが、で十分な議論があります ウィキペディアの記事 ハフマンコーディング.

これは、より高い圧縮を実現する他の手法もカバーしています（ハフマンコードが最適な空間の外で作業）。

Answer 3

Huffman Codingは、2つの確率のパワーで人口分布に近似しています。真の分布が2つの確率（および入力記号が完全に相関していない）のパワーで構成されている場合、ハフマンコーディングが最適です。そうでない場合は、範囲エンコーディングでより良くできます。ただし、入力内の特定のシンボルに特定のビットセットを割り当てることが最適です。