LZ4

出典: フリー百科事典『ウィキペディア(Wikipedia)』
Jump to navigation Jump to search
LZ4
作者 Yann Collet
開発元 Yann Collet
初版 2011年4月24日 (2011-04-24)
最新版 1.7.5 / 2017年1月3日(18か月前) (2017-01-03
リポジトリ github.com/lz4/lz4
プログラミング言語 C
対応OS クロスプラットフォーム
プラットフォーム Portable
サポート状況 Active
種別 データ圧縮
ライセンス Simplified BSD License
公式サイト www.lz4.org
テンプレートを表示

LZ4 は圧縮と展開の速さに焦点を当てた可逆圧縮アルゴリズムである。バイト指向の圧縮方法であるLZ77ファミリーに属する。

機能[編集]

gzipのようなアルゴリズムより低い圧縮率であるLZOよりわずかに圧縮率が低い。しかし、圧縮速度はLZOと同等であり、gzipより数倍速い。展開速度はLZOより著しく速くなりうる[1]

設計[編集]

LZ4はデータをシーケンスの連続として表現する。それぞれのシーケンスは、2つの4ビットフィールドに分けられた1バイトのトークンで始まる。最初のフィールドは、出力にコピーされるリテラルバイトの数字で表現される。2つ目のフィールドはすでにデコードした出力バッファからコピーするバイト数を表す(0は最小の一致長である4バイトを表わす)。ビットフィールドのどちらかの値が15なら、長さがそれ以上で追加のデータがあることを示す。値が255のときは、さらにもう1バイト追加されることを示す。そのように、255の値を含む追加のバイトの並びによって任意の長さが表現される。リテラルの文字列が、追加のバイトとトークンのあとにあるなら文字列の長さを示す必要がある。この後にはオフセットが続き、出力バッファでコピーを始めるときにどれだけ戻るかを示す。(もしあればであるが、)シーケンスの終わりには一致長の追加バイトがある [2]

圧縮はストリームまたはブロックで実行できる。より高い圧縮率は、最良一致を探し出すことに、より注力することで達成される。その結果より小さな出力とより速い展開速度が得られる。

実装[編集]

Yann Collet による C のリファレンス実装があり、BSDライセンスである。 Java、C#、Python などの多様な言語へのポートやバインディングがある[3]。Hadoop のようなデータベースも、早い圧縮のためにこのアルゴリズムを利用している。 LZ4はLinuxカーネル 3.11にもネイティブに実装されている[4]。FreeBSD、Illumos、Linux ZFS、ZFS-OSX におけるZFSファイルシステムの実装はオンザフライ圧縮のために LZ4 アルゴリズムをサポートしている[5][6][7][8]。Linux は SquashFS のために LZ4 を 3.19-rc1 からサポートしている[9]

また、Nintendo Switch に利用されている[10]。その他の採用例については公式サイトを参照のこと。

参考文献[編集]

  1. ^ Michael Larabel (2013年1月28日). “Support For Compressing The Linux Kernel With LZ4”. Phoronix. 2015年8月28日閲覧。
  2. ^ Yann Collet (2011年5月26日). “RealTime Data Compression”. 2015年8月28日閲覧。
  3. ^ Extremely Fast Compression algorithm http://www.lz4.org- GitHub
  4. ^ Jonathan Corbet (2013年7月19日). “Kernel development”. LWN.net. 2015年8月28日閲覧。
  5. ^ FreeBSD 9.2-RELEASE Release Notes”. FreeBSD (2013年11月13日). 2015年8月28日閲覧。
  6. ^ LZ4 Compression”. illumos. 2015年8月28日閲覧。
  7. ^ Illumos #3035 LZ4 compression support in ZFS and GRUB- GitHub
  8. ^ Features: lz4 compression”. OpenZFS. 2015年8月28日閲覧。
  9. ^ Phillip Lougher (2014年11月27日). “Squashfs: Add LZ4 compression configuration option”. 2015年8月28日閲覧。
  10. ^ Nintendo Switch uses LZ4”. 2018年3月25日閲覧。

外部リンク[編集]