修了試験 2021-12-12実施分 基本情報技術者試験 問6

解説

正解は3です。 一意に復号できる符号のうち、平均符号長が最短のものを選ぶ問題です。 一意に復号できるかは、ある符号が他の符号の先頭部分（接頭語）になっていないかで判断できます。 平均符号長は、各文字の符号長に出現頻度を掛けて足し合わせた値です。 【計算】 選択肢3の平均符号長は、1×0.5＋2×0.3＋3×0.1＋3×0.1です。 ＝0.5＋0.6＋0.3＋0.3＝1.7（ビット）です。 選択肢4の平均符号長は、すべて2ビットなので2.0（ビット）です。 【選択肢別解説】 1：× aの0がcの00の先頭と一致し、bの1がdの11の先頭と一致します。 ビット列00がaaなのかcなのか区別できず、一意に復号できません。 2：× aの0がbの01の先頭と一致します。 例えば010は、0と10（ac）とも、01と0（ba）とも読めるので、一意に復号できません。 3：○ 0、10、110、111はどの符号も他の符号の先頭部分になっていないので、一意に復号できます。 平均符号長は1.7ビットで、一意に復号できる候補の中で最短です。 4：× 4文字とも2ビットの固定長なので一意に復号できます。 しかし平均符号長は2.0ビットで、選択肢3の1.7ビットより長くなります。 【ポイント】 出現頻度の高い文字に短い符号を割り当て、接頭語の重複を避けた符号がハフマン符号です。 「一意に復号できるか」を先に確認し、残った候補の平均符号長を比べるのが解き方の基本です。