Snappy (データ圧縮)

Snappy
作者	ジェフ・ディーン; サンジャイ・ゲマワット（英語版）; スタイナー・ガンダーソン（英語版）;
開発元	Google
初版	2011年3月18日
最新版	1.2.1 / 2024年5月21日 (2か月前)
リポジトリ	github.com/google/snappy;
プログラミング; 言語	C++
対応OS	クロスプラットフォーム
プラットフォーム	ポータブル
サイズ	2 MB
種別	データ圧縮
ライセンス	Apache License 2.0（バージョン1.0.1まで）; 修正BSDライセンス;
公式サイト	google.github.io/snappy/
	テンプレートを表示

Snappy（旧称: Zippy）は、LZ77の着想に基づいてGoogleによって開発されたC++で書かれている高速なデータ圧縮ライブラリであり、2011年にオープンソース化された^[2]^[3]。Snappyは非常に速い圧縮速度と妥当な圧縮率を目的としており、高い圧縮率や他のデータ圧縮ライブラリとの互換性は目的としていない。64ビットモードで動作する2011年頃のWestmereのクロック周波数2.26 GHzのCore i7プロセッサのシングルコアを使用した場合、圧縮速度は250 MB/sで、展開速度は500 MB/sである。圧縮率はgzipより20–100%低くなる^[4]^[5]。

SnappyはBigtableやMapReduceなどのGoogleのプロジェクトや、Google内部のRPCシステムのデータ圧縮など広く使用されている。SnappyはMariaDB ColumnStore^[6]、Apache Cassandra、Couchbase Server、Apache Hadoop、LevelDB（英語版）、MongoDB、RocksDB、Apache Lucene、Apache Spark、InfluxDB（英語版）などのオープンソースプロジェクトで使用することができる^[4]。展開時に圧縮ストリーム内のエラーを検出するためにテストが行われる。Snappyのソースコードは一部の最適化を除いてインラインアセンブラを使用しておらず^[7]、移植性がある。

ストリームフォーマット

Snappyの符号化はビット指向ではなく、バイト指向である^{[注釈 1]}。このフォーマットではハフマン符号や算術符号などのエントロピーエンコーダは使用されない。

ストリームの最初のバイトは圧縮前のデータのサイズを表し、可変長符号の使用を可能にするリトルエンディアンヴァリアントとして格納される^[8]。各バイトの下位7ビットはデータに使用され、上位ビットはサイズを表すフィールドの終わりを示すフラグに使用される。

ストリーム内の残りのバイトは4つの要素型のいずれかを使用して符号化される。要素型は要素の最初のバイト（タグバイト）の下位2ビットで符号化される^[9]:

00 – リテラル – 非圧縮データ。上位6ビットはデータの長さ（len-1）を格納するために使用される。60よりも大きな長さは60（1バイト）から63（4バイト）の6ビット長で示される1–4バイトの整数に格納される。
01 – 長さを3ビットとして格納し、オフセットを11ビットとして格納してコピーする。タグバイトの後の1バイトはオフセットの一部として使用される。
10 – 長さを6ビットのタグバイトとして格納し、オフセットをタグバイトの後に2バイトの整数として格納してコピーする。
11 – 長さを6ビットのタグバイトとして格納し、オフセットをタグバイトの後に4バイトのリトルエンディアン整数として格納してコピーする。

コピーは辞書^{[注釈 2]}を参照する。オフセットは現在の位置から展開済みのストリームに戻るシフトである。長さは辞書からコピーするバイト数である。辞書のサイズはSnappyバージョン1.0のコンプレッサーでは32,768バイトに制限されていたが、バージョン1.1では65,536バイトに更新された。

Snappyフォーマットの完全な仕様書はGitHubにあるリファレンス実装のリポジトリにある^[9]。

圧縮されたストリームの例

次のテキストを圧縮する:

Wikipedia is a free, web-based, collaborative, multilingual encyclopedia project.

圧縮されたデータの16進ダンプは次のように始まる:

0000000: ca02 f042 5769 6b69 7065 6469 6120 6973  ...BWikipedia is

最初の2バイトのca02は圧縮前のデータのサイズを表すリトルエンディアンヴァリアントである^{[注釈 3]}^[8]。従って、最上位バイトは「02」である。0x02ca（ヴァリアント） = 0x014a = 330バイト。次の2バイトの0xf042は66+1バイトのリテラルが続くことを示している。

0000010: 2061 2066 7265 652c 2077 6562 2d62 6173   a free, web-bas
0000020: 6564 2c20 636f 6c6c 6162 6f72 6174 6976  ed, collaborativ
0000030: 652c 206d 756c 7469 6c69 6e67 7561 6c20  e, multilingual
0000040: 656e 6379 636c 6f09 3ff0 1470 726f 6a65  encyclo.?..proje

72バイト目の0x09は01型のタグバイトで、length - 4 = 010₂ = 2₁₀で、offset = 0x03f = 63または「pedia 」である。74バイト目の0xf014は20+1バイトの長さのリテラルである。

0000050: 6374 2e00 0000 0000 0000 0000 0000 0000  ct.

この例では、4文字以上の全ての共通部分文字列が圧縮処理によって除去された。より一般的なコンプレッサーは、これをより良く圧縮することができる。gzipやbzip2などの圧縮方法とは異なり、アルファベットをビットストリームに圧縮するために使用されるエントロピー符号はない。

インタフェース

Snappyのリファレンス実装の主なインタフェースはC++で書かれている。また、C言語向けの言語バインディングも提供している。サードパーティーによって言語バインディングと移植版が提供されており、C#、Common Lisp、Crystal、Erlang、Go、Haskell、Lua、Java、Nim、Node.js、Perl、PHP、Python、R言語、Ruby、Rust、Smalltalk、OpenCL^[10]など向けのものが含まれている^[4]。

脚注

[脚注の使い方]

注釈

^ ストリームが出力または消費するのはバイト全体のみである。
^ 展開したばかりのデータ。
^ ヴァリアントの仕様についてはProtocol Buffersを参照。

出典

^ "Release 1.2.1"; 閲覧日: 2024年5月25日; 出版日: 2024年5月21日.
^ Avram, Abel; 笹井崇司 (2011年4月13日). “Google Snappy: 高速圧縮ライブラリ”. InfoQ. C4Media Inc.. 2023年12月14日時点のオリジナルよりアーカイブ。2023年12月14日閲覧。
^ Metz, Cade (2011年3月24日). “Google open sources MapReduce compression” (英語). The Register. Situation Publishing. 2023年12月14日時点のオリジナルよりアーカイブ。2023年12月14日閲覧。
^ ^a ^b ^c “snappy” (英語). 2023年12月14日時点のオリジナルよりアーカイブ。2023年12月14日閲覧。
^ “LZO vs Snappy vs LZF vs ZLIB, A comparison of compression algorithms for fat cells in HBase” (英語). sleepcoding. Tumblr (2011年4月14日). 2023年12月14日時点のオリジナルよりアーカイブ。2023年12月14日閲覧。
^ “MariaDB Enterprise ColumnStore Storage Architecture” (英語). MariaDB Documentation. MariaDB. 2023年12月14日時点のオリジナルよりアーカイブ。2023年12月14日閲覧。
^ wmi-11; Victor Costan (2017年8月24日). “Add a loop alignment directive to work around a performance regression. · google/snappy@824e671” (英語). GitHub. GitHub, Inc.. 2023年12月14日閲覧。
^ ^a ^b “Encoding” (英語). Protocol Buffers Documentation. Google LLC. 2023年12月14日時点のオリジナルよりアーカイブ。2023年12月14日閲覧。
^ ^a ^b “snappy/format_description.txt at 27f34a580be4a3becf5f8c0cba13433f53c21337 · google/snappy” (英語). GitHub. GitHub, Inc.. 2023年12月14日閲覧。
^ “Vitis_Libraries/data_compression at b7b347a00e24eacee2870c4a3ff55cd08870f364 · Xilinx/Vitis_Libraries” (英語). GitHub. GitHub, Inc.. 2023年12月14日閲覧。