可変長符号化による圧縮の比
出典: 平成29年度 秋期 応用情報技術者試験 午前 問3 (IPA)
四つのアルファベット a～d から成るテキストがあり，各アルファベットは 2 ビットの固定長 2 進符号で符号化されている。このテキストにおける各アルファベットの出現確率を調べたところ，表のとおりであった。各アルファベットの符号を表のような可変長 2 進符号に変換する場合，符号化されたテキストの，変換前に対する変換後のビット列の長さの比は，およそ幾つか。
| アルファベット | a | b | c | d |
|---|---|---|---|---|
| 出現確率（%） | 40 | 30 | 20 | 10 |
| 可変長 2 進符号 | 0 | 10 | 110 | 111 |
- ア 0.75
- イ 0.85
- ウ 0.90
- エ 0.95
正解と解説を見る
正解: エ
- ア: 0.75 は平均 1.5 ビットのときの比です。計算すると平均は 1.9 ビットです。
- イ: 0.85 は平均 1.7 ビットのときの比です。c と d の符号は 3 ビットです。
- ウ: 0.90 は平均 1.8 ビットのときの比です。出現確率を掛けて足し直すと 1.9 ビットです。
- エ: 平均 1.9 ビット ÷ 2 ビット = 0.95 なので正しい答えです。
ポイント
- 可変長符号の 1 文字あたりの平均ビット数は、
0.4 × 1 ＋ 0.3 × 2 ＋ 0.2 × 3 ＋ 0.1 × 3 = 0.4 ＋ 0.6 ＋ 0.6 ＋ 0.3 = 1.9 ビット - 変換前は固定長で 1 文字 2 ビット なので、比は 1.9 ÷ 2 = 0.95 です。