連長圧縮講座

Revised : 2006/05/03
Since : 2006/05/01

連長圧縮(Run Length Encoding)

元のデータを記号と長さで表現する方法である。

連長圧縮の欠点は、データが連続していないと、符号化後のデータが元のデータより膨張することである。
これを防ぐ方法は幾つかあるが、一番理解しやすいのは連長圧縮開始の記号を挿入する方法であろう。
例えば、連長圧縮開始の記号をZとすると・・・

復号はZが出現したら、その次の記号を出力し、さらに続く回数分出力する。
Zを出力すると、圧縮率が悪くなる場合は、Zを出力せずにそのまま符号化すれば良い。
Zを符号化する場合は注意が必要である。上の表を参考に・・・
ページの上部へ

簡単な実装方法

連長圧縮開始の記号を用いずに簡単に連長圧縮を実装する方法がある。
それは、同じ記号が規定数連続出現した場合には、連長圧縮する方法である。
復号は、同じ記号が規定数連続出現した時、その後に続く回数分出力する。

改良版として記号をグループ分けして、グループ毎に規定数を決める方法がある。
これはα符号のように、小さい数字ほど少ないbit数で表す場合等に有効である。

PackBits

上記方法では記号が連続する場合、圧縮率が低下してしまう。
これを改善し、連続しない場合は、連続するまでの長さを記録する方法がPackBitsである。
この長さは０となることはありえないため、実際の長さ－１で表す。
また、不連続の場合の長さを正の数で表し、連続長の場合は負の数で表す。
この方法は、TIFFやPICT等に使われている。
ページの上部へ

Switched Run Length Encoding

しかし、PackBitsでは、長さの最大値が128バイト程度に限られてしまう。
これを改善し、不連続と連続を交互に切り替える方法がSwitched Run Length Encodingである。
この方法では、長さを正と負に分ける必要がなく最大値を256バイト程度まで拡大できる。