連長圧縮(RLE)

ランレングス符号化は、同じ記号が続く極大の並び（ラン）を、ひとつの（記号, 個数）の組に置き換えます。読み取り欄に届くのはテキストではなく二つの数、N 文字と R ラン です。ページ上のそれ以外の数値は、すべてこの二つの商にすぎません。

各記号の意味

N

入力される文字数。入力した文字列の長さ、それだけです。

R

ランの数、つまり同じ記号が繰り返される極大ブロックの数。隣り合う二文字が異なるたびに R は 1 増えます。数えているのは境界であって、文字ではありません。

L̄

N/R、平均ラン長。結果を決めるのはこの量だけです。

ratio

N/2R、すなわち L̄/2。1 を超えれば出力は入力より小さくなります。

公式の導き方

1. 文字ではなくランを数えます。0010111100001111 では隣同士が 5 か所で異なるので、ランは 6 本、行には R=6 と出ます。
2. 符号化後の大きさは 2R、それ以外の要素はありません。ランが何でできているかは計算に一度も入らず、6 本のランは画素でも文字でも数字でも 12 単位です。
3. 割り算します。ratio = N/2R = L̄/2。損益分岐点は L̄ = 2 にあり、しかもちょうど到達できます。AABB と入力すれば、棒グラフは入力 4 バイト、出力 4 バイトを示します。
4. 上下の向きは対称ではありません。上には限りがなく、100 万文字のランひとつは組ひとつになります。下の床は 0.50× で、これより下はありません。入力にできる最悪のことは、各文字にそれぞれのランを与えることだからです。

表示の読み方

四つの見本はどれもちょうど 16 文字で、だからこそまとめて読む価値があります。画像の走査線はラン 3 本で 6 バイト。典型的なランは 4 本で 8。ビットマスクは 6 本で 12。最悪の場合は 16 本で 32。入力の長さは同じなのに、出力は 6 バイトから 32 バイトまで——5 倍の開きが、ひとえに R だけで決まります。次に hello world と入力してみてください。11 文字、10 ラン、出力 20 バイト。ふつうの文章はこの範囲の下端に落ち着きます。ランレングス符号化が単体の圧縮器ではなく圧縮器の部品である理由は、まさにそこにあります。

前提

組がちょうど 2 単位であること、記号と個数の幅が同じであること、そして個数がいくらでも大きくなれること。実際の符号化器は個数に固定幅——1 バイト、つまり 255——を与えるため、それより長いランは複数の組に分割せざるをえず、損益分岐点は 2 をわずかに上回ります。幅が同じという前提は、この方式が最も得意とするデータでこそ最も強く崩れます。1 ビットのファクス画像では、記号は 1 ビットですが、個数はそうではありません。

成り立たない場合

0.50× の床は、工夫で取り除ける欠陥ではありません。可逆符号化は元に戻せなければならず、異なる入力は異なる出力に対応する必要があります。そして写す先となる短い文字列は、長い文字列より数が少ない。したがって、ひとつでも入力を短くする方式は、必ずどこかの入力を長くします。これは数え上げの事実であって、ランレングス符号化の性質ではありません。上の三つ目の洞察にある PackBits は最悪の場合を 128 バイトにつき制御バイト 1 つ——1% 未満——まで下げますが、誰もそれ以上には行けません。床はいくらでも下げられる一方、決して到達できないからです。この方式はその費用を外側に、動くのを目で追える読み取り欄に置いているだけなのです。