LZ4
| 作者 | Yann Collet |
|---|---|
| 初版 | 2011年4月24日 |
| 最新版 |
1.10.0
/ 2024年7月22日[1] |
| リポジトリ | |
| プログラミング 言語 | C言語 |
| 対応OS | クロスプラットフォーム |
| プラットフォーム | ポータブル |
| サポート状況 | 開発中 |
| 種別 | データ圧縮 |
| ライセンス | 二条項BSDライセンス |
| 公式サイト |
lz4 |
LZ4は、圧縮と展開の速さに焦点を当てた可逆圧縮アルゴリズムである。バイト指向の圧縮方法であるLZ77ファミリーに属する。Yann Collet が2011年より開発している。
Yann Collet は LZ4 の開発を始めた4年後の2015年より Zstandard も開発している。
機能
[編集]gzipのようなアルゴリズムより低い圧縮率であるLZOよりわずかに圧縮率が低い。しかし、圧縮速度はLZOと同等であり、gzipより数倍速い。展開速度はLZOより著しく速くなりうる[2]。
Zstandard の開発者によると LZ4 と Zstandard の --fast=4 が同程度の圧縮率だが、解凍速度は LZ4 の方が速い。[3]
設計
[編集]LZ4はデータをシーケンスの連続として表現する。それぞれのシーケンスは、2つの4ビットフィールドに分けられた1バイトのトークンで始まる。最初のフィールドは、出力にコピーされるリテラルバイトの数字で表現される。2つ目のフィールドはすでにデコードした出力バッファからコピーするバイト数を表す（0は最小の一致長である4バイトを表わす）。ビットフィールドのどちらかの値が15なら、長さがそれ以上で追加のデータがあることを示す。値が255のときは、さらにもう1バイト追加されることを示す。そのように、255の値を含む追加のバイトの並びによって任意の長さが表現される。リテラルの文字列が、追加のバイトとトークンのあとにあるなら文字列の長さを示す必要がある。この後にはオフセットが続き、出力バッファでコピーを始めるときにどれだけ戻るかを示す。（もしあればであるが、）シーケンスの終わりには一致長の追加バイトがある [4]。
圧縮はストリームまたはブロックで実行できる。より高い圧縮率は、最良一致を探し出すことに、より注力することで達成される。その結果より小さな出力とより速い展開速度が得られる。
実装
[編集]Yann Collet による C のリファレンス実装があり、BSDライセンスである。 Java、C#、Python などの多様な言語へのポートやバインディングがある[5]。
利用例
[編集]Hadoop のようなデータベースも、速い圧縮のためにこのアルゴリズムを利用している。
Linuxカーネル 3.11にもネイティブに実装されている[6]。Linux は SquashFS のために LZ4 を 3.19-rc1 からサポートしている[7]。
FreeBSD、Illumos、Linux ZFS、ZFS-OSX におけるZFSファイルシステムの実装はオンザフライ圧縮のために LZ4 アルゴリズムをサポートしている[8][9][10][11]。
PlayStation 4[12]やNintendo Switch に利用されている[13]。その他の採用例については公式サイトを参照のこと。
bsdtar では採用されているが、GNU tar では採用されていない。同じ Yann Collet が開発した Zstandard は GNU tar でも bsdtar でも採用されている。
参考文献
[編集]- ^ “releases”. GitHub. 2019年8月29日閲覧。
- ^ Michael Larabel (2013年1月28日). “Support For Compressing The Linux Kernel With LZ4”. Phoronix. 2015年8月28日閲覧。
- ^ Release Zstandard v1.3.4 - faster everything · facebook/zstd
- ^ Yann Collet (2011年5月26日). “RealTime Data Compression”. 2015年8月28日閲覧。
- ^ Extremely Fast Compression algorithm http://www.lz4.org - GitHub
- ^ Jonathan Corbet (2013年7月19日). “Kernel development”. LWN.net. 2015年8月28日閲覧。
- ^ Phillip Lougher (2014年11月27日). “Squashfs: Add LZ4 compression configuration option”. 2015年8月28日閲覧。
- ^ “FreeBSD 9.2-RELEASE Release Notes”. FreeBSD (2013年11月13日). 2015年8月28日閲覧。
- ^ “LZ4 Compression”. illumos. 2015年8月28日閲覧。
- ^ Illumos #3035 LZ4 compression support in ZFS and GRUB - GitHub
- ^ “Features: lz4 compression”. OpenZFS. 2015年8月28日閲覧。
- ^ “Open Source Software used in PlayStation®4”. 2020年7月1日閲覧。
- ^ “Nintendo Switch uses LZ4”. 2018年3月25日閲覧。