スナッピー（圧縮）

Snappy（旧称Zippy）は、LZ77のアイデアに基づいてGoogleがC++で記述し、2011年にオープンソース化した高速データ圧縮および解凍ライブラリです。 ^{[3] [4]}最大限の圧縮や他の圧縮ライブラリとの互換性を目指しているわけではありません。代わりに、非常に高速で妥当な圧縮を目指しています。圧縮速度は250 MB/秒、解凍速度は、 64ビットモードで動作する2011年頃の「Westmere」2.26 GHz Core i7プロセッサのシングルコアを使用した場合、500 MB/秒です。圧縮率はgzipよりも20～100%低くなります。^[5]

SnappyはBigtable、MapReduceなどのGoogleプロジェクトや、Googleの内部RPCシステムのデータ圧縮に広く使用されています。MariaDB ColumnStore、^[6] Cassandra、Couchbase、Hadoop、LevelDB、MongoDB、RocksDB、Lucene、Spark、InfluxDB、^[7] Cephなどのオープンソースプロジェクトで使用できます。[ ^8] FirefoxはlocalStorageのデータを圧縮するためにSnappyを使用しています。^{[9]圧縮されたストリームでエラーを検出するために解凍がテストされています。Snappyは}インラインアセンブラを使用せず（一部の最適化^[10]を除く）、移植可能です。

Snappy エンコーディングはビット指向ではなく、バイト指向です (ストリームからバイト全体のみが出力または消費されます)。この形式では、ハフマン コーディングや算術コーディングのようなエントロピー エンコーダーは使用されません。

ストリームの最初のバイトは圧縮されていないデータの長さで、リトルエンディアンの可変長整数[11]として保存されます。可変長 コード^の使用を可能にする^{セクション1。}各バイトの下位7ビットはデータに使用され、上位ビットは長さフィールドの終わりを示すフラグです。

ストリームの残りのバイトは、4つの要素型のいずれかを使用してエンコードされます。要素型は、要素の最初のバイト（タグバイト）の下位2ビットにエンコードされます。 ^[12]

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

コピーは辞書（解凍されたばかりのデータ）を参照します。オフセットは、現在の位置からすでに解凍されたストリームへのシフトです。長さは、辞書からコピーするバイト数です。辞書のサイズは、1.0 Snappy コンプレッサによって 32,768 バイトに制限されていましたが、バージョン 1.1 では 65,536 に更新されました。^{[引用が必要]}

Snappy形式の完全な公式説明は、Google GitHubリポジトリにあります。^[11]

テキスト

Wikipedia は、無料の Web ベースの共同作業型多言語百科事典プロジェクトです。

次のように圧縮され、説明付きの 16 進データとして表示されます。

000000 51  f0 42 57 69 6b 69 70 65 64 69 61 20 69 73 20 >Q.BWikipediaは<
000010 61 20 66 72 65 65 2c 20 77 65 62 2d 62 61 73 65 >無料のウェブベース<
000020 64 2c 20 63 6f 6c 6c 61 62 6f 72 61 74 69 76 65 >d、共同<
000030 2c 20 6d 75 6c 74 69 6c 69 6e 67 75 61 6c 20 65 >、多言語 e<

^{ストリームは、非圧縮データの長さをvarint [11] : section 1}として開始します。したがって、上位ビットがクリアされた最初のバイトは、51 ₁₆ =81バイトの長さに相当します。

最初のブロックはリテラルでなければならず、f042がそれに対応します。最初のバイトは次のように分解されます。f0 ₁₆ ⇒ len−1=111100 ₂ ;type=00 ₂ ;type 0はリテラルを意味し、length−1が111100 ₂ =60の場合は、次のバイトから長さが読み取られることを意味します。この場合は42 ₁₆ =66です。テキストの最初の66バイト（「Wikipediaは、無料で利用できるWebベースの共同作業型多言語百科事典です」）が続きます。^{[11] : 2.1}

000040 6e 63 79 63 6c 6f 09 3f  1c 70 72 6f 6a 65 63 74 >ncyclo.?.project<
000050 2e >.<

次のブロックのヘッダーは093fで構成され、 09 ₁₆ ⇒ off _h =000 ₂、len−4=010 ₂、type=01 ₂と分解されます。type 1 は「1バイトオフセット付きコピー」を示します。コピーする長さは 010 ₂ +4=6 バイトとなり、オフセットは 11 ビットの整数で、その上位ビットは off _h、下位ビットは次のバイト3fとなるため、{off _h }{3f ₁₆ }=00000111111 ₂ =63 となります。^{[11] : 2.2、2.2.1}

これは、63 バイト前から 6 バイトをコピーすることを意味します。すでに 67 バイトがコピーされているため、位置 4 (5 番目のバイトから) から 6 バイトをコピーすることと評価され、「pedia」が生成されます。

このブロックには他に内容がないので、次のブロックはすぐに始まります – 1c ₁₆ ⇒ len−1=000111 ₂ ;type=00 _{2 、つまり長さ000111 2} +1=8のリテラルです。^{[11] : 2.1}テキストの最後の部分（「プロジェクト」）が続きます。

この例では、4 文字以上の共通部分文字列はすべて圧縮プロセスによって削除されました。より一般的な圧縮ツールでは、これをより適切に圧縮できます。gzip や bzip2 などの圧縮方法とは異なり、アルファベットをビット ストリームにパックするために エントロピー エンコーディングは使用されません。

Snappyストリームは、最大4GiB−1の全体サイズの入力をサポートしています。^{[11] ：セクション1。}圧縮されていない、または不十分に圧縮されているセクション、自己識別できないセクション、単純な出力サイズチェック以外のデータ整合性メカニズムがないセクションには、大きなオーバーヘッドが追加される可能性があります。

これらの問題に対処するために、Snappyフレーミングフォーマット^[2]「Snappyフレーム」が使用される場合があります。これは、入力を最大64KiBのチャンクに分割し、^{[2] ：4.2、4.34}バイトのブロックヘッダー（1バイトの識別子と3バイトの長さ）で区切られます。^{[2] ：セクション1}

• _{FF 16}型の「ストリーム識別子」はストリームを開始し、ASCIIの「sNaPpY」のみで構成されていなければならない。^{[2] : 4.1}
• タイプ0の「圧縮データ」には、圧縮されたSnappyストリームが含まれています。^{[2] : 4.2}
• タイプ1の「非圧縮データ」には、そのまま出力にコピーするデータが含まれています。^{[2] : 4.3}

どちらのタイプのデータ チャンクにも、圧縮されていないデータの CRC-32Cチェックサムが含まれています。

タイプ2-7F ₁₆のチャンクは予約されており、必ずエラーが発生します。^{[2] : 4.5}タイプ80 ₁₆ -FE ₁₆のチャンクは、それを理解できない解凍プログラムによって無視される場合があります。^{[2] : 4.4,4.6}

SnappyディストリビューションにはC++とCのバインディングが含まれています。サードパーティが提供するバインディングとポートには^[13] C#、Common Lisp、Crystal（プログラミング言語）、Erlang、Go、Haskell、Lua、Java、Nim、Node.js、Perl、PHP、Python、R、Ruby、Rust、Smalltalk、OpenCLなどがあります。^{[14] [15]} コマンドラインインターフェースプログラムも利用可能です。^[16]

• Z標準

• スナッピーメーリングリスト