第04回 ランレングス符号

単純なハフマン符号の限界

前回見たように、ハフマン符号ではシンボルの出現率が偏っているほど平均符号長が短くなり、効率が良くなる。しかし、これはシンボルが多数ある場合にだけ起きることであり、シンボルが2種類だけの場合はハフマン符号を使っても効率は改善されない。

モノクロの画像は白と黒のどちらかのピクセルだけで構成されるので、白と黒のピクセルをシンボル \(W, B\) と考えれば、この画像はこの2文字からなる「文」として扱うことができる。

図のような画像では白のピクセルが黒よりずっと多く、シンボル \(W\) が発生する確率はもう一方よりもずっと高い。
しかし、シンボルが2種類しかないので、ハフマン符号は結局
シンボル符号語
\(W\)0
\(B\)1

となり、画像の情報を送るにはピクセル数と同じビット数のデータが必要になってしまう。

固定長ランレングス符号

概要

シンボルが2種類しかないときは、それらの組み合わせをシンボルとして扱うことで効率のよい符号化ができる。例えば上のケースで
  • \(B\) が出たら区切る
  • \(W\) が3個続いたら区切る
というルールでブロックを作ると「\(B\)」「\(WB\)」「\(WWB\)」「\(WWW\)」の4種類ができる。これらを「シンボル」として扱い、
「シンボル」符号語
\(B\)00
\(WB\)01
\(WWB\)10
\(WWW\)11
のような等長符号を作ることができる (呼び名が紛らわしいので、この授業では以降 \(WWB\) などは鍵カッコつきで「シンボル」、本来の \(W, B\) のことは単にシンボルと書く)。このような符号を固定長ランレングス符号という。
この符号を使えば、上の例の拡大部分の左上から右の29ピクセル分は
\(WWW\), \(WWW\), \(WWW\), \(WWW\), \(WWW\), \(WWB\), \(B\), \(WWW\), \(B\), \(WWW\)
→ 11 11 11 11 11 10 00 11 00 11
となり、20ビットのデータで送ることができる。


白の割合がもっと多い場合なら、「シンボル」を8種類 (最大7文字)、符号長を3にして
「シンボル」符号語
\(B\)000
\(WB\)001
\(WWB\)010
・・・・・・
\(WWWWWWB\)110
\(WWWWWWW\)111
のようにすればさらに効率を上げられる。

固定長ランレングス符号の平均符号長は以下のようにして求める。
平均符号長は (本来の) シンボル1つあたりに平均して割り当たる符号語の長さだが、固定長ランレングス符号の表は (ブロック化された)「シンボル」に対するものなので、まずは「シンボル」の長さの平均値を求める。
シンボル \(B\) が発生する確率が \(p\) なら、それぞれの「シンボル」が発生する確率は

\( X'= \begin{bmatrix} x_B & x_{WB} & x_{WWB} & x_{WWW} \\ p & (1-p)p & (1-p)^2p & (1-p)^3 \end{bmatrix} \)

となる。そのため、「シンボル」の平均の長さ (\(W, B\) が何個あるか) は

\( n_3=p+2(1-p)p+3(1-p)^2p+3(1-p)^3 \)

となる ( \(n\) の右下の \(3\) は「シンボル」が最長3文字であることをあらわす) 。この第1~3項は次のようにまとめられる。

\( \begin{eqnarray} n_3&=&\frac{p}{1-p}\Big((1-p)+2(1-p)^2+3(1-p)^3\Big)+3(1-p)^3\\ &=&\frac{p}{1-p}\sum^3_{r=1}r(1-p)^r+3(1-p)^3 \end{eqnarray} \)

まとめた項は、数学の公式

\( \begin{eqnarray} \sum^N_{r=1}rx^r=\frac{x(1-x^N)}{(1-x)^2}-\frac{Nx^{N+1}}{1-x}\dots① \end{eqnarray} \)

の左辺で \(x\) を \(1-p\)、\(N\) を \(3\) と置いたものに等しいので、

\( \begin{eqnarray} n_3&=&\frac{p}{1-p}\Bigg(\frac{(1-p)(1-(1-p)^3)}{(1-(1-p))^2}-\frac{3(1-p)^{3+1}}{1-(1-p)}\Bigg)+3(1-p)^3\\ &=&\frac{\cancel{p}}{\cancel{1-p}}\frac{\cancel{(1-p)}(1-(1-p)^3)}{p^\cancel{2}}-\frac{\cancel{p}}{\cancel{1-p}}\frac{3(1-p)^{3+\cancel{1}}}{\cancel{p}}+3(1-p)^3\\ &=&\frac{1-(1-p)^3}{p}-\cancel{3(1-p)^3}+\cancel{3(1-p)^3}\\ &=&\frac{1-(1-p)^3}{p} \end{eqnarray} \)

となる。平均符号長、すなわち(本来の)シンボル1つあたりの符号長は、「「シンボル」1つあたりの符号長」( \(\bar{L}\) と書く。このケースではすべての符号語の長さが2なので \(\bar{L}=2\) ) を「1つの「シンボル」の平均の長さ」(いま求めた \(n_3\) ) で割って

\( \begin{eqnarray} L=\frac{\bar{L}}{n_3}=\frac{2p}{1-(1-p)^3} \end{eqnarray} \)
となる。

課題1

上の例の条件で \(p=0.1\) のときの平均符号長を求めよ。ただし、計算結果は四捨五入して小数第二位までにすること (スマホの電卓機能などを使ってよい)。
  • 上の式の \(p\) に0.1を代入するだけ。

課題2

「シンボル」を8種類、符号語を3ビットに拡張した場合の平均符号長を \(p\) の関数の形で記述せよ。
  • まず「シンボル」の平均の長さ \(n_7\) を求める。
  • 符号語はすべて3ビットなので、\(\bar{L}=3\) を \(n_7\) で割ったものが平均符号長になる。

課題3

課題2の条件で \(p=0.1\) のときの平均符号長の値を求めよ。ただし、計算結果は四捨五入して小数第二位までにすること (スマホの電卓機能などを使ってよい)。

ランレングスハフマン符号

概要

上記のようにしてつくった「シンボル」に、等長符号ではなくハフマン符号を割り当ててやれば、もっと効率のよい符号ができる。例えば \(p=0.1\) なら情報源事象系は \( X'= \begin{bmatrix} x_B & x_{WB} & x_{WWB} & x_{WWW} \\ 0.1 & 0.09 & 0.081 & 0.729 \end{bmatrix} \) となる。これをもとにハフマン符号を作ると、
「シンボル」符号語
\(B\)10
\(WB\)110
\(WWB\)111
\(WWW\)0

のようになる。
「シンボル」一つあたりの符号長の平均は
\( \begin{eqnarray} \bar{L}&=&0.729\times 1+0.1\times2+(0.09+0.081)\times 3\\ &=&1.442 \end{eqnarray} \)

になる。一方、「1つの「シンボル」の平均の長さ」は

\( n_3=\frac{1-(1-p)^3}{p}=2.71 \)

で、平均符号長は

\( \begin{eqnarray} L=\frac{\bar{L}}{n_3}=\frac{1.442}{2.71}\simeq0.53 \end{eqnarray} \)

となる。この値を同じ条件の固定長ランレングス符号の平均符号長 (課題1の答え) と比べるとこちらの方が小さく、もっと効率の良い符号であることがわかる。

課題4

課題2, 3のように拡張した場合には、\(p=0.1\) ではそれぞれの「シンボル」が出現する確率は以下のようになる。このときのランレングスハフマン符号 (「シンボル」に対する符号語の対応表) を求めよ。
「シンボル」確率
\(B\)0.1
\(WB\)0.09
\(WWB\)0.081
\(WWWB\)0.0729
\(WWWWB\)0.06561
\(WWWWWB\)0.059049
\(WWWWWWB\)0.0531441
\(WWWWWWW\)0.4782969
  • ハフマン符号を作るための符号の木も解答用紙に書くこと。
  • 木を作るには、一番下の桁までまじめに計算する必要はない。大小関係がわかるレベルまで計算すれば十分。

課題5

課題4のケースでの「シンボル」一つあたりの符号長の平均 \(\bar{L}\) を求めよ。ただし、計算結果は四捨五入して小数第三位までにすること (スマホの電卓機能などを使ってよい)。

課題6

課題4のケースで \(p=0.1\) のときのの平均符号長 \(L\) を求めよ。ただし、計算結果は四捨五入して小数第二位までにすること (スマホの電卓機能などを使ってよい)。
inserted by FC2 system