連長圧縮
出典: フリー百科事典『ウィキペディア（Wikipedia）』
連長圧縮（ランレングス圧縮、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」と表せる。 これは、Ａが５回続き、そのあとにＢが９回、そしてＡが３回続いていることを表している（連続回数を、元のデータを表す符号の前に記録することもある。その場合、符号化した後は「5 A 9 B 3 A」と表される）。
さらに、データがこの２種類だけで、最初にＡが来ることにしておけば、「5 9 3」だけで表せる。 このルールに従ったときにＢが最初に見つかった場合は、最初にＡが０回連続していることにすれば良い。 例えば、「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%、つまり元の２倍に膨らんでしまった。 さらに、C言語など、動的にメモリを確保出来ない言語でプログラムする場合、メモリの確保を容易にするために元のサイズを記録しておいた方が都合が良いので、さらに大きくなってしまうことになる。
それを防ぐ方法はいくつかあるが、その中でも最も単純なのが、ある一定数だけ同じデータが繰り返した場合にだけランレングス圧縮を施すという方法である。例えば、次のデータを圧縮したとしよう。
元のデータ： A B C D D D D
| 通常の符号化方法 | 対策済みの符号化 |
| A 1 B 1 C 1 D 4 | A B C D D 2 |
この方法で符号化することで、通常の方法では８文字も必要だったものが６文字で済むようになる。
[編集] PackBits
ところが、この方法では逆に連続するデータの圧縮率が低下してしまう。例えば、次のようなデータを圧縮したとしよう。
元のデータ： 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
４. ２と３をデータの末尾まで交互に繰り返していく
- 5 A B C D E 3 1 F 6
となる。
復号時は以下の手順に従う。
１. まずは非連続データとして扱い、最初の１文字を読み込んで長さを求めた後、後ろに続く非連続データをそのまま出力する
- 5 A B C D E 3 1 F 6 → A B C D E
２. 復号し終えたら連続データとして扱うように切り替え、１文字だけ読み込んで連続する長さを求めた後、復号した最後の文字をその長さだけ繰り返し出力する。
- 5 A B C D E 3 1 F 6 → A B C D E E E E
３. 再度非連続データとして扱い、１文字読み込んで長さを求めた後、続く非連続データをそのまま出力する
- 5 A B C D E 3 1 F 6 → A B C D E E E E F
４. ２と３をデータの末尾まで交互に繰り返していく
- 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とは違い、フラグビット※を用意する必要がないため、Switched Run Length Encodingでは256バイト程度までの長さを表現出来る。
※PackBitsでは長さを表す符号の左１ビットで非連続データか連続データかを区別するが、このような用途に使うビットをフラグビットと言う
