ランレングス符号化（RLE）の基本原理と代表的な変種・実装ポイント、現実世界での活用事例

2025年11月22日 最終更新日時 : 2025年11月22日 エバープレイ編集部

ランレングス符号化（Run-Length Encoding: RLE）とは

ランレングス符号化（RLE）は、同じ値（シンボル）が連続して現れる「連長」をその回数と値の組で表現する、非常に単純で古典的な可逆圧縮法です。データ中に同一のバイトやビット列が長く続く場合に有効で、白黒の1ビット画像やパレット画像、テキストの繰り返しなどに適しています。アルゴリズムの単純さからハードウェア実装や前処理・後処理として広く用いられてきました。

基本的な仕組み（概念と例）

最も単純なRLEは「連続するシンボルの長さ（run length）とそのシンボル」を並べて記録します。例えば文字列：

  • AAAAABBBCCDAA

をRLEで表すと、（5,A）（3,B）（2,C）（1,D）（2,A）というように表現できます。人間可読な表記なら「5A3B2C1D2A」となります。

画像やバイナリでは、通常「長さ」と「値」をバイト単位で格納します。例えば、連長を1バイトで表現する実装なら同じバイトが256回以上続く場合は複数の符号化ブロックに分けます。また、連長とデータの位置づけ（長さが先か値が先か）や、連長バイトの値に意味を持たせる（符号化モードとリテラルモードを分ける）など実装バリエーションがあります。

代表的な変種・規格

  • 単純RLE — 長さ・値のペアを素直に保存する最も基本的な形。
  • PackBits — Appleが導入した形式で、長さバイトの符号（符号付き）でリピートとリテラルを切り替える。TIFFファイルの一部実装でも利用されてきました。
  • BMPのRLE（RLE4/RLE8） — Windows BMPフォーマットには、パレットカラー向けに4ビットまたは8ビット単位のRLEが公式にサポートされています。
  • PDFのRunLengthDecode — PDF仕様でサポートされる単純なランレングスデコーダフィルタがあります（連長符号のエンコード規則が規格化されています）。
  • FAX（CCITT Group 3/4） — モノクロ画像の圧縮に特化したランレングス＋ハフマン符号化の組合せを用いる方式（画質を保ちつつ高効率な符号化を実現）。

具体例（画像での利用）

モノクロ（1ビット）画像では、各行を左から右へ走査して「白の連長、黒の連長、白の連長…」の系列として保存できます。例えば白が30ピクセル、黒が10ピクセルの列が続く場合、「30,10,...」という値列になるため、元のビットをそのまま並べるより遥かに小さくなります。医用画像のマスクやセグメンテーション情報、OCR前処理、FAXデータの送受信などで多用されています。

長所と短所

  • 長所
    • 実装が非常に簡単で高速（線形時間 O(n)）かつ低いメモリオーバーヘッド。
    • 連続したデータ（低エントロピー）に対して非常に高い圧縮率を示す。
    • 可逆圧縮でデータを完全に復元可能。
    • ハードウェアに向く単純な逐次処理が可能。
  • 短所
    • データに繰り返しパターンが無い高エントロピー領域では圧縮効果が低く、場合によってはデータサイズが増えることがある。
    • 適切なエンコーディング仕様（エスケープや終了マーカー、最大長の扱い）を決めないと実用に難がある。
    • 単体ではテキストや自然画像のような複雑な冗長性を捉えきれない場合が多い。

実装上の注意点（現場でよく直面する問題）

  • 連長（カウント）フィールドのビット幅を決める（例：1バイト＝最大255まで、2バイトでより長いランを扱う）。上限を超えるランは分割して複数ブロックにする必要がある。
  • リテラル（連続しない値の並び）とリピート（単一値の繰り返し）をどう区別するか。PackBitsのように符号付き長さバイトで切り替える方式が一般的。
  • 値として使うバイトが「制御バイト（マーカー）」と衝突する場合のエスケープ処理。マーカーバイトを値として扱えるようにエスケープを定義するか、別のフォーマットを採る。
  • 圧縮後のサイズが入力より大きくなる境界条件への対策。多くの実装は「圧縮しても大きくなる場合は無圧縮で保存する」オプションを持つ。
  • マルチチャネル（RGB）画像に対しては、各チャンネル別々にRLEをかけるか、ピクセル単位で値として扱うかで結果が変わる。パレット画像（インデックスカラー）に対しては特に有効。

パフォーマンスと組合せ戦略

RLE自体の計算量は線形で非常に軽量です。実務ではRLEを他の圧縮法と組み合わせて使うことが多いです。例えば、まずRLEで長い連続を圧縮してから、残ったデータに対してLZ77/DEFLATEやハフマン符号化を適用すると効果的です（実際、一部の複合圧縮形式では同様の前処理を行います）。ただし、RLEを無差別に適用するとデータ統計が変わり、後段のアルゴリズムの劣化を招く可能性もあるため適用条件を選ぶことが重要です。

現実世界での利用例

  • FAX通信（CCITT Group 3/4）：白黒の走査データをランレングスとして扱い、さらにハフマン符号で効率化。
  • TIFFやBMPの一部実装：パレット画像向けにRLE圧縮が公式サポートされていることがある。
  • PDFのRunLengthDecodeフィルタ：単純なRLEを扱うためのフィルタが存在する。
  • 画像処理ライブラリや機械学習のマスク表現：COCOや一部コンペでRLE形式のマスクが使われる（区間を圧縮してメモリ効率を上げる）。
  • ゲームや古典的なグラフィックスフォーマット（例：PCXなど）での利用。

いつ使うべきか — 推奨事項

  • 単色やパレット画像、二値化したマスクデータなど、連続値が存在するデータには第一候補として検討する。
  • ランの長さが短く不規則なデータでは効果が期待できないため、事前にサンプリングしてRLEが有効か確認する。
  • 他の圧縮との組合せを検討する。特に画像のように空間的冗長性があるデータに対してはRLE＋LZ/Huffmanの組合せが強力。
  • フォーマットの互換性や仕様に従う（BMP/RLE、PDFのRunLengthDecode、TIFFのPackBits など）。

まとめ

ランレングス符号化は非常に単純かつ高速で、特定用途（連続する値が多いデータ）に対しては非常に優れた可逆圧縮手法です。一方で高エントロピーなデータでは逆効果になり得るため、適用するデータの性質を理解した上で利用することが重要です。現代の複合圧縮パイプラインでは、RLEは前処理・後処理として有効に活用されることが多く、フォーマット互換や実装上の細かな仕様（最大連長、エスケープ、マーカー等）に注意して設計する必要があります。

参考文献

カテゴリー
IT
前の記事
ゴーストのアナログ盤徹底ガイド：おすすめレコードとプレスの選び方、コレクター必携New!!
2025年11月22日
次の記事
ゴーストをレコードで聴くべき理由とおすすめ盤ガイド—Opus Eponymous から Impera までのコレクター視点解説New!!
2025年11月22日