一意に復号できて最も短い符号
出典: 令和2年度 10月 応用情報技術者試験 午前 問4 (IPA)
a，b，c，d の 4 文字から成るメッセージを符号化してビット列にする方法として表のア～エの 4 通りを考えた。この表は a，b，c，d の各 1 文字を符号化するときのビット列を表している。メッセージ中での a，b，c，d の出現頻度は，それぞれ 50%，30%，10%，10%であることが分かっている。符号化されたビット列から元のメッセージが一意に復号可能であって，ビット列の長さが最も短くなるものはどれか。
| a | b | c | d | |
|---|---|---|---|---|
| ア | 0 | 1 | 00 | 11 |
| イ | 0 | 01 | 10 | 11 |
| ウ | 0 | 10 | 110 | 111 |
| エ | 00 | 01 | 10 | 11 |
- ア ア (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 が c の符号 00 の先頭になっているので、「00」が aa か c か区別できず、一意に復号できません。
- イ: a の符号 0 が b の符号 01 の先頭になっているので、例えば「010」が「ac」か「ba」か区別できず、一意に復号できません。
- ウ: どの符号も他の符号の先頭になっておらず一意に復号でき、平均 1.7 ビットで最も短いので正しい答えです。
- エ: エは一意に復号できますが、平均 2 ビットで、ウの 1.7 ビットより長くなります。
ポイント
- 一意に復号できる には、どの符号も他の符号の先頭部分になっていない (接頭符号) 必要があります。
・ア: a (0) が c (00) の先頭になっていて、「00」が aa か c か区別できません。
・イ: a (0) が b (01) の先頭になっていて、区別できない場合があります。 - ウとエは一意に復号できます。平均の長さを比べると、
・ウ: 0.5 × 1 ＋ 0.3 × 2 ＋ 0.1 × 3 ＋ 0.1 × 3 = 1.7 ビット
・エ: 全て 2 ビットなので 2 ビット - よって ウ が最も短くなります。