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 |
答え ウ
【解説】
ア | この規則だと“aa”を符号化すると“00”になり、これは“c”との区別ができず、復号できないので符号化のルールが条件に合わない。 |
イ | この規則だと“ba”を符号化すると“010”になり、これは“ac”との区別ができず、復号できないので符号化のルールが条件に合わない。 |
ウ | この符号化ルールは問題ないので、ビット列の平均値を求めると出現頻度は、a:長さ1×50%、b:長さ2×30%、c:長さ3×10%、d:長さ3×10%なので、0.5+0.6+0.3+0.3=1.7である。 |
エ | この符号化ルールは問題ないので、ビット列の平均値を求めると出現頻度は、a:長さ2×50%、b:長さ2×30%、c:長さ2×10%、d:長さ2×10%なので、1.0+0.6+0.2+0.2=2.0である。 |
【キーワード】
・符号化