math - ハフマン コードの文字の単一ビット コードの条件は?

Question

これは私が学校の設定で遭遇した質問ですが、私を悩ませ続けているので、ここで質問することにしました.

ハフマン圧縮では、固定長シーケンス (文字) が可変長シーケンスでエンコードされます。コード シーケンスの長さは、ソース文字の頻度 (または確率) によって異なります。

私の質問は次のとおりです。その文字が単一ビットでエンコードされる最小最高文字頻度は何ですか?

Answer 1

答えは 0.4 であることがわかります。つまり、最高頻度pがp >= 0.4の場合、対応する文字の 1 ビット コードが保証されます。つまり、これは十分条件です。

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

これを判断する方法は、コード ツリーの構築方法、特に最後に残った 3 つのサブツリーの頻度を調べることです。Johnsen の「バイナリ ハフマン コードの冗長性について」(1980 年) に証明が掲載されています(残念ながら、これは有料リンクです)。

Answer 2

一般に、入力シンボル ストリームの約 50% は、Huffman が単一ビットとしてコード化するための特定のシンボルで構成されている必要があります。この理由は、ハフマン コーディングの仕組み (あるシンボルのエンコーディングを別のシンボルのプレフィックスにすることはできません) により、1 つのシンボルを 1 ビットでエンコードすることにより、他のすべてのシンボルの最初のビットを反対の値にする必要があるためです (つまり、1 つのシンボルが としてエンコードされている場合、他のすべてのシンボルは少なくとも 1 ビット以上で0始まる必要があります)。1任意のビット長に対して可能なエンコード スペースの半分を排除しているため、損益分岐点にするには、入力されるシンボルの少なくとも半分をエンコードする方法を取得する必要があります。

シンボル スペースが 3 つのシンボルのみで構成される特殊なケースがあることに注意してください。このような場合、最も頻度の高いシンボルが 1 ビットでエンコードされます (他の 2 つは、選択されていない最初のビット値の 2 番目のビットのバリエーションになるため) - 2 つ以上のシンボルの確率が等しく大きい場合、どちらかをエンコードできます。したがって、3 シンボルの場合、たとえば 34% の確率を持つシンボルは、理論的には 1 ビット (たとえば0) としてコーディングされ、他の 2 つのシンボルは 33% 以下の確率で および としてコーディングされる可能性があり10ます11。

したがって、すべての可能性を考慮している場合、技術的には、1/3 以上のものは単一ビットとしてエンコードされる可能性があります (3 シンボルの場合)。