|
連長圧縮連長圧縮（れんちょうあっしゅく）は、データ圧縮アルゴリズムの一つで、可逆圧縮に分類される。ランレングス圧縮、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バイトで済むようになる。
PackBitsところが、この方法では逆に連続するデータの圧縮率が低下する場合がある。次の例では、全体としては圧縮率が上がっているが、前半の連続するデータの部分の圧縮率は下がっている。
そこで、このような圧縮率の低下を回避するため、連続しないデータが見つかった場合は、連続するデータが現れるまでの長さを記録していくことにする。先の例に適用すると、次のようになる。
- が付いた（負の）長さデータは連続しないデータの長さを表し、この例では「"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とは違い、フラグビット[1]が必要ないため、Switched Run Length Encodingでは256程度までの長さを表現できる。 脚注関連項目 |