トップ過去問一覧応用情報技術者 平成22年・秋 > 問2
問2

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

b

c

d

I

0

1

00

11

II

0

01

10

11

III

0

10

110

111

IV

00

01

10

11

 

I の場合、0011 では aabb なのか cd なのか区別付きません。

II の場合、 0110 では bcなのか ada なのか区別付きません。

III の場合は一意に決まります。

IV の場合は一意に決まります。

この時点で候補は III IV のどちらかになります。問題は最も短くなるものはどれかということなので例として100文字の場合を想定して計算してみましょう。

III の場合、50×1+30×2+10×3+10×3=170

IV の場合、50×2+30×2+10×2+10×2=180

よって III が正解になります。

無料学習システムはこちら
→間違えた問題を繰り返し学習
→分野別学習
→模擬試験モード
デモサイト
無料ユーザ登録

問題文や解説文の内容の正確性については、できるかぎりチェックをしていますが、間違いがある可能性があります。 十分ご注意の上、参考までにご利用ください。