連長圧縮講座

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


Home  圧縮 ∥ 連長圧縮 | 簡単実装 | PackBits | Switched Run Length Encoding

連長圧縮(Run Length Encoding)

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

元のデータ 圧縮後のデータ 圧縮率
AAAAAAAA A7 25%
AA A1 100%
A A0 200%

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

元のデータ 圧縮後のデータ 圧縮率
ABCAAAAAAAAA ABCZA8 50%
AABBZZ ZA1ZB1ZZ1 150%
AABBZ AABBZZ0 140%

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

簡単な実装方法

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

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

元のデータ 圧縮後のデータ 規定数
ABCAAAABBBBCCCC A0B0C0A3B3C3 1
ABCAAAABBBBCCCC ABCAAA1BBB1CCC1 3
ABCAAAABBBBCCCC ABCAAA1BB2C3 A3,B2,C1
ページの上部へ

PackBits

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

Switched Run Length Encoding

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

元のデータ 圧縮後のデータ 方法
ABCAAAABBBBCCCC 2ABC-3A-3B-3C PackBits
ABCAAAABBBBCCCC 3ABCA30B30C3 Switched Run Length
AAAABCCCCABCAAA 0A31BC33ABCA2 Switched Run Length
ページの上部へ
容量300MB、月額125円、高性能なサーバが日本最大級のバックボーンに直結。
さくらのレンタルサーバ
ロリポップのドメインが65種類 → 85種類に!!
きっとお好みのドメインが見つかるはず!
アフィリエイトならリンクシェア