連長圧縮
連長圧縮（れんちょうあっしゅく）は、データ圧縮アルゴリズムの一つで、可逆圧縮に分類される。ランレングス圧縮、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倍あるということになる。また、伸長時にメモリの確保を容易にするために元のデータのサイズを記録する場合はさらに膨らんでしまうことになる。
それを防ぐ方法はいくつかあるが、その中でも最も単純なのが、ある一定数だけ同じデータが繰り返した場合にだけ連長圧縮を施すという方法である。次の例では、8バイト（8文字）必要だったものが6バイトで済むようになる。
| 元のデータ | ABCDDDD | = | A | B | C | DDDD |
| 通常の符号化方法 | A1B1C1D4 | A1 | B1 | C1 | D4 | |
| 対策済みの符号化 | ABCDD2 | A | B | C | DD2 |
PackBits
[編集]ところが、この方法では逆に連続するデータの圧縮率が低下する場合がある。次の例では、全体としては圧縮率が上がっているが、前半の連続するデータの部分の圧縮率は下がっている。
| 元のデータ | AAAABBCCCCCCDEFG | = | AAAA | BB | CCCCCC | DEFG |
| 通常の符号化方法 | A4B2C6D1E1F1G1 | A4 | B2 | C6 | D1E1F1G1 | |
| 上記の符号化方法 | AA2BB1CC3DEFG | AA2 | BB1 | CC3 | DEFG |
そこで、このような圧縮率の低下を回避するため、連続しないデータが見つかった場合は、連続するデータが現れるまでの長さを記録していくことにする。先の例に適用すると、次のようになる。
| 元のデータ | AAAABBCCCCCCDEFG | = | AAAA | BB | CCCCCC | DEFG |
| 符号化したデータ | 4A2B6C-4DEFG | 4A | 2B | 6C | -4DEFG |
- が付いた（負の）長さデータは連続しないデータの長さを表し、この例では「"A" が4、"B" が2、"C" が6ずつ続き、圧縮できない "DEFG" の4文字がある」と符号化されたことになる。この方法をPackBitsと言い、TIFFやPICTなどで使われている。
Switched Run Length Encoding
[編集]しかし、PackBitsでは、データの長さを表す符号が連続するデータの長さのものであるか連続しないデータの長さのものであるかをその正負によって判別しているので、表現できるデータの長さが半分までになる。データの長さには通常1バイトを割り当てるので、PackBitsで表現できるデータの長さは128までとなる。通常はそこまで連続することはなかなかないが、色数の少ない画像などでは十分に考え得る。この対策として、コードの変わり目で連続データとして扱うか非連続データとして扱うかを交互に切り替えていくSwitched Run Length Encodingがある。
データ「A B C D E E E E F F F F F F F」を例として、圧縮の方法を解説する。
- まずは非連続データとして扱い、PackBits同様に連続したデータが現れるまでの長さを記録し、その後ろに非連続データをそのまま出力する
A B C D E E E E F F F F F F F→5 A B C D E - 連続したデータに出会ったら、次に連続しないデータに出会うまでの長さを記録する
A B C D E E E E F F F F F F F→5 A B C D E 3 - 再度、連続したデータが現れるまでの長さを記録し、その後ろに非連続データをそのまま出力する
A B C D E E E E F F F F F F F→5 A B C D E 3 1 F - 2と3をデータの末尾まで交互に繰り返していく
A B C D E E E E F F F F F F F→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とは違い、フラグビット[1]が必要ないため、Switched Run Length Encodingでは256程度までの長さを表現できる。