BT

Facebook、Zlibを上回る新しい圧縮アルゴリズムをオープンソース化

| 作者: Sergio De Simone フォローする 14 人のフォロワー , 翻訳者 笹井 崇司 フォローする 0 人のフォロワー 投稿日 2016年9月9日. 推定読書時間: 3 分 |

原文(投稿日:2016/09/02)へのリンク

Facebookが新しい圧縮アルゴリズムZstandard 1.0オープンソース化した。FacebookのエンジニアであるYann Collet氏とChip Turner氏の記事によると、これは「現在の標準」であるzlibよりも高速かつ高効率な、数少ない圧縮アルゴリズムの1つだという。Facebook ZstandardはCollet氏によるこれまでの成果を利用している。彼はLZ4の作者でもあり、もともと2015年に新しいアルゴリズムの最初のバージョンをリリースした。

Facebookのベンチマークによると、Zstandardはどんな圧縮率と帯域幅の組み合わせでもzlibを上回っている。

特に、標準のロスレス圧縮Silesiaコーパスを用いたとき、Zstandardはずば抜けた性能を見せた。

  • 同じ圧縮率で約3–5倍高速
  • 同じ圧縮スピードで10–15%小さいファイルを生成
  • 圧縮率によらず2倍高速に解凍
  • ずっと高い圧縮率 (~3.15に対して~4x) までスケール

ZstandardはFinite State Entropyを用いている。これはJarek Duda氏によるエントロピー符号のためのASN (Asymmetric Numeral Systems)に関する研究に基づいている。ANSは「スピードと圧縮率のトレードオフに決着をつける」ことを目指し、きめ細かな符号と非常に高速なエンコードの両方に使えて、データ暗号化をサポートする。だが、Zstandardのパフォーマンス改善の根底にあるのは、設計と実装における様々な選択にある。

  • zlibは32KBウィンドウに制限されていたが、Zstandardはモバイルや組み込み環境を含む最近の環境における巨大なメモリを利用し、固有の制限を課されない。

  • 算術演算間のデータ依存性を取り除くことで、複数のALUによって並行してシンボルをデコードするため、新しいHuffmanデコーダーHuff0が使われている。

  • Zstandardはできるだけ分岐をなくそうとし、間違った分岐予測によるコストのかかるパイプラインのフラッシュを最小限にする。たとえば、whileループを分岐を使わずに書き直すとどうなるか、以下に示す。

    /* 従来のバージョン */
    while (nbBitsUsed >= 8) { /* 各whileテストは分岐 */
      accumulator <<= 8;
      accumulator += *byte++;
      nbBitsUsed  -= 8;
    }
    
    /* 分岐なしバージョン */
    nbBytesUsed = nbBitsUsed >> 3;
    nbBitsUsed &= 7;
    ptr += nbBytesUsed;
    accumulator = read64(ptr);
  • repcodeモデリングによって、数バイトしか違わないシーケンスの圧縮を大幅に改善する。

Zstandardにはコマンドラインツールとライブラリがあり、どちらもCで書かれている。具体的に利用可能なハードウェア、圧縮対象データ、最適化のボトルネックに合わせて慎重に微調整できるよう、20以上の圧縮レベルを提供している。Facebookは、多くのユースケースに適しているデフォルトのレベル3からはじめることを推奨している。それから、スピードとスペースの適切なトレードオフを確かめながらレベル9まで上げてみたり、より高い圧縮率を求めて、圧縮スピードを気にしない場合には、レベル20以上を確保することをすすめている。

また、Zstandardの将来のバージョンに何がやってくるのか、Collet氏とTurner氏はいくつかのヒントを提示している。それにはマルチスレッドのサポート、高速な圧縮と高い圧縮率を可能にする新しい圧縮レベルなどが含まれる。

ZstandardはAppleのZLFSEやGoogleのBrotliに続くものだ。両者ともオープンソースで、それぞれ特定のユースケースに最適化しようとしている。BrotliはWebアセットとAndroid APKにとって高い圧縮率になるようチューンされているようだ。LZFSEはZlibよりも高速で同等の圧縮率でありながら、低消費電力であることを目指している。

 
 

Rate this Article

Relevance
Style
 
 

この記事に星をつける

おすすめ度
スタイル

こんにちは

コメントするには InfoQアカウントの登録 または が必要です。InfoQ に登録するとさまざまなことができます。

アカウント登録をしてInfoQをお楽しみください。

あなたの意見をお聞かせください。

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

このスレッドのメッセージについてEmailでリプライする
コミュニティコメント

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

このスレッドのメッセージについてEmailでリプライする

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

このスレッドのメッセージについてEmailでリプライする

ディスカッション

特集コンテンツ一覧

.NETの派生を理解する

Wayne Citrin 2018年7月18日 午前3時44分

ASP.NET Core - シンプルの力

Chris Klug 2018年6月4日 午前3時26分

InfoQにログインし新機能を利用する


パスワードを忘れた方はこちらへ

Follow

お気に入りのトピックや著者をフォローする

業界やサイト内で一番重要な見出しを閲覧する

Like

より多いシグナル、より少ないノイズ

お気に入りのトピックと著者を選択して自分のフィードを作る

Notifications

最新情報をすぐ手に入れるようにしよう

通知設定をして、お気に入りコンテンツを見逃さないようにしよう!

BT