表2の方法で符号化する場合、 \(p_{b1}\)～\(p_{b7}\) と \(p_{w1}\)～\(p_{w7}\) がすべて
であり、\(p_{b8}\), \(p_{w8}\)
がどちらも
の場合の平均符号長 \(L\) を求めてください。ただし、結果は四捨五入して小数第2位までにしてください。
解答
シンボルの平均の長さは
\(L_s = \)
なので、平均符号長は
\(L = \)
概要の符号の木を元にしてハフマン符号の表を完成させ、その場合の平均符号長を求めてください。
解答
符号の木をもとに表を書き下すと以下のようになる。
シンボル
の並び |
符号語 |
| B |
111111 |
| BB |
111110 |
| BBB |
111101 |
| BBBB |
111100 |
| BBBBB |
111011 |
| BBBBBB |
111010 |
| BBBBBBB |
111001 |
| BBBBBBBB |
10 |
| W |
111000 |
| WW |
110111 |
| WWW |
110110 |
| WWWW |
110101 |
| WWWWW |
110100 |
| WWWWWW |
11001 |
| WWWWWWW |
11000 |
| WWWWWWWW |
0 |
シンボルの平均の長さは
\(L_s=\)
((1+2+3+4+5+6+7) × 0.01 + 8 × 0.43) × 2 = 7.44
符号長は「W8個」が1bit、「B8個」が2bit、「W7個」と「W6個」が5bitで、それ以外の12通りの並びではすべて6bitになる。
よって、シンボルの並びに対応する符号語の平均の長さ \(\bar{L}\) は
\(\bar{L}\)
= 0.43 × (1+2) + 0.01 × (5 × 2 + 6 × 12)
= 1.29 + 0.82
= 2.11 (bit)
よって、平均符号長は
\(L=\bar{L}/L_s\)
=2.11 / 7.44
= 0.283...
≒ 0.28 (bit)
となる。