842（圧縮アルゴリズム）

842、8-4-2、またはEFTは、可逆データ圧縮アルゴリズムです。これは、辞書長が制限されたLempel-Ziv圧縮のバリエーションです。一般的なデータの場合、842はLZ77の80～90%の圧縮率を実現し、スループットははるかに速く、メモリ使用量も少なくなります。 ^{[ 1 ]}ハードウェア実装では、エネルギー消費とチップ面積も最小限に抑えられます。

842圧縮は、仮想メモリ圧縮、データベース（特に列指向ストア）、ストリーミング入出力（バックアップやログファイルへの書き込みなど）に使用できます。

このアルゴリズムは、8バイトのブロックと、8、4、2バイトのサブフレーズで動作します。各フレーズのハッシュを使用して、過去のエンコード済みデータのスライディングウィンドウバッファへのオフセットを持つハッシュテーブルを検索します。一致したデータはオフセットで置き換えることができるため、各ブロックの結果は、一致したデータと新しいリテラルデータの混合になります。^{[ 2 ] [ 1 ] [ 3 ]}

IBMはPOWER7+以降のPowerプロセッサに842圧縮用のハードウェアアクセラレータと命令を追加しました。^{[ 4 ]}さらに、POWER9とPower10では、 zlibとgzipで使用されるRFC 1951 Deflateアルゴリズムのハードウェアアクセラレーションが追加されました。^{[ 5 ]}

POWERプロセッサ上でのハードウェア支援による842圧縮のためのデバイスドライバが、2011年にLinuxカーネルに追加されました。[ 6 ]最近^では、 Linuxはソフトウェア実装にフォールバックできますが、もちろんこれははるかに低速です。^{[ 7 ]} 圧縮RAMドライブ用のLinuxカーネルモジュールであるzramは、842を使用するように構成できます。

研究者らはグラフィックス処理ユニットを使用して842を実装し、専用GPUを使用すると約30倍高速な解凍が可能になることを発見した。^{[ 8 ]}オープンソースライブラリはCUDAとOpenCL用の842を提供している。^{[ 9 ]} FPGAによる842の実装は、ソフトウェア実装よりも13倍優れたスループットを示した。^{[ 10 ]}