ハフマンコードの文字のシングルビットコードの条件？

Question

これは私が学校の環境で出会った質問ですが、それは私を悩ませ続けているので、ここで尋ねることにしました。

Huffman圧縮では、固定長シーケンス（文字）が可変長シーケンスでエンコードされています。コードシーケンスの長さは、ソース文字の周波数（または確率）に依存します。

私の質問は、最も高い文字周波数は何ですか、その文字は1つのビットでエンコードされますか？

Answer 1

答えは0.4、つまり最高の周波数の場合、 p は p> = 0.4, 、対応する文字の1ビットコードが保証されます。言い換えれば、これは十分な条件です。

また、p> = 1/3が必要な状態であることも事実です。つまり、例があるかもしれません 0.4> p> = 1/3, 、そして最短のコードは1ビットですが、そのようなケースはありません p <1/3.

それについて推論する方法は、特に3つの最後に生き残ったサブツリーの周波数で、コードツリーの構築方法を見ることです。ジョンセンに証明が表示されます、 「バイナリハフマンコードの冗長性について」、1980年 （残念ながら、これは有料リンクです）。

Answer 2

一般に、入ってくるシンボルストリームの約50％は、ハフマンがそれを単一としてコーディングするための特定のシンボルで構成する必要があります。この理由は、ハフマンコーディングの仕組み（あるシンボルのエンコードは別のシンボルの接頭辞になることはできない）のために、シンボルを1つのビットでエンコードすることにより、最初のビットが必要であることが必要です。 他のすべてのシンボル 反対の値になります（つまり、1つのシンボルが次のようにエンコードされている場合 0, 、他のすべてはから始めなければなりません 1 さらに、少なくとも1ビット）。特定のビットの長さで可能なエンコードスペースの半分を排除するため、入力されているシンボルの少なくとも半分をエンコードする方法を獲得する必要があります。

シンボル空間が3つのシンボルのみで構成される特別なケースがあることに注意してください。そのような場合、どちらのシンボルが最大の周波数を持っている場合は1ビットでエンコードされます（他の2つは選択されていない最初のビット値の2番目のビットのバリエーションになるため） - 2つ以上が等しく高い確率を持っている場合、どちらかをエンコードできます。したがって、3-Symbolの場合、たとえば34％の確率を含むシンボルが理論的に単一のビットとしてコード化できる可能性があります（たとえば、たとえば、 0）他の2つは33％以下の確率を持ち、次のようにコーディングされる可能性があります 10 と 11.

あなたが検討しているなら すべて 可能性、技術的には1/3以上は、単一のビットとしてエンコードされる可能性があります（3シンボルの場合）。