令和2年度 秋期 応用情報技術者試験 午前 問4

この問題は「ハフマン符号化」に関連するものです。
ハフマン符号では、頻度の高い文字を短いビット列で表し、頻度の低い文字を長いビット列で表現することで、全体の平均ビット長を最小化します。

選択肢の検証

ア

• 符号: a=0, b=1, c=00, d=11
• 問題点: c = 00 と a = 0 の繰り返しが区別できず、一意に復号できません。
• 結果: 不適切（一意に復号不可）

イ

• 符号: a=0, b=01, c=10, d=11
• 問題点: 符号化後のビット列に「00110」がある場合、
• abc (00110)
• aada (00110)
  の区別がつかず、一意に復号できません。
• 結果: 不適切（一意に復号不可）

ウ

• 符号: a=0, b=10, c=110, d=111
• 特徴: プレフィックス符号であり、一意に復号可能。
• 各文字が他の文字の接頭辞になっていません。
• 平均ビット長の計算:
  (1 × 0.5) + (2 × 0.3) + (3 × 0.1) + (3 × 0.1) = 1.7
• 結果: 適切（復号可能で比較的短い）

エ

• 符号: a=00, b=01, c=10, d=11
• 特徴: 各文字が2ビットで構成されており、一意に復号可能。
• ただし、aに2ビットが割り当てられており効率が悪い。
• 平均ビット長: 2.0
• 結果: 不適切（ビット長が長い）

結論

最も適切な選択肢は「ウ」です。
一意に復号可能で、ビット列の長さが最短に近い方式です。

答え

ウ: a = 0, b = 10, c = 110, d = 111