連長圧縮

連長圧縮：データ圧縮アルゴリズム

連長圧縮（ランレングス圧縮、RLE：Run Length Encoding）は、データ圧縮の手法の一つです。連続して同じデータが繰り返される場合に有効な可逆圧縮アルゴリズムであり、元のデータと完全に同じデータを復元できます。

連長圧縮の原理

連長圧縮は、連続する同じデータとその連続数を記録することで圧縮を行います。例えば、「AAAAABBBBBBBAAA」というデータは、「A5B9A3」のように表現できます。これは、Aが5回、Bが9回、Aが3回連続していることを示しています。連続するデータの種類が限られている場合、さらに圧縮率を高めることができます。例えば、データがAとBのみで構成され、常にAから始まるというルールを設ければ、「593」だけで表現できます。Bから始まる場合は、最初のAの連続数を0とすれば良いでしょう。

この特性から、白と黒の2値データで構成されるファクシミリ画像などの圧縮に適しています。

連長圧縮の欠点と解決策

連長圧縮の最大の欠点は、連続したデータが少ない場合、圧縮後のデータサイズが元のデータより大きくなってしまうことです。「ABCDEFG」のようなデータは、「A1B1C1D1E1F1G1」となり、逆にデータサイズが増加します。

この問題を解決するため、いくつかの改良手法が考案されています。単純な方法としては、同じデータが一定数以上連続する場合のみ連長圧縮を行う方法です。これにより、連続しないデータによる圧縮率の低下を防ぎます。

PackBits

PackBitsは、連続するデータと連続しないデータの両方を効率的に扱うためのアルゴリズムです。連続するデータの長さを正の数で、連続しないデータの長さを負の数で表現します。例えば、「AAAABBCFFFFFGH」をPackBitsで符号化すると、「4A2B6F2GH」のようになります。負の数は連続しないデータの長さを、正の数は連続するデータの長さを表します。PackBitsはTIFFやPICTといった画像フォーマットで使用されています。

Switched Run Length Encoding

PackBitsでは、データ長を表す符号の正負によって連続データか非連続データかを判別するため、表現できるデータ長に制限があります。Switched Run Length Encodingは、この制限を克服するためのアルゴリズムです。連続データと非連続データを交互に処理することで、より長いデータ長を表現できます。例えば、「ABCCCCCCDEFGGGGGG」というデータの場合、まず連続しないデータとして「A」「B」「C」「D」「E」「F」を扱います。その後ろに、連続する「C」の数「6」と、連続する「G」の数「6」を記録します。復号時は、この記録に従ってデータが復元されます。この方法により、PackBitsよりも多くのデータ長を表現でき、より効率的な圧縮が可能になります。

まとめ

連長圧縮はシンプルながら効果的なデータ圧縮アルゴリズムですが、データの特性によっては圧縮率が低下する可能性があります。PackBitsやSwitched Run Length Encodingなどの改良手法は、これらの欠点を補う役割を果たし、様々なアプリケーションで利用されています。特に、画像データや、連続するデータが多いデータの圧縮において有用な手法です。これらの手法は、データの特性に合わせて適切に選択することが重要です。

関連項目

差分圧縮
BMP (一部のカラーパレット形式において連長圧縮が利用可能)

もう一度検索