連長圧縮
連長圧縮（ランレングス圧縮、RLE：Run Length Encoding）は、データ圧縮アルゴリズムの一つで、可逆圧縮に分類される。
符号化の原理
連長圧縮では、ある連続したデータを、そのデータ一つ分と連続した長さで表現することで圧縮している。
例えば、「A A A A A B B B B B B B B B A A A」は「A 5 B 9 A 3」と表せる。これは、Aが5回続き、そのあとにBが9回、そしてAが3回続いていることを表している（連続回数を、元のデータを表す符号の前に記録することもある。その場合、符号化した後は「5 A 9 B 3 A」と表される）。
さらに、データがこの2種類(AとB)だけで、最初にAが来ることにしておけば、「5 9 3」だけで表せる。このルールに従ったときにBが最初に見つかった場合は、最初にAが0回連続していることにすれば良い。例えば、「B B B A A A A A B B B B B A A A」は「0 3 5 5 3」で表せることになる。
こういったことから、白と黒以外にほとんど情報がないモノクロファクシミリでよく使われている。
連長圧縮の欠点とその解決方法
連長圧縮の欠点は、データが連続していないと、符号化後のデータが元のデータより膨らんでしまうという点。例えば、「A B C D A B C A B A B C D E」は「A 1 B 1 C 1 D 1 A 1 B 1 C 1 A 1 B 1 A 1 B 1 C 1 D 1 E 1」となる。この場合の圧縮率は200%、つまり元の2倍に膨らんでしまった。また、伸長時にメモリの確保を容易にするために元のサイズを記録する場合はさらに膨らんでしまうことになる。
それを防ぐ方法はいくつかあるが、その中でも最も単純なのが、ある一定数だけ同じデータが繰り返した場合にだけランレングス圧縮を施すという方法である。例えば、次のデータを圧縮したとする。
元のデータ： A B C D D D D
| 通常の符号化方法 | 対策済みの符号化 |
|---|---|
| A 1 B 1 C 1 D 4 | A B C D D 2 |
この方法で符号化することで、通常の方法では8文字も必要だったものが6文字で済むようになる。
Pack Bits
ところが、この方法では逆に連続するデータの圧縮率が低下してしまう。例えば、次のようなデータを圧縮したとする。
元のデータ： A A A A B B C C C C C C D E F G
| 通常の符号化方法 | 上記の符号化方法 |
|---|---|
| A 4 B 2 C 6 D 1 E 1 F 1 G 1 | A A 2 B B 0 C C 4 D E F G |
このように、場合によっては逆に圧縮率の低下に繋がることもある。そこで、連続しないデータが見つかった場合は、連続するデータが現れるまでの長さを記録していく。たとえば先の「A A A A B B C C C C C C D E F G」という列があったとして、
4 A 2 B 6 C -4 D E F G
と符号化する。- が付いた長さデータは連続しないデータの長さを表し、この例では「"A"が4、"B"が2、"C"が6ずつ続き、圧縮できない"DEFG"の4文字がある」と符号化されたことになる。この方法をPackBitsと言い、TIFFやPICTなどで使われている。
Switched Run Length Encoding
しかし、PackBitsでは、連続するデータの長さを保持出来る量が128バイト程度に限られてしまう。通常はそこまで連続することは、なかなかないが、色数の少ない画像などでは十分に考え得る。その対策としては、コードの変わり目で連続データとして扱うか非連続データとして扱うかを交互に切り替えていくSwitched Run Length Encoding がある。
次のデータを圧縮しながら原理を解説する。
元のデータ：A B C D E E E E F F F F F F F
- まずは非連続データとして扱い、PackBits同様に連続したデータが現れるまでの長さを記録し、その後ろに非連続データをそのまま出力する
5 A B C D E - 連続したデータに出会ったら、次に連続しないデータに出会うまでの長さを記録する
5 A B C D E 3 - 再度、連続したデータが現れるまでの長さを記録し、その後ろに非連続データをそのまま出力する
5 A B C D E 3 1 F - 2と3をデータの末尾まで交互に繰り返していく
5 A B C D E 3 1 F 6
となる。
復号時は以下の手順に従う。
- まずは非連続データとして扱い、最初の1文字を読み込んで長さを求めた後、後ろに続く非連続データをそのまま出力する
5 A B C D E 3 1 F 6 → A B C D E - 復号し終えたら連続データとして扱うように切り替え、1文字だけ読み込んで連続する長さを求めた後、復号した最後の文字をその長さだけ繰り返し出力する。
5 A B C D E 3 1 F 6 → A B C D E E E E - 再度非連続データとして扱い、1文字読み込んで長さを求めた後、続く非連続データをそのまま出力する
5 A B C D E 3 1 F 6 → A B C D E E E E F - 2と3をデータの末尾まで交互に繰り返していく
5 A B C D E 3 1 F 6 → A B C D E E E E F F F F F F F
PackBitsとは違い、フラグビットテンプレート:Refを用意する必要がないため、Switched Run Length Encodingでは256バイト程度までの長さを表現出来る。
- テンプレート:Note フラグビット
- PackBitsでは長さを表す符号の左1ビットで非連続データか連続データかを区別するビット
