動画の解説を参照
前回見たように、シンボルが多数ある場合にハフマン符号を使うと、シンボルの出現率が偏っているほど平均符号長が短く、効率が良くなります。
しかし、シンボルが2種類だけの場合はハフマン符号を使っても効率は改善されません。
例
モノクロの画像は白と黒のどちらかのピクセルだけで構成されるので、白と黒のピクセルをシンボル W, B と考えれば、この32x32ピクセルの画像はこの2文字からなる「文」として扱うことができます。
「一番上の行を左から右に順に見て、次はその下の行をまた左から右に...」という読み方をすれば、これは長さ \(32\times32=1024\) の文と考えることができます。
|
| 図1 |
図1のような画像では白のピクセルが黒より多く、シンボル W が発生する確率は B が発生する確率よりも高くなります。
しかし、シンボルが2種類しかないので、ハフマン符号は結局
となり、画像の情報を送るにはピクセル数と同じ1024bitのデータが必要になってしまいます。
動画の解説を参照
上のケースで「Bがいくつ続いたか」「Wがいくつ続いたか」に応じて、シンボルの並びに対して符号語を作ってみます。
符号語の先頭には「何が」、それに続くものとして「続いた数-1」を入れることにして、続いた数を1～8の範囲で許容することにすると、種類用に1bit、カウント用に3bit使って以下のような「シンボルの並びに対する等長符号」ができます。
このような符号を
固定長ランレングス符号といいます。
表1
シンボル
の並び |
意味 |
符号語 |
| B |
Bが1個 |
0000 |
| BB |
Bが2個 |
0001 |
| BBB |
Bが3個 |
0010 |
| BBBB |
Bが4個 |
0011 |
| BBBBB |
Bが5個 |
0100 |
| BBBBBB |
Bが6個 |
0101 |
| BBBBBBB |
Bが7個 |
0110 |
| BBBBBBBB |
Bが8個 |
0111 |
| W |
Wが1個 |
1000 |
| WW |
Wが2個 |
1001 |
| WWW |
Wが3個 |
1010 |
| WWWW |
Wが4個 |
1011 |
| WWWWW |
Wが5個 |
1100 |
| WWWWWW |
Wが6個 |
1101 |
| WWWWWWW |
Wが7個 |
1110 |
| WWWWWWWW |
Wが8個 |
1111 |
この符号を使えば、上の例の画像の上側82ピクセル分 は
Wが8個, Wが8個, Wが8個, Wが8個, Wが7個, Bが2個, Wが8個, Wが8個, Wが5個, Bが4個
→ 1111 1111 1111 1111 1110 0001 1111 1111 1100 0011
となり、40bitのデータで送ることができます (白黒でなくても、色の数がそれほど多くない場合であれば符号語の先頭に割り当てるbit数を色数に応じて増やせば同様のことができます)。
この方法の効率は、BとWの単独の出現率ではなく、その切り替わりがどれほど頻繁に起こるかで変わります。
例として、BとWがそれぞれ1つ、2つ、4つ、8つずつ続く場合を考えてみましょう。
どの場合もシンボル数は 1024個ですが、全体を符号化したものの情報量は異なります。平均符号長は全体の情報量をシンボル数で割ったものなので、
| 連続数 |
全体の情報量 (bit) |
平均符号長 (bit) |
| 1 |
\(4\times 1024\) |
4 |
| 2 |
\(4\times 512\) |
2 |
| 4 |
\(4\times 256\) |
1 |
| 8 |
\(4\times 128\) |
0.5 |
のようになります。このように同じ色 (シンボル) が長く続くほど平均符号長が小さく、効率が良くなります。
※ 準備 : 学籍番号を入れて「入力」をクリック (タップ) してください。
白のピクセルと黒のピクセルが交互に
個ずつ並ぶ 32×32ピクセルの画像について、表1の固定長ランレングス符号で符号化した場合の平均符号長を求めてください。
ただし、結果は四捨五入して小数第2位までにしてください。
課題1解説
動画の解説を参照
前項では特定の画像について平均符号長を求めましたが、それらはあくまで限定された対象についてのものでした。
シンボルの並びが発生する確率が分かっていれば、情報源事象系をもとにして一般的な意味での平均符号長を計算できます。
まず、「B」「BB」「BBB」...「BBBBBBBB」、「W」「WW」「WWW」...「WWWWWWWW」の並びが起こることを事象として扱って、16個の事象からなる事象系を作ります ((1)式, 表2)。
|
\(
X=\begin{bmatrix}
x_{b1} & x_{b2} & \cdots & x_{b8} & x_{w1} & x_{w2} & \cdots & x_{w8}\\
p_{b1} & p_{b2} & \cdots & p_{b8} & p_{w1} & p_{w2} & \cdots & p_{w8}
\end{bmatrix}
\cdots (1)
\)
|
表2
シンボルの
並び |
事象 |
発生確率 |
シンボルの
並びの長さ |
| B |
\(x_{b1}\) |
\(p_{b1}\) |
\(l_{b1}(=1)\) |
| BB |
\(x_{b2}\) |
\(p_{b2}\) |
\(l_{b2}(=2)\) |
| BBB |
\(x_{b3}\) |
\(p_{b3}\) |
\(l_{b3}(=3)\) |
| BBBB |
\(x_{b4}\) |
\(p_{b4}\) |
\(l_{b4}(=4)\) |
| BBBBB |
\(x_{b5}\) |
\(p_{b5}\) |
\(l_{b5}(=5)\) |
| BBBBBB |
\(x_{b6}\) |
\(p_{b6}\) |
\(l_{b6}(=6)\) |
| BBBBBBB |
\(x_{b7}\) |
\(p_{b7}\) |
\(l_{b7}(=7)\) |
| BBBBBBBB |
\(x_{b8}\) |
\(p_{b8}\) |
\(l_{b8}(=8)\) |
| W |
\(x_{w1}\) |
\(p_{w1}\) |
\(l_{w1}(=1)\) |
| WW |
\(x_{w2}\) |
\(p_{w2}\) |
\(l_{w2}(=2)\) |
| WWW |
\(x_{w3}\) |
\(p_{w3}\) |
\(l_{w3}(=3)\) |
| WWWW |
\(x_{w4}\) |
\(p_{w4}\) |
\(l_{w4}(=4)\) |
| WWWWW |
\(x_{w5}\) |
\(p_{w5}\) |
\(l_{w5}(=5)\) |
| WWWWWW |
\(x_{w6}\) |
\(p_{w6}\) |
\(l_{w6}(=6)\) |
| WWWWWWW |
\(x_{w7}\) |
\(p_{w7}\) |
\(l_{w7}(=7)\) |
| WWWWWWWW |
\(x_{w8}\) |
\(p_{w8}\) |
\(l_{w8}(=8)\) |
シンボルの並びの平均の長さ (その並びにあるシンボルの個数の平均) \(L_s\) は以下の式で求められます。
\(L_s=\displaystyle \sum_i p_il_i\)
\(=p_{b1}l_{b1}+p_{b2}l_{b2}+\cdots+p_{b8}l_{b8}\)
\(+p_{w1}l_{w1}+p_{w2}l_{w1}+\cdots+p_{w8}l_{w8}\)
\(=p_{b1}+2p_{b2}+\cdots+8p_{b8}\)
\(+p_{w1}+2p_{w2}+\cdots+8p_{w8}\)
一方、どの並びに対する符号語の符号長も4bitなので、「シンボルの並び」に対応する符号語の平均の長さ (平均符号長ではないことに注意) \(\bar{L}\) は、
\(\bar{L}=4\) (bit)
なので、平均符号長、つまり「シンボル1つあたりに平均して割り当たる符号語の長さ」は以下のようになります。
\(L=\)
\(\Large{\frac{\bar{L}}{L_s}}\)
\(=\Large{\frac{4}{L_s}}\)(bit)
表2の方法で符号化する場合、 \(p_{b1}\)～\(p_{b7}\) と \(p_{w1}\)～\(p_{w7}\) がすべて
であり、\(p_{b8}\), \(p_{w8}\)
がどちらも
の場合の平均符号長 \(L\) を求めてください。ただし、結果は四捨五入して小数第2位までにしてください。
課題2解説
動画の解説を参照
表2の符号では16通りのシンボルの並びに対してすべて4bitの符号語を割り当てましたが、それぞれの並びが出現する確率が異なる場合は、
ここで割り当てる符号をハフマン符号にすればもっと効率を上げられます。
\(p_{b1}\)～\(p_{b7}\) と \(p_{w1}\)～\(p_{w7}\) がすべて 0.01 であり、\(p_{b8}\), \(p_{w8}\)
がどちらも 0.43 の場合は、ハフマン符号のルールに従って符号の木を作ると下図のようになります。
この場合、シンボルの並びに割り当てられる符号語の長さは1～6bitですが、出現頻度の高いW8個、B8個の並びには1bit、2bitの短い符号語が割り当てられるので、
平均の長さ \(\bar{L}\) は4bitよりも小さくなります。
その結果、\(\bar{L}/L_s\) で求められる平均符号長 \(L\) も、表1の固定長ランレングス符号より短くなります。
概要の符号の木を元にしてハフマン符号の表を完成させ、その場合の平均符号長を求めてください。
この問題は全員共通です。確率の値は課題2のものではなく、概要のものを使って計算してください。
| シンボルの並び |
符号語 |
| B |
|
| BB |
|
| BBB |
|
| BBBB |
|
| BBBBB |
|
| BBBBBB |
|
| BBBBBBB |
|
| BBBBBBBB |
|
| W |
|
| WW |
|
| WWW |
|
| WWWW |
|
| WWWWW |
|
| WWWWWW |
|
| WWWWWWW |
|
| WWWWWWWW |
|
課題3解説