情報理論第13回　ランレングス符号

例
モノクロの画像は白と黒のどちらかのピクセルだけで構成されるので、白と黒のピクセルをシンボル

W, B

と考えれば、この画像はこの2文字からなる「文」として扱うことができる。

図のような画像では白のピクセルが黒よりずっと多く、シンボル

W

が発生する確率はもう一方よりもずっと高い。
しかし、シンボルが2種類しかないので、ハフマン符号は結局

シンボル	符号語
$W$	0
$B$	1

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

固定長ランレングス符号

B

W B

W W B

W W W

W W B

W

B

固定長ランレングス符号

W W W

W W W

W W W

W W W

W W W

W W B

B

W W W

B

W W W

白の割合がもっと多い場合なら、「シンボル」を8種類 (最大7文字)、符号長を3にして

のようにすればさらに効率を上げられる。

B

p

X^{'} = [\begin{matrix} x_{B} & x_{WB} & x_{WWB} & x_{WWW} \\ p & (1 - p) p & {(1-p)}^{2} p & {(1-p)}^{3} \end{matrix}]

W

B

n_{3} = p + 2 (1 - p) p + 3 {(1-p)}^{2} p + 3 {(1-p)}^{3}

n

n_{3} = \frac{p}{1-p} ((1 - p) + 2 {(1-p)}^{2} + 3 {(1-p)}^{3}) + 3 {(1-p)}^{3} = \frac{p}{1-p} \sum_{r = 1}^{3} r {(1-p)}^{r} + 3 {(1-p)}^{3}

\sum_{r = 1}^{N} r x^{r} = \frac{x(1-x^{N})}{{(1-x)}^{2}} - \frac{Nx^{N+1}}{1-x}

x

1 - p

N

n_{3} = \frac{p}{1-p} (\frac{(1-p)(1-{(1-p)}^{3})}{{(1-(1-p))}^{2}} - \frac{3{(1-p)}^{3+1}}{1-(1-p)}) + 3 {(1-p)}^{3} = \frac{1-{(1-p)}^{3}}{p} - 3 {(1-p)}^{3} + 3 {(1-p)}^{3} = \frac{1-{(1-p)}^{3}}{p}

\overline{L}

\overline{L} = 2

n_{3}

L = \frac{\overline{L}}{n_{3}} = \frac{2p}{1-{(1-p)}^{3}}

p = 0.1

p

p

n_{7}

\overline{L} = 3

n_{7}

p = 0.1

p = 0.1

X^{'} = [\begin{matrix} x_{B} & x_{WB} & x_{WWB} & x_{WWW} \\ 0.1 & 0.09 & 0.081 & 0.729 \end{matrix}]

\overline{L} = 0.1 \times 2 + (0.09 + 0.081) \times 3 + 0.729 \times 1 = 1.442

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

L = 1.442 / 2.71 ≒ 0.53

p = 0.1

\overline{L}

小数第三位まで

p = 0.1

L