玄関＞コンピュータの部屋＞各種解説コーナー＞データ圧縮法概説
目次 第1章 第2章 第3章 第4章 第5章 第6章 第7章

【第2章　連長符号化(Run Length Encoding、RLE)】

2.1 符号化手順

一番単純な圧縮法で、前章で説明しましたように同じ記号がたくさん続く場合にしか圧縮効果がありませんので、主として画像データの圧縮に利用されています。 この手法の実用例としては、MacintoshのPICTファイルでモノクロのビットマップデータを圧縮するのに用いられているPackBitsが有名です。

PackBitsでは次のような規則に基づいて元データを符号化します。

  1. 元データは８ビットの固定長符号であると仮定し、８ビット単位で符号化する。
  2. 「abcd」のように繰り返しのない一連の記号は、１バイト目に(記号数−１)という１バイト整数を、２バイト以後に一連の記号を並べた(記号数＋１)バイトで符号化する。 １バイト目の整数は０から127の範囲、つまり記号数にすると１個から128個とし、一連の記号が129個以上続く場合は２つ以上に分割して符号化する。
    例えば元データが「abcd」の場合、「3abcd」と符号化される。
  3. 「aaaa」のように同じ記号が複数個連続して続く場合は、１バイト目に(−記号の繰り返し数＋１)という負の１バイト整数を、２バイト目に記号そのものを並べた２バイトで符号化する。 １バイト目の整数は-1から-127の範囲、つまり繰り返し数にすると２個から128個とし、同じ記号が129個以上続く場合は２つ以上に分割して符号化する。
    例えば元データが「aaaa」の場合、「-3a」と符号化される。
  4. 2.のようなデータを「リテラル(文字列)グループ」、3.のようなデータを「反復グループ」といい、これらは１バイト目が正の整数か負の整数かによって区別される。 「a」のように記号が１つだけの場合、どちらの方法で符号化しても「0a」となる。

以上の規則に基づく実際の符号化手順は、例えば次のようになります。

  1. 一連の記号をリテラルとして保存するための一時記憶場所を確保し、リテラル数ｍを０にする。 同時に反復グループ用に前記号を保存するための一時記憶場所を確保し、繰り返し数ｎを０にする。
  2. 元データから最初の１記号(８ビット固定長符号)を入力し、入力記号を前記号として記憶し、ｎを１にする。
  3. 元データから次の１記号を入力する。
  4. 入力記号が前記号と異なる場合は、

    もし前記号の繰り返し数ｎが２以上ならば、
    　反復グループとして「-(n-1)<前記号>」を出力。
    あるいは前記号の繰り返し数ｎが２未満ならば、
    　もしリテラル数ｍが128未満ならば、
    　　ｍを１増加して、前記号をリテラルのｍ文字目として保存。
    　あるいはリテラル数ｍが128以上ならば、
    　　リテラルグループとして「(m-1)<リテラル>」を出力。
    　　リテラルをクリアし、リテラル数ｍを０にする。

    入力記号を前記号として記憶し、ｎを１にする。
    3.に戻る。
  5. 入力記号が前記号と同じ場合は、

    もしリテラル数ｍが１以上ならば、
    　リテラルグループとして「(m-1)<リテラル>」を出力。
    　リテラルをクリアし、リテラル数ｍを０にする。 もし前記号の繰り返し数ｎが128未満ならば、
    　繰り返し数ｎを１増加する。
    あるいは前記号の繰り返し数ｎが128以上ならば、
    　反復グループとして「-(n-1)<前記号>」を出力。
    　前記号はそのままで、ｎを１にする。

    3.に戻る。
  6. 元データが終了した場合、

    もし前記号の繰り返し数ｎが１未満(１記号も入力せず)ならば、
    　何もしない。
    あるいは前記号の繰り返し数ｎが１ならば、
    　ｍを１増加して、前記号をリテラルのｍ文字目として保存。
    　リテラルグループとして「(m-1)<リテラル>」を出力。
    あるいは前記号の繰り返し数ｎが２以上ならば、
    　もしリテラル数ｍが１以上ならば、
    　　リテラルグループとして「(m-1)<リテラル>」を出力。
    　反復グループとして「-(n-1)<前記号>」を出力。

2.2 実例

例として、「abbbccccde」というデータを前節の手順に従って符号化してみましょう。

  1. リテラル記憶場所確保、ｍ＝０。 前記号記憶場所確保、ｎ＝０。
  2. １記号目の「ａ」を入力。
    前記号＝ａ、ｎ＝１
  3. 「ｂ」入力。
    入力記号ｂ≠前記号ａ
    　前コードの繰り返し数ｎ＝１＜２
    　　リテラルの繰り返し数ｍ＝０＜128
    　　　ｍ＝１、リテラル＝ａ
    前記号＝ｂ、ｎ＝１
  4. 「ｂ」入力。
    入力記号ｂ＝前記号ｂ
    　リテラル数ｍ＝１≧１
    　　「０ａ」を出力
    　　リテラルをクリア、ｍ＝０
    　前記号の繰り返し数ｎ＝１＜128
    　　ｎ＝２
  5. 「ｂ」入力。
    入力記号ｂ＝前記号ｂ
    　リテラル数ｍ＝０
    　前記号の繰り返し数ｎ＝２＜128
    　　ｎ＝３
  6. 「ｃ」入力。
    入力記号ｃ≠前記号ｂ
    　前記号の繰り返し数ｎ＝３≧２
    　　「(-2)ｂ」を出力。
    　前記号＝ｃ、ｎ＝１
  7. 「ｃ」入力。
    入力記号ｃ＝前記号ｃ
    　前記号の繰り返し数ｎ＝１＜128
    　　ｎ＝２
  8. 「ｃ」入力。
    入力記号ｃ＝前記号ｃ
    　前記号の繰り返し数ｎ＝２＜128
    　　ｎ＝３
  9. 「ｃ」入力。
    入力記号ｃ＝前記号ｃ
    　前記号の繰り返し数ｎ＝３＜128
    　　ｎ＝４
  10. 「ｄ」入力。
    入力記号ｄ≠前記号ｃ
    　前記号の繰り返し数ｎ＝４≧２
    　　「(-3)ｃ」を出力。
    　前記号＝ｄ、ｎ＝１
  11. 「ｅ」入力。
    入力記号ｅ≠前記号ｄ
    　前記号の繰り返し数ｎ＝１＜２
    　　リテラルの繰り返し数ｍ＝０＜128
    　　　ｍ＝１、リテラル＝ｄ
    前記号＝ｅ、ｎ＝１
  12. 元データ終了。
    前記号の繰り返し数ｎ＝１
    　ｍ＝２、リテラル＝ｄｅ
    　「１ｄｅ」を出力

以上の結果、出力データは「0a(-2)b(-3)c1de」となり、この時の圧縮率と平均符号長は次のようになります。

圧縮率＝9×8
───
10×8		＝0.9(90％)
平均符号長＝72
──
10		＝7.2ビット

2.3 復号手順

符号化されたデータ「0a(-2)b(-3)c1de」から元のデータを復元する手順は以下のとおりです。

  1. 「０」入力
  2. リテラルグループのため、次の記号「ａ」を入力しそのまま出力
    復元データ：「ａ」
  3. 「(-2)」入力
  4. 反復グループのため、次の記号「ｂ」を入力しそれを３個出力
    復元データ：「ａｂｂｂ」
  5. 「(-3)」入力
  6. 反復グループのため、次の記号「ｃ」を入力しそれを４個出力
    復元データ：「ａｂｂｂｃｃｃｃ」
  7. 「１」入力
  8. リテラルグループのため、次の２記号「ｄｅ」を入力しそのまま出力
    復元データ：「ａｂｂｂｃｃｃｃｄｅ」
  9. 復元終了

2.4 PackBits以外の連長符号化実用例

連長符号は、PackBits以外ではWindowsのBMPファイルでビットマップデータを圧縮する場合にも用いられています。 BMPのRLEの場合、リテラルグループの記号数と反復グループの繰り返し数はどちらも１から255までの１バイト整数が用いられ、記号数および繰り返し数は最大255までとなります。 その代わり、リテラルグループと反復グループを区別するために、リテラルグループの場合は記号数の前に値０の１バイト整数が付け加えられます。 したがって、例えば「abcd」は「04abcd」と符号化され、「aaaa」は「4a」と符号化されます。

実際にプログラムを組んだりデータを圧縮してみたりするとわかりますが、このWindows方式はPackBits方式よりも効率が悪く、あまり合理的な方法とは言えません。

2.5 連長符号化の特徴

最終更新日：2001年7月2日 　第1章へ← →第3章へ
【我楽多頓陳館】 　〒webmaster@snap-tck.com 　Copyleft (C) 2000 SNAP(Sugimoto Norio Art Production)