ランレングス圧縮【連長圧縮】 RLE / Run Length Encoding

概要

ランレングス圧縮（連長圧縮）とは、最も基本的な圧縮アルゴリズムの一つで、連続して現れる符号を、繰り返しの回数を表す値に置き換える方式。圧縮によって内容を損なわない可逆圧縮を行う。

例えば、「AAAABBBBCCCC」という文字列を圧縮する場合、「A」が4回、「B」が4回、「C」が4回それぞれ連続しているため、各文字とその繰り返し回数を組み合わせて「4A4B4C」のように表すことができる。

展開する場合は「4A」を「AAAA」のように戻していくことで元の文字列が得られる。この例では元のデータの半分のデータ長に圧縮することができた。

この単純な方法では同じ符号が連続する箇所が少ないか存在しない場合、圧縮どころか逆にデータ長が大きく伸びてしまう場合がある。例えば、「ABCABC」は「1A1B1C1A1B1C」となってしまい、元の倍の長さになってしまう。

こうした事態を防ぐための手法がいくつか考案されている。例えば、繰り返し回数を表す数字が負数の場合は、その絶対値の長さだけ元のデータがそのまま記載されている区間が出現するという規則を追加する方式がよく知られる（PackBits方式）。

例えば、「AAAABCDEBBBB」は、単純な符号化では「4A1B1C1 D1E4B」と12文字で表されるが、PackBits方式では中間の繰り返しのない4文字の先頭に「-4」（説明のため負号を付けて2文字で表しているが実際のデータ上は1文字分）を付加した「4A-4BCDE4B」となり、9文字で表すことができる。

ランレングス圧縮は余白の多い白黒2値画像のように、符号の種類が少なく繰り返し箇所が多い性質のデータで効率よく圧縮でき、ファクシミリの伝送符号や一部のビットマップ画像形式（BMP形式やPICT形式など）などに採用例がある。

(2020.3.18更新)