連長圧縮について

圧縮の基本ともいえる連長圧縮についておさらい。

連長圧縮とは

Wikipediaより引用。

連長圧縮（れんちょうあっしゅく）は、データ圧縮アルゴリズムの一つで、可逆圧縮に分類される。ランレングス圧縮、RLE (Run Length Encoding) とも呼ばれる。

アルゴリズム

連長圧縮では、連続するデータをデータ1つとそのサイズに置き換える。

例

AAABBCCCC ⇒ A3B2C4

上記の例の場合、データのサイズが9から6に減少しているため、約66%(2/3)圧縮できていることになる。

欠点

例えばこの法則を次のような例に適用するとどうなるだろうか。

ABCDEF

この場合、「サイズ1のデータが6個ある」と解釈されるため、A1B1C1D1E1F1となる。
しかしこれでは圧縮の意味を成さない。この場合だと、サイズは元のデータの2倍に膨れ上がってしまっている。

解決法

PackBitsという手法を利用する。PackBitsでは、連続しないデータが見つかった場合、連続するデータが表れるまでの長さを記録する。

• 圧縮前：AAABBCCCCDEFG
• 圧縮後：3A2B4C-4DEFG

正数で連続するデータの長さを、負数で連続しないデータの長さを表すことによって、連続しているデータかどうかを区別する。これで連長圧縮が持つ問題を回避することができる。