情報源記号 A、B、C、D、Eをそれぞれ 0.12、0.3、0.05、0.45、0.08の確率で発生する無記憶5元情報源に対する2元ハフマン符号として、最も適切なものはどれか。ただし、例えばAを100と符号化することをA→100と書くことにする。
① A→100、B→11、C→1010、D→0、E→1011
② A→100、B→00、C→1110、D→0、E→1011
③ A→100、B→110、C→111、D00、E→01
④ A→110、B→101、C→111、D→000、E→100
⑤ A→110、B→1110、C→0、D→1111、E→10
①
ハフマン符号は出現率の多い文字から順に
0、10、110、1110、 ・・・、と符号化し、
最後の2文字は 11・・・10、と 11・・・11
で表し、データ量を圧縮する。
この考え方では、
D:0
B:10
A:110
C:1110
E:1111
となる。
0と1を入れ替えて
D:1
B:01
A:001
C:0001
E:0000
でも可能である。
これをさらに応用して
D:0
B:11
A:100
C:1010
E:1011
としても A～Eを一意に表すとことができ、データの圧縮も可能である。
① 正しい。平均ビット長は
1×0.45 ＋ 2×0.3 ＋ 3×0.12 ＋ 4×0.08 ＋ 4×0.05 = 1.93である。
② 例えば、000のビット列の場合、BD なのか DB なのか DDD なのか区別できない。
③ 2×0.45 ＋ 3×0.3 ＋ 3×0.12 ＋ 3×0.08 ＋ 2×0.05 = 2.5で①より長くなる。
④ ビット列が同じであり、ハフマン符号化ではない。
⑤ 発生確率の一番高いDに4ビット割り当てると圧縮率が悪くなる。
| Ⅲ－２ | 目次 | Ⅲ－４ |