DE-S27｜情報Ⅰ 対策問題

正答

1

この問題のポイント

平均符号長の計算（ハフマン法の効果） を問う問題です。「頻度×符号長」の合計という期待値の計算を身につけましょう。

解説

可変長符号では文字ごとに符号の長さが違うため、「1文字あたり平均何ビットか(平均符号長)」を、各文字の出現頻度を重みにして計算します。平均符号長 = Σ(出現頻度 × その文字の符号長)です。

手順どおり計算します。

1. Aの分 = 0.5 × 1ビット = 0.5ビット(A=0は1ビットの符号)。
2. Bの分 = 0.25 × 2ビット = 0.5ビット(B=10は2ビット)。
3. Cの分 = 0.25 × 2ビット = 0.5ビット(C=11は2ビット)。
4. 平均符号長 = 0.5 + 0.5 + 0.5 = 1.5ビット/文字。
5. 100文字の総ビット数 = 1.5 × 100 = 150ビット。

比較の基準は固定長です。3種類の文字を固定長で区別するには2ビット必要(2¹=2では足りず、2²=4で足りる)なので、100文字で200ビット。ハフマン法により 200 → 150ビット、つまり25%節約できたことになります。「頻度の高いAに1ビットの短い符号を与えたから縮んだ」という因果関係まで説明できるようにしましょう。

共通テストでは、まさにこの「固定長なら何ビット→ハフマンなら何ビット→何%削減」という3段の計算が出題されています。頻度の合計が100%になっているかを確かめてから計算を始めると、ミスに気づきやすくなります。

選択肢の確認

1．○ 平均符号長1.5ビット × 100文字 = 150ビット。
2．× 200ビットは固定長(全文字2ビット)で符号化した場合の値。
3．× 100ビットは全文字を1ビットにした場合だが、1ビットでは3種類を区別できないので実現不可能。
4．× 300ビットは全文字を3ビットにした場合の値で、圧縮の意味がない。

ここだけは覚えよう

平均符号長=Σ(頻度×符号長)、総ビット数=平均×文字数 — 固定長との差が圧縮の節約分。