Zstandard

Zstandard
作者	Yann Collet
開発元	Yann Collet, Przemysław Skibiński (inikep)
初版	2015年1月25日
最新版	1.5.2 / 2022年6月21日 (22か月前)
リポジトリ	github.com/facebook/zstd.git;
プログラミング; 言語	C言語
対応OS	クロスプラットホーム
プラットフォーム	Portable
サポート状況	開発中
種別	データ圧縮
ライセンス	BSDライセンスとGPLv2のデュアルライセンス
公式サイト	facebook.github.io/zstd/
	テンプレートを表示

Zstandard (Zstd) は、2015年からFacebookに所属しているYann Colletによって開発された可逆圧縮アルゴリズムである。またCで書かれた前述のアルゴリズムのリファレンス実装の名前でもある。この実装のバージョン1は2016年8月にフリーソフトウェアとして公開された^[2]^[3]。

特徴

Zstandardは現在主流であるDeflate (ZIP, gzip) アルゴリズムによるものと遜色ない圧縮を、より高速に行えるように設計されている。

Zstandardは大きな検索窓の辞書式圧縮アルゴリズム (LZ77) とエントロピー符号化を併用しており、エントロピー符号化ステージで有限状態エントロピー(FSE)のtANS（英語版）あるいはハフマン符号化を使用している^[4]。Zstandardの実装で特徴的なのはエントロピー復号時に逆方向から読み取ることである。

ライセンス

リファレンス実装はBSDライセンスでGitHubにおいて公開されている。1.0以降のバージョンにおいては関連する特許の使用を認める追加ライセンス^[5] も付属している。

バージョン1.3.1 ^[6] から、この特許条項は削除され、ライセンスはBSD + GPLv2デュアルライセンスに変更された^[7]。

利用例

Linuxカーネルには2017年11月(バージョン4.14)からZstandardが含まれており、btrfsやsquashfsファイルシステムでの圧縮方法として利用可能となっている。また、2020年10月(バージョン5.9)からカーネルイメージの圧縮方法として利用可能となった。

FreeBSDカーネルには2017年からZstandardが含まれており、コアダンプ(ユーザープログラムとカーネルパニックの両方)の圧縮オプションとして利用可能となっている。

UbuntuやArch Linux等、一部のLinuxディストリビューションでパッケージ圧縮方式としてZstandardが利用できるようになった。xzに比べてパッケージのサイズが若干増加するが、展開速度は格段に高速になる。

参照

LZ77
Asymmetric Numeral Systems（英語版）
Brotli
LZFSE - AppleがiOS 9とOS X 10.11以降に使用し2016年1月にオープンソース化した類似のアルゴリズム

参考文献

^ “Releases - facebook/zstd”. 2022年11月28日閲覧。
^ Sergio De Simone, Facebook Open-Sources New Compression Algorithm Outperforming Zlib / InfoQ, Sep 02, 2016
^ “Life imitates satire: Facebook touts zlib killer just like Silicon Valley's Pied Piper”. The Register. (2016年8月31日) 2016年9月6日閲覧。
^ https://github.com/facebook/zstd/blob/master/doc/zstd_compression_format.md#entropy-encoding
^ zstd/PATENTS "Additional Grant of Patent Rights Version 2", Facebook
^ "Zstd v1.3.1 release", GitHub
^ "New license", GitHub

外部リンク

公式ウェブサイト
zstd - GitHub
Zstandard Overview - Zstandard アルゴリズムの概要（英語）
Smaller and faster data compression with Zstandard Facebook Announcement（英語） - "Zstandardによるより小さく、速い圧縮"
英ガーディアン紙はzlibの代わりにZStandardを使用している旨の記事
RFC 8878

[1] “Releases - facebook/zstd”. 2022年11月28日閲覧。

[2] Sergio De Simone, Facebook Open-Sources New Compression Algorithm Outperforming Zlib / InfoQ, Sep 02, 2016

[3] “Life imitates satire: Facebook touts zlib killer just like Silicon Valley's Pied Piper”. The Register. (2016年8月31日) 2016年9月6日閲覧。

[4] ttps://github.com/facebook/zstd/blob/master/doc/zstd_compression_format.md#entropy-encoding

[5] zstd/PATENTS "Additional Grant of Patent Rights Version 2", Facebook

[6] "Zstd v1.3.1 release", GitHub

[7] "New license", GitHub

[1]

[2]

[3]

[4]

[5]

[6]

[7]