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

正解は ウ です。 ビット列から一意に復元できるかは、 ある文字の符号が別の文字の符号の先頭部分になっていないか で確かめます。復元できるものの中で、出現頻度を重みにした平均ビット数を比べます。 方法 a b c d 一意に復元 平均ビット数 ア 0 1 00 11 ×(00 が aa か c か分からない) - イ 0 01 10 11 ×(010 が ac か ba か分からない) - ウ 0 10 110 111 ○ 1.7 エ 00 01 10 11 ○(全て2ビット) 2.0 ウ:$1\times0.5+2\times0.3+3\times0.1+3\times0.1=1.7$ ビット エ:全ての文字が2ビットなので 2.0 ビット ウは、出現頻度の高い a に短い符号を割り当て、どの符号も他の符号の先頭部分になっていません。そのため一意に復元でき、平均ビット数も最小です。

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

出典令和2年度 10月 応用情報技術者試験 午前 問4

a

b

c

d

ア

0

1

00

11

イ

0

01

10

11

ウ

0

10

110

111

エ

00

01

10

11