トップQs
タイムライン
チャット
視点

Snappy (データ圧縮)

Googleが開発したC++で書かれているデータ圧縮ライブラリ ウィキペディアから

Remove ads

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]。

曖昧さ回避 「Snappii（英語版）」とは異なります。
概要 作者, 開発元 ...

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]、移植性がある。

Remove ads

ストリームフォーマット

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]。

Remove ads

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

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

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 = 0102 = 210で、offset = 0x03f = 63または「pedia 」である。74バイト目の0xf014は20+1バイトの長さのリテラルである。

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

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

Remove ads

インタフェース

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]。

脚注

関連項目

外部リンク

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads
Remove ads