応用情報技術者試験 応用情報技術者試験 平成28年度春期 午前 問4: a，b，c，d の 4 文字から成るメッセージを符号化してビット列にする方法として表のア〜エの 4 通りを考えた。この表は a，b，c，d の各 1 文字を符号

問題本文

a，b，c，d の 4 文字から成るメッセージを符号化してビット列にする方法として表のア〜エの 4 通りを考えた。この表は a，b，c，d の各 1 文字を符号化するときのビット列を表している。メッセージ中での a，b，c，d の出現頻度は，それぞれ 50%，30%，10%，10%であることが分かっている。符号化されたビット列から元のメッセージが一意に復号可能であって，ビット列の長さが最も短くなるものはどれか。

選択肢

• ア.a: 0，b: 1，c: 00，d: 11
• イ.a: 0，b: 01，c: 10，d: 11
• ウ.a: 0，b: 10，c: 110，d: 111
• エ.a: 00，b: 01，c: 10，d: 11

正解

ウ. a: 0，b: 10，c: 110，d: 111

解説

ハフマン符号化のように、まず「一意に復号できるか(ある符号が別の符号の接頭辞になっていない＝語頭条件を満たすか)」を確認し、次に出現頻度を重みにした平均ビット長を比べて最短のものを選ぶ問題である。ウは 0/10/110/111 でどの符号も他の符号の先頭に現れず一意復号可能で、平均長は 0.5×1+0.3×2+0.1×3+0.1×3=1.7 ビットとなり、固定長(各2ビット＝平均2ビット)のエより短く、最も効率がよいので正解はウである。

選択肢ごとの解説

• ア.a=0,b=1,c=00,d=11 は a(0)が c(00)の先頭、b(1)が d(11)の先頭になっており、ビット列の区切りが一意に定まらず復号できないため誤り。
• イ.a=0,b=01,c=10,d=11 は a(0)が b(01)の先頭になっており、例えば 0101 が aba とも bb とも解釈でき一意に復号できないため誤り。
• ウ.どの符号も他の符号の接頭辞になっておらず一意に復号でき、頻度の高い a に最短の1ビット、頻度の低い c・d に3ビットを割り当てているため平均1.7ビットと最短になり正しい。
• エ.a=00,b=01,c=10,d=11 はすべて2ビットの固定長で一意に復号できるが、平均長は2ビットでウの1.7ビットより長く、最短ではないため誤り。