RunLength圧縮を学ぶ

最近圧縮技術について学んでいるので，学んだことを随時ブログに書いていこうと思っています．初回記事ですが早速，今回はランレングス圧縮について学んでいきます．

ランレングス圧縮とは

ランレングス圧縮を大雑把に説明すると，連続した同じデータをひとまとめにする圧縮技術のことです．例えば

AAAAABBBBBBCCCCC

というようなデータ列があると，Aが5個，Bが6個，Cが5個というように数えていくことがあると思いますが，これをそのまま

A5B6C5

と符号化して情報量を圧縮する方式です．ここで，データがいくつ並んでいるかを表す数値をラン長と呼びます．

メリット

ランレングス圧縮のメリットとしては以下のようなものが挙げられます．

処理が単純
圧縮するデータが２値など，少ないデータ種類で構成されている場合圧縮率が良い

上記で説明したように連続したデータをまとめるだけの処理なので簡単に実装でき，扱いやすいです．また，連続すればするほど一気に圧縮できるので，例えば黒と白のみで構成された画像を圧縮する際などはデータが連続する確率が高いので圧縮率が良くなります．

デメリット

単純であるが故にデメリットもあります．

データの並びによってはデータが膨張する場合がある．

これは致命的なデメリットです．データをまとめて記述するとは言えラン長というデータを追加するため，例えば，

ABCABCABC

というデータの場合，

A1B1C1A1B1C1A1B1C1

というようにわざわざ与えなくてもいいようなところまでラン長を追加してしまって，データが２倍になります．が，これについては後述するランレングスの応用でなんとかなったりします．

ランレングスの実装

解説を踏まえて実装していきます．使用言語はPythonです．

def getRunLength(data, processPtr, code):
    run = 0

    while processPtr < len(data) and code == data[processPtr] and run < 0xff :
        processPtr += 1
        run += 1

    return (run,processPtr)

受け取ったデータの処理開始点(processPtr)から続くラン長を取得します．そして，次に処理すべき点を返すようにします．ラン長は1バイトに納めたいので256バイト以上同じデータが続くようであればそこで終了し，次につなげます．

これを用いてエンコードします．

from struct import pack, unpack_from

def encode_RLE(data):
    encode_data = b''
    processPtr = 0

    while processPtr < len(data) - 1: 
        code = data[processPtr]
        run,processPtr = getRunLength(data, processPtr, code )
        encode_data += pack('B',code) + pack('B',run)

    return encode_data

バイナリデータを扱うので，structモジュールをインポートしています．

データの最後までループを回し，ラン長を取得するたびにデータ値 + ラン長の形式で書き込んでいきます．特に複雑な部分はありません．

デコードはその逆をそのままやる感じです．

def decode_RLE(data):
    decode_data = b''
    it = iter(data)

    for code, run in zip(it, it):
        decode_data += pack('B',code) * run

    return decode_data

エンコードされたデータを受け取り，イテレータを作成して，zipという関数を用いて二つずつ取り出すようにしています．このイテレータを扱うのがスクリプト言語っぽくていいですね．もっと使いこなしていきたいです．

ランレングス圧縮の応用

上でも述べたように，このままだとデータにばらつきがある場合処理後のデータが膨張してしまう可能性があります．これについて，ラン長が１の場合にはラン長を記録しないといったような応用方法が考案されています．名前がついているものであればPackBitsという方法があったりします．これについては次回勉強していきたいと思います．