第7回 ランレングス符号

初めに必ず連絡事項を確認してください。

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

解説動画

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

モノクロの画像は白と黒のどちらかのピクセルだけで構成されるので、白と黒のピクセルをシンボル W, B と考えれば、この32x32ピクセルの画像はこの2文字からなる「文」として扱うことができる。
「一番上の行を左から右に順に見て、次はその下の行をまた左から右に...」という読み方をすれば、これは長さ \(32\times32=1024\) の文になる。
図1
図1のような画像では白のピクセルが黒より多く、シンボル W が発生する確率は B が発生する確率よりも高い。
しかし、シンボルが2種類しかないので、ハフマン符号は結局
シンボル 符号語
W 0
B 1
となり、画像の情報を送るにはピクセル数と同じ1024ビットのデータが必要になってしまう。

ランレングス符号

概要

解説動画

上のケースで「Bがいくつ続いたか」「Wがいくつ続いたか」に応じて、シンボルの並びに対して符号語を作ってみる。
符号語の先頭には「何が」、それに続くものとして「続いた数-1」を入れることにして、続いた数を1~8の範囲で許容することにすると、種類用に1ビット、カウント用に3ビット使って以下のような「シンボルの並びに対する等長符号」ができる。
このような符号を固定長ランレングス符号という。

表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
となり、40ビットのデータで送ることができる (白黒でなくても、色の数がそれほど多くない場合であれば符号語の先頭に割り当てるビット数を色数に応じて増やせば同様のことができる)。

この方法の効率は、BとWの単独の出現率ではなく、その切り替わりがどれほど頻繁に起こるかに依存する。
図1のようにBとWの変化があまり起こらない場合であればこの方法で効率は上がるが、
図2
のようなケースでは「Bが1個」「Wが1個」のように1つのピクセルあたり4ビットの符号語が割り当てられ、データ量は4倍に増えてしまう。
このときはシンボル「B」「W」に対して符号語の長さはいずれも4ビットなので、平均符号長も4ビットになる。

もう少しだけシンボルが連続する
図3
のようなケースでは「Bが2個」「Wが2個」の並びに対して4ビットの符号語が割り当てられる。このときのデータ量は、シンボルの並びに対しては4ビット、1つのシンボルに対しては2ビットとなる。
つまり、このときの平均符号長は2ビットになる。

課題1

以下に示す図4のような画像を表1の方法でランレングス符号にしたときの平均符号長を求めよ。
図4
課題1ヒント

「Bが4個」「Wが4個」の並びに対して4ビットの符号語が割り当てられる。

課題2

以下に示す図5のような画像を表1の方法でランレングス符号にしたときの平均符号長を求めよ。ただし、結果は四捨五入して小数第2位までにすること。
図5
課題2ヒント

「Bが5個」「Wが5個」の並びが全部で 1020/5=204組あり、それぞれに4ビットの符号語、最後の「BBBB」に対しても4ビットの符号語が割り当てられる。
それらを加えたのが全データ量で、それをシンボルの数で割れば平均符号長が求められる。

ランレングス符号の平均符号長

概要

解説動画

固定長ランレングス符号の平均符号長は以下のようにして求める。
まず、「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\) は

\( \begin{eqnarray} L_s&&=\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} \end{eqnarray} \)

のように表わせる。

一方、どの並びに対する符号語も4ビットなので、「シンボルの並び」に対応する符号語の平均の長さ \(\bar{L}\) は、\(\bar{L}=4\) (ビット) となる。

よって、平均符号長、つまり「シンボル1つあたりに平均して割り当たる符号語の長さ」は以下のようになる。

\( \begin{eqnarray} L&&=\frac{\bar{L}}{L_s} (ビット) \end{eqnarray} \)

課題3

表1の方法で \(p_{b1}\)~\(p_{b7}\) と \(p_{w1}\)~\(p_{w7}\) がすべて\(0.01\)、\(p_{b8}=p_{w8}=0.43\) のときの平均符号長 \(L\) を求めよ。ただし、結果は四捨五入して小数第2位までにすること。
課題3ヒント

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

概要

解説動画

表1の符号では16通りのシンボルの並びに対してすべて4ビットの符号語を割り当てたが、それぞれの並びが出現する確率が異なる場合はここで割り当てる符号をハフマン符号にすればもっと効率を上げられる。
課題3で与えられた発生確率の場合は、ハフマン符号のルールに従って符号の木を作ると下図のようになる。


この場合、シンボルの並びに割り当てられる符号語の長さは1~6ビットであるが、出現頻度の高いW8個、B8個の並びには1ビット、2ビットの短い符号語が割り当てられるため、平均の長さ \(\bar{L}\) は4よりも小さくなる。
その結果、\(\bar{L}/L_s\) で求められる平均符号長 \(L\) も、表1の固定長ランレングス符号より短くなる。

課題4

概要の符号の木を元にしてハフマン符号の表を完成させ、その場合の平均符号長を求めよ。
課題4ヒント
シンボルの並び 符号語
B
BB
BBB
BBBB
BBBBB
BBBBBB
BBBBBBB
BBBBBBBB
W
WW
WWW
WWWW
WWWWW
WWWWWW
WWWWWWW
WWWWWWWW

提出

ノート・紙に解いた課題を撮影したものを以下のフォームから送信してください。
課題提出用フォーム
※ 締切は10/26(土) 正午です。提出によって出席・点数がつきます。