平成28年度 春期 午前 問4

✓ これが正解ウ0 10 110 111

解説

読み方が一通りに決まる中で、平均が最短の割当てを選びます。

関門は二つあります。順番を間違えると必ずつまずくので、先に一つ目から片づけます。一つ目は、続けて並べたビット列を元のメッセージに戻せるかどうかです。見分け方は簡単で、どの符号も、ほかの符号の先頭になっていないことを確かめます。この条件を満たしていれば、先頭から読み進めるだけで区切りが決まります。二つ目は、符号化した後の長さです。一文字あたりの平均は、符号の長さに出現頻度を掛けて足し合わせれば出ます。この二つを満たすのが、a に 0、b に 10、c に 110、d に 111 を割り当てた案です。どの符号もほかの先頭にはなっていないので復号できますし、平均は 0.5 × 1 ＋ 0.3 × 2 ＋ 0.1 × 3 ＋ 0.1 × 3 ＝ 1.7 ビットになります。すべてを 2 ビットにそろえた案は復号できますが平均は 2.0 ビットなので、こちらのほうが短く済みます。この割当ては、出現頻度の小さいものから束ねていくハフマン符号の作り方と同じ形になっており、束ねた深さがそのまま符号の長さになっています。

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

• ア0 1 00 11：a に 0、c に 00 を与えた案です。0 が 00 の先頭になっているので、00 という並びが a の二つ続きとも c 一文字とも取れてしまい、元に戻すときに読み方が決まりません。
• イ0 01 10 11：a の 0 が b の 01 の先頭になっています。0110 という並びは、b と c の二文字とも読めますし、a と d と a の三文字とも読めるので、二通りに分かれてしまいます。
• エ00 01 10 11：四文字すべてを 2 ビットにそろえた案です。区切りは一通りに決まりますが、100 文字あたり 200 ビット必要で、出現の偏りを長さに生かせていません。