平成22年度 秋期 午前 問2

✓ これが正解ウa＝0 ／ b＝10 ／ c＝110 ／ d＝111

解説

先に一意に読めるかを見て、残った中で平均長を比べます。

この問いには関門が 2 つあります。順番を守らないと落ちる作りなので、先に順番を決めてしまいます。関門の 1 つ目は、符号化されたビット列が一通りに読めるかどうかです。ある文字の符号が別の文字の符号の先頭と同じになっていると、区切り方が 2 通りできてしまい、元のメッセージに戻せません。これを避ける条件を語頭条件と呼びます。関門の 2 つ目が、1 文字あたりの平均ビット数です。出現頻度に符号の長さを掛けて足し合わせ、短いほうを採ります。正解は、出現頻度の高い文字ほど短い符号を割り当てた側で、語頭条件を満たしたうえで 0.5×1 ＋ 0.3×2 ＋ 0.1×3 ＋ 0.1×3 ＝ 1.7 ビットとなります。これはハフマン符号の考え方そのもので、同じ頻度から木を組み立てても 1・2・3・3 ビットという同じ長さになります。平均だけを先に比べると、そもそも復号できない符号を最短として選んでしまいます。

ほかの選択肢はなぜ違うのか

• アa＝0 ／ b＝1 ／ c＝00 ／ d…：1 ビットの符号が 2 ビットの符号の先頭と重なっています。0 が 2 つ並んだ列を、1 文字が 2 回とも、別の 1 文字とも読めてしまうため、平均が最短でも元のメッセージに戻せません。
• イa＝0 ／ b＝01 ／ c＝10 ／ …：0 で始まる符号が 2 つあり、片方がもう片方の頭に含まれます。010 という列が ac とも ba とも読めて区切り位置が一通りに定まらないので、この関門を越えられません。
• エa＝00 ／ b＝01 ／ c＝10 ／…：4 つとも同じ長さなので区切りには困りませんが、出現頻度の偏りをまったく使っていません。平均は 2.0 ビットとなり、可変長の側の 1.7 ビットに及びません。