情報理論 第12回　ハフマン符号 練習問題解答例

• 練習問題1
上の例の条件で、a～f を扱える最短の等長符号と、その平均符号長 $L$ を求めよ (必要なのは表と数値)。

最短の等長符号は、例えば


シンボル	符号語
a	000
b	001
c	010
d	011
e	100
f	101

で、計算するまでもなく平均符号長 $L$ は $3$。

• 練習問題2
上の例で求めたハフマン符号の平均符号長 $L$ を求めよ。

a～f に対応する符号語の長さがそれぞれ3, 2, 4, 2, 4, 2なので、 $L=(0.25+0.35+0.18)\times 2+0.14\times 3+(0.02+0.06)\times 4=1.56+0.42+0.32=2.3$

• 練習問題3
a～h の8つのシンボルを扱える最短の等長符号と、その平均符号長 $L$ を求めよ (必要なのは表と数値)。

最短の等長符号は、例えば


シンボル	符号語
a	000
b	001
c	010
d	011
e	100
f	101
g	110
h	111

で、計算するまでもなく平均符号長 $L$ は $3$。

• 練習問題4
シンボルが a～h の8つで、情報源事象系が $X=\left[\begin{array}{cccccccc}{x}_a& x_b& x_c& x_d& x_e& x_f& x_g& x_h\\ 0.05& 0.16& 0.07& 0.13& 0.18& 0.09& 0.11& 0.21\end{array}\right]$ である場合のハフマン符号を求めよ。また、その平均符号長 $L$ を求めよ (必要なのは図、表、数値)。

ハフマン符号を求めるための符号の木とハフマン符号は


シンボル 符号語 a 1111 b 101 c 1110 d 110 e 100 f 011 g 010 h 00

のようになり、平均符号長は $L=0.21\times 2+(0.16+0.13+0.18+0.09+0.11)\times 3+(0.05+0.07)\times 4=0.42+0.67\times 3+0.12\times 4=0.42+2.01+0.48=2.91$ となる。

• 練習問題5
シンボルが a～h の8つで、情報源事象系が $X=\left[\begin{array}{cccccccc}{x}_a& x_b& x_c& x_d& x_e& x_f& x_g& x_h\\ 0.01& 0.03& 0.45& 0.03& 0.07& 0.02& 0.04& 0.35\end{array}\right]$ である場合のハフマン符号を2通り求めよ。また、その平均符号長 $L$ を求めよ (必要なのは図x2、表x2、数値x1)。
(ここでいう「2通り」とは、最長の符号語の長さが異なる、構造的に異なったもの2つということ)

タイプ1

シンボル 符号語 a 111111 b 11101 c 0 d 11110 e 110 f 111110 g 11100 h 10

この符号の平均符号長は $L=0.45\times 1+0.35\times 2+0.07\times 3+(0.03+0.03+0.04)\times 5+(0.01+0.02)\times 6=0.45+0.7+0.21+0.1\times 5+0.03\times 6=1.36+0.5+0.18=2.04$ となる。

タイプ2

シンボル 符号語 a 11111 b 11010 c 0 d 11011 e 1100 f 11110 g 1110 h 10

この符号の平均符号長は $L=0.45\times 1+0.35\times 2+(0.07+0.04)\times 4+(0.01+0.03+0.03+0.02)\times 5=0.45+0.7+0.11\times 4+0.09\times 5=1.15+0.44+0.45=2.04$ となる。

(ハフマン符号はコンパクト符号で、$L$ は最小値なはずなので、どちらか片方でだけ計算すれば十分)


最初の3回の組み合わせ方をタイプ2と同じようにして、次の組み合わせ方を変えたものもハフマン符号としては正しいが、これだとタイプ1と同様に最長の符号語の長さは6になってしまう。


シンボル 符号語 a 111111 b 11100 c 0 d 11101 e 110 f 111110 g 11110 h 10