令和2年度 高度共通 午前I（PM試験） 問2

正解：ウ

AI解説

符号化されたビット列を一意に復号するには、どの符号語も他の符号語の先頭部分（語頭）にならないという語頭条件（プレフィックス条件）を満たすのが確実である。平均符号長は各文字の出現頻度×符号長の総和で求める。ウは頻度の高いaに1ビット、bに2ビット、c・dに3ビットを割り当てた語頭符号で、平均符号長は0.5×1＋0.3×2＋0.1×3＋0.1×3＝1.7ビットとなり、固定長2ビットより短い。これはハフマン符号の考え方である。 ア: ある符号語が他の符号語の語頭と重なる割当てであり、ビット列の区切りが一意に定まらないため復号できない。 イ: 同様に一意に復号するための条件を満たさない割当てであり、元のメッセージを正しく復元できない。 ウ: 正しい。語頭条件を満たして一意に復号可能であり、出現頻度の高い文字ほど短い符号を割り当てているため平均符号長が1.7ビットと最短になる。 エ: 全文字2ビットの固定長符号で一意復号は可能だが、平均符号長は2.0ビットとなりウの1.7ビットより長い。 💡 出現頻度に偏りがあるときは、高頻度の文字に短い符号を与えると平均符号長を圧縮できる（ハフマン符号）。ただし語頭条件を満たさなければ復号不能なので、まず一意復号の可否、次に平均長の順で検討する。