連長圧縮(RLE)
任意のテキストを入力すると、それがランに分割される様子を確認できる — 同じ文字が連続して繰り返されると、単一の(記号, 個数)のペアに圧縮される。長いランはデータを縮小し、短いランはデータを増大させる。
なぜ損益分岐点はちょうど2なのか 🖖
どのランも — どれほど長くても — 記号に1、個数に1と、保存には常に同じ2単位のコストがかかる。長さLのランを符号化する価値があるのは、そのコストがL個の生の文字を書き出すより安い場合、つまりLが2より大きい場合だけである。入力全体で平均すると、この条件はL̄ = N/Rが2より大きいこと(Nは総長、Rはランの数)になる — これがまさに上の式が検証している境界線である。これはまた、RLEが汎用の圧縮アルゴリズムとしては貧弱である理由でもある。英語のテキスト、ソースコード、ランダムなデータでは、2より長いランはめったに現れない。そのためRLEは、1ビットのFAXスキャン、疎なビットマップ、単色領域を持つパレット画像など、意図的に長いランを持つように設計されたデータに限って使われる。実際のフォーマットはこの発想をさらに推し進めている。PNGは圧縮の前に各走査線にPaeth/Sub/Upの差分フィルタをかけ、まず滑らかなグラデーションをゼロに近い差分の長いランに変換する — その後をRLE(DEFLATE経由)が引き受ける。上の最悪ケースの例を試してみよう。16種類の異なる文字は長さ1のランを16個生み出すため、符号化には16文字を保存するのに32単位が必要になる — 入力サイズは2倍に膨張する。
自分でも思いつく圧縮 🖖
ランレングス符号化は、自力でも再発明できる唯一の圧縮アイデアです。WWWWWWW を一文字ずつ書き出す代わりに、ただ「W が7つ」と言うだけ——電話番号を「7を3回」と読むときの近道とまったく同じです。データを左から右へ一度だけ走査し、いま数えている連続部分より先は何も覚えないので、高速でストリーミングにも向きます。しかも可逆です。(記号, 個数) の組から元のデータを完全に復元できる点が、細部を永久に捨てる JPEG や MP3 とは違います。
膨張しないRLEの親戚 🖖
素朴な RLE は圧縮しにくいデータを2倍にしかねませんが、Apple の PackBits——1980年代の MacPaint で生まれ、今も TIFF の標準的な圧縮モード——はほとんど膨張しないよう設計されています。各ブロックは符号付きの1つの制御バイトで始まり、非負の値は「続くバイトはそのまま」、負の値は「次のバイトを繰り返す」を意味します。ユニークなデータは最大128バイトのまとまりでそのままコピーされるため、最悪でも128バイトあたり制御バイト1つしか増えません——素朴な RLE が達しうる100%ではなく、1%未満のオーバーヘッドです。