ハフマン符号の計算ツール

正解：B. 1.9ビット

ハフマン符号では、確率の最も小さい2つをまとめる操作を繰り返します。0.1と0.2をまとめて0.3、次に0.3と0.3をまとめて0.6、最後に0.6と0.4をまとめるので、符号長はAが1、Bが2、CとDが3ビットになります。平均符号長は 0.4 × 1 + 0.3 × 2 + 0.2 × 3 + 0.1 × 3 = 1.9 ビットです。

正解：A. 2.25ビット

まず0.1と0.15をまとめて0.25、次に0.2と0.25をまとめて0.45、残りの0.25と0.3をまとめて0.55、最後に0.45と0.55をまとめます。符号長はA、B、Cが2ビット、DとEが3ビットになり、平均符号長は (0.3 + 0.25 + 0.2) × 2 + (0.15 + 0.1) × 3 = 1.5 + 0.75 = 2.25 ビットです。確率の偏りが小さい情報源では、1、2、3、4、4 のような段々の符号長より、長さのそろった符号の方が短くなります。

正解：C. 約93%

ハフマン符号では、0.1と0.3をまとめて0.4、次に0.4と0.6をまとめるので、符号長はAが1、BとCが2ビットです。平均符号長は 0.6 × 1 + 0.3 × 2 + 0.1 × 2 = 1.4 ビットで、効率は 1.30 ÷ 1.4 ≈ 0.93、つまり約93%です。残りの約7%は、符号長が整数のビットに限られるために生じるむだです。

正解：B. 0.78ビット

4種類の確率は、00が0.64、01と10が0.16、11が0.04です。0.04と0.16をまとめて0.2、0.2と0.16をまとめて0.36、最後に0.64とまとめるので、符号長は1、2、3、3ビットとなり、2記号あたりの平均は 0.64 × 1 + 0.16 × 2 + 0.16 × 3 + 0.04 × 3 = 1.56 ビットです。元の1記号あたりでは 1.56 ÷ 2 = 0.78 ビットです。1記号ずつでは0と1に1ビットずつ割り当てるしかありませんが、まとめて符号化すると、エントロピーの約0.72ビットに近づけられます。