Loading article…
ランレングス符号化（RLE ）は、可逆データ圧縮の一種で、データの連続した出現（同じデータ値の連続）を、元の連続した出現としてではなく、そのデータ値の単一の出現と、その連続出現回数として格納します。例えば、色付きのドットで構成された画像内の「緑緑緑緑緑」というシーケンスは、「緑×5」のように短縮できます。
ランレングス符号化は、アイコン、線画、ゲーム、アニメーションなどの単純な画像のように、多数の連続したパターン（ラン）を含むデータに対して最も効率的です。ランが少ないファイルの場合、RLEで符号化するとファイルサイズが大きくなる可能性があります。
RLE は、そのエンコード方式を使用する特定の画像フォーマットを指す場合もあります。RLE は、CompuServeが白黒画像を圧縮するためにサポートしていた初期のグラフィックファイルフォーマットで、後にGraphics Interchange Format (GIF) に広く取って代わられました。また、 Windows 3.xであまり使用されていない画像フォーマットの名前でもあり、ファイル拡張子 . で保存されrle、ランレングスエンコードされたビットマップで構成されています。これは、Windows 3.x の起動画面のフォーマットとして使用されていました。
ランレングス符号化 (RLE) 方式は、1967 年というかなり前からアナログテレビ信号の伝送に採用されていました。[ 1 ] 1983 年に、ランレングス符号化は日立によって特許を取得しました。[ 2 ] [ 3 ] [ 4 ] RLE は、コンピューター アイコンなどのパレットベースのビットマップ 画像 (比較的少ない色を使用) に特に適しており、GIFなどのより高度なフォーマットが登場する前のCompuServeなどの初期のオンライン サービスで人気のあった画像圧縮方式でした。[ 5 ] 写真などの連続トーン画像 (非常に多くの色を使用) には適していませんが、JPEGでは、画像ブロックを変換および量子化した後に残る係数に RLE を使用しています。
ランレングス符号化データの一般的なフォーマットには、Truevision TGA、PackBits（Apple製、MacPaintで使用）、PCX、ILBMなどがあります。国際電気通信連合は、T.45として知られるファックス機用のランレングスカラーを符号化する標準も規定しています。 [ 6 ] このファックスカラー符号化標準は、他の技術とともに修正ハフマン符号化に組み込まれており、ファックス文書のほとんどは主に空白で、時折黒が挿入されるだけなので、比較的効率的です。
RLEの空間計算量はここで、 nは入力データのサイズです。
ランレングス符号化は、繰り返し出現する文字列の物理的なサイズを縮小することでデータを圧縮します。このプロセスでは、各文字の連続出現を識別してカウントすることにより、入力データを圧縮形式に変換します。手順は以下のとおりです。
itertoolsからrepeat 、compress 、groupbyをインポートします。def ilen ( iterable ): """ 反復可能な項目の数を返します。 >>> ilen(x for x in range(1000000) if x % 3 == 0) 333334 """ # zip() を使用して入力を 1 タプルでラップし、compress() がそれを真の値として読み取ります。return sum ( compress ( repeat ( 1 ), zip ( iterable )))def rle_encode ( iterable , * , length_first = True ): """ >>> "".join(rle_encode("AAAABBBCCDAA")) '4A3B2C1D2A' >>> "".join(rle_encode("AAAABBBCCDAA", length_first=False)) 'A4B3C2D1A2' """ return ( f " { ilen ( g ) }{ k } " if length_first else f " { k }{ ilen ( g ) } " # ilen(g): iterable g の長さfor k , g in groupby ( iterable ) )デコード処理では、エンコードされた形式から元のデータを再構築するために、文字を出現回数に応じて繰り返します。手順は以下のとおりです。
itertoolsからchain 、repeat 、batchedをインポートdef rle_decode ( iterable , * , length_first = True ): """ >>> "".join(rle_decode("4A3B2C1D2A")) 'AAAABBBCCDAA' >>> "".join(rle_decode("A4B3C2D1A2", length_first=False)) 'AAAABBBCCDAA' """ return chain . from_iterable ( repeat ( b , int ( a )) if length_first else repeat ( a , int ( b )) for a , b in batched ( iterable , 2 ) )白い背景に黒一色のテキストが表示された画面を考えてみましょう。空白部分には白いピクセルが長く連続して並び、テキスト内には黒いピクセルが短く連続して並びます。黒いピクセルをB、白いピクセルをWとした場合の、仮想的な走査線は次のようになります。
WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW 上記の仮想的なスキャンラインにランレングス符号化（RLE）データ圧縮アルゴリズムを適用すると、以下のようにレンダリングできます。
12W1B12W3B24W1B14W これは、12 個の W、1 個の B、12 個の W、3 個の B などというシーケンスとして解釈でき、元の 67 文字をわずか 18 文字で表します。画像の保存に使用される実際のフォーマットは、一般的にこのようなASCII文字ではなくバイナリですが、原理は同じです。バイナリ データ ファイルもこの方法で圧縮できます。ファイル フォーマットの仕様では、パディング スペースとしてファイル内の繰り返しバイトが指定されていることがよくあります。ただし、DEFLATEなどの新しい圧縮方法では、文字列 (など) の連続を利用できるラン レングス エンコーディングの一般化であるLZ77ベースのアルゴリズムがよく使用されますBWWBWWBWWBWW。
ランレングス符号化は、データの特性や追加の圧縮アルゴリズムに対応するために、複数の方法で表現できます。たとえば、一般的な方法の1つは、2文字以上の連続文字のみをランレングスで符号化し、「エスケープ」記号を使用して連続文字を識別するか、文字自体をエスケープとして使用して、文字が2回出現するたびに連続文字であることを示す方法です。前の例では、次のようになります。
WW12BWW12BB3WW24BWW14これは、12個のW、1個のB、12個のW、3個のBといったように解釈されます。このような連続した文字列の出現頻度が低いデータでは、圧縮率を大幅に向上させることができます。
もう1つの問題は、追加の圧縮アルゴリズムの適用です。連続した文字列を抽出した後でも、異なる文字の出現頻度が高い場合があり、さらに圧縮できます。ただし、連続した文字列が発生した場所に連続した文字列の長さが書き込まれると、これらの数値の存在が通常のフローを妨げ、圧縮が難しくなります。これを克服するために、一部の連続文字列エンコーダは、データとエスケープ記号を連続文字列から分離し、2つを独立して処理できるようにします。例のデータの場合、出力は文字列 " WWBWWBBWWBWW" と数値 ( 12,12,3,24,14) の2つになります。