出現頻度に基づく可変長符号化と平均ビット長

正解は「ウ」です。 可変長符号が一意に復元可能であるためには、どの符号語も他の符号語の「接頭辞（プレフィックス）」になっていないこと（瞬時復号可能・プレフィックス条件）が必要です。 【各選択肢のプレフィックス検証】 ・ア：a = '0', b = '1', c = '01', d = '10' 符号 '01' の先頭が '0'（a の符号）と重複し、'10' の先頭が '1'（b の符号）と重複するため、復号が一意に定まりません（例: '01' が "c" なのか "ab" なのか判定不能）。 ・イ：a = '0', b = '01', c = '011', d = '0111' a = '0' が b, c, d の先頭と一致しており、プレフィックス条件を満たさず一意復元できません。 ・ウ：a = '0', b = '10', c = '110', d = '111' ハフマン符号の構造を持っており、どの符号語も他の符号語の接頭辞になっていません。木構造を用いて一意に復元可能です。 ・エ：固定長符号（すべて 2 ビット）であり、一意復元は可能です。 【ウとエの平均ビット長の比較】 各文字の出現頻度は a = 50%(0.5), b = 30%(0.3), c = 10%(0.1), d = 10%(0.1) です。 ・ウの平均ビット長： $1 \text{ビット} \times 0.5 + 2 \text{ビット} \times 0.3 + 3 \text{ビット} \times 0.1 + 3 \text{ビット} \times 0.1$ $= 0.5 + 0.6 + 0.3 + 0.3 = 1.7$ ビット/文字 ・エの平均ビット長： すべての文字が 2 ビットなので、平均 $2.0$ ビット/文字 したがって、一意に復元可能であり平均ビット数が最も少 ないもの は「ウ」（1.7 ビット）です。

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

出典令和2年度 10月 高度情報処理技術者試験 午前Ⅰ

a

b

c

d

ア

0

1

00

11

イ

0

01

10

11

ウ

0

10

110

111

エ

00

01

10

11