Snappy (データ圧縮)
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/02/21 03:18 UTC 版)
ストリームフォーマット
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]。
注釈
- ^ ストリームが出力または消費するのはバイト全体のみである。
- ^ 展開したばかりのデータ。
- ^ ヴァリアントの仕様についてはProtocol Buffersを参照。
出典
- ^ "Release 1.1.10"; 閲覧日: 2023年4月1日; 出版日: 2023年3月8日.
- ^ 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日閲覧。
- Snappy (データ圧縮)のページへのリンク