ランレングスエンコーディング

この記事では、ランレングスエンコーディングアルゴリズムがどのように動作し、何に使われるのか、そしてそのエンコードとデコード関数をPythonで実装する方法について説明します。

ランレングスエンコーディング(RLE)は、データ圧縮の非常にシンプルな形態で、入力としてデータのストリームが与えられ(例:「AAABBCCCC」)、出力は連続したデータ値のカウントの列(例:「3A2B4C」)となります。

このタイプのデータ圧縮は可逆的で、解凍すると元のデータがすべて復元される。

エンコード(圧縮)とデコード(伸長)の両方がシンプルであることが、このアルゴリズムの最大の魅力です。

ここでは、簡単な例として、元のデータと符号化されたデータのストリーム(「run」)を見てみましょう。

入力データ

入力データ:“`
AAAAAAFDDCCCCCCCAEEEEEEEEEEEEEEEEE


出力データ

入力データ:```
6A1F2D7C1A17E


この例では、34文字から13文字に圧縮することができました。

お気づきのように、連続した値が多いほど、圧縮の結果、スペースを節約することができます。

一方、値が頻繁に変わるデータ列(たとえば「BEFEFADED」)がある場合、スペースはまったく節約されません。

むしろ、1つの文字が2つの文字になるため、データサイズが大きくなる可能性もあります(例:「A」が「1A」になる)。

このため、RLEは特定の種類のデータやアプリケーションにしか向いていません。

例えば、物体を簡単に追跡できるロボットカメラ「Pixy」では、内蔵カメラデバイスから外部アプリケーションに転送する前に、RLEを使用してラベル付きビデオデータを圧縮しています。

各ピクセルには、「物体なし」「物体1」「物体2」などのラベルが付与されます。

RLEは、シンプルで高速、かつ低エントロピーのラベルデータを圧縮できるため、このアプリケーションに最適な符号化方式です。

エンコーディング

文字列のデータをエンコードするには、データの各文字をループして、出現回数を数える必要があります。

前の文字と異なる文字が見つかったら、出現回数とその文字をエンコードに追加します。

以下に、Pythonによる簡単な実装を示します。

# rle-encode.py


def rle_encode(data):
    encoding = ''
    prev_char = ''
    count = 1


if not data: return ''


for char in data:
        # If the prev and current characters
        # don't match...
        if char != prev_char:
            # ...then add the count and character
            # to our encoding
            if prev_char:
                encoding += str(count) + prev_char
            count = 1
            prev_char = char
        else:
            # Or increment our counter
            # if the characters do match
            count += 1
    else:
        # Finish off the encoding
        encoding += str(count) + prev_char
        return encoding


コメントから、このコードで何が起こっているのかがわかるはずです。

そうでない場合は、デバッガを使ってコードを実行し、その動作を確認するのが良い練習になるでしょう。

上記と同じファイルについて、コードを実行した例を示します。

encoded_val = rle_encode('AAAAAAFDDCCCCCCCAEEEEEEEEEEEEEEEEE')
print(encoded_val)


そして出力は

$ python rle-encode.py
6A1F2D7C1A17E


デコード

RLEエンコードされたデータストリームをデコードするのは、実はエンコードするよりももっと簡単です。

前と同じように、データストリームを一度に一文字ずつ順に見ていく。

もし数値文字があればそれを count に追加し、もし非数値文字があれば、それらの文字の count をデコードに追加し、すべての入力 data を繰り返し処理した後に呼び出し元に返されます。

以下はPythonで実装されたアルゴリズムです。

# rle-decode.py


def rle_decode(data):
    decode = ''
    count = ''
    for char in data:
        # If the character is numerical...
        if char.isdigit():
            # ...append it to our count
            count += char
        else:
            # Otherwise we've seen a non-numerical
            # character and need to expand it for
            # the decoding
            decode += char * int(count)
            count = ''
    return decode


このコードを、エンコードで得たのと同じ出力に対して実行することができます。

decoded_val = rle_decode('6A1F2D7C1A17E')
print(decoded_val)


そしてその出力はエンコード関数への元の入力と同じである。

$ python rle-decode.py
AAAAAAFDDCCCCCCCAEEEEEEEEEEEEEEEEE


この実装では、有効なRLEデータストリームがあることを確認するためのエラーチェックは行っていないことに注意してください。

入力データが正しくフォーマットされていない場合は、エラーが発生する可能性があります。

タイトルとURLをコピーしました