LZ4

LZ4：高速圧縮と展開を両立する可逆圧縮アルゴリズム

LZ4は、データの圧縮と展開を高速に行うことを重視した、可逆圧縮アルゴリズムです。LZ77ファミリーに属するバイト指向の圧縮方法であり、Yann Collet氏によって2011年から開発されています。Collet氏は、LZ4開発から4年後の2015年には、さらに高速な圧縮アルゴリズムであるZstandardの開発も開始しました。

LZ4の性能

LZ4は、gzipなどのアルゴリズムと比較して圧縮率はやや低めですが、LZOと同等の圧縮速度を実現しています。特に、gzipと比べると数倍高速な圧縮処理が可能です。展開速度においては、LZOよりも大幅に高速化されている点が大きな特徴です。Zstandardの開発者によると、Zstandardの--fast=4設定とLZ4は同程度の圧縮率を示しますが、解凍速度ではLZ4の方が優れているとされています。

LZ4の設計

LZ4は、データをシーケンスの連続として表現します。各シーケンスは、1バイトのトークンで始まり、このトークンは2つの4ビットフィールドに分割されています。最初のフィールドは、リテラルバイトの数、2番目のフィールドは、既にデコード済みの出力バッファからコピーするバイト数を表します。フィールドの値が15を超える場合、より長いシーケンスであることを示し、追加データの存在を示唆します。値が255の場合は、さらに1バイトを追加する必要があることを意味します。このように、255を含む追加バイト列によって、任意の長さのシーケンスを表すことが可能です。リテラル文字列が存在する場合は、その長さを示す必要があり、その後にはオフセットが続きます。オフセットは、出力バッファからコピーを開始する位置を示します。シーケンスの最後には、一致長の追加バイトが存在する場合があります。

圧縮処理は、ストリームまたはブロック単位で実行できます。より高い圧縮率を得るためには、最適な一致を探索することにより多くの計算リソースを費やすことで達成できます。これにより、出力サイズを小さくし、展開速度を向上させることが可能です。

実装と利用例

LZ4には、Yann Collet氏によるC言語のリファレンス実装が存在し、BSD[[ライセンス]]で公開されています。また、Java、C#、Pythonなど、様々なプログラミング言語へのポートやバインディングも存在します。

LZ4は、Hadoopのような大規模データベースシステムにおいて、高速な圧縮処理のために利用されています。Linuxカーネル3.11以降にもネイティブに実装されており、SquashFSファイルシステムでは3.19-rc1からサポートされています。さらに、FreeBSD、Illumos、Linux ZFS、ZFS-OSXなどのZFSファイルシステムでも、オンザフライ圧縮のためにLZ4が利用されています。ゲーム機であるPlayStation 4|PlayStation_4やNintendo Switchにも採用されています。その他の採用例については、公式ウェブサイトを参照してください。

bsdtarではLZ4が採用されていますが、GNU tarでは採用されていません。一方、Collet氏が開発したZstandardは、GNU tarとbsdtarの両方でサポートされています。

もう一度検索