応用情報技術者試験 応用情報技術者試験 平成29年度秋期 午前 問3: 四つのアルファベット a 〜 d から成るテキストがあり，各アルファベットは 2 ビットの固定長 2 進符号で符号化されている。このテキストにおける各アルファベ

問題本文

四つのアルファベット a 〜 d から成るテキストがあり，各アルファベットは 2 ビットの固定長 2 進符号で符号化されている。このテキストにおける各アルファベットの出現確率を調べたところ，表のとおりであった。各アルファベットの符号を表のような可変長 2 進符号に変換する場合，符号化されたテキストの，変換前に対する変換後のビット列の長さの比は，およそ幾つか。

選択肢

• ア.0.75
• イ.0.85
• ウ.0.90
• エ.0.95

正解

エ. 0.95

解説

可変長符号(ハフマン符号など)では，出現頻度の高い文字に短いビット列を割り当てることで，1文字あたりの平均符号長を短くできる。比較には出現確率を重みにした平均符号長(期待ビット長)を使う。変換前は全文字一律2ビットなので平均は2ビット。変換後の平均符号長は a:1×0.4 ＋ b:2×0.3 ＋ c:3×0.2 ＋ d:3×0.1 ＝ 0.4＋0.6＋0.6＋0.3 ＝ 1.9 ビットとなる。よって長さの比は 1.9 ÷ 2 ＝ 0.95 で，エが正しい。