Friday, November 6, 2015

ソート済の整数列を圧縮する件

圧縮されたソート済の整数列ってのは汎用的なデータ構造で、たとえば検索エンジンの転置インデックスとか、いろんなところで使うわけです。で、検索エンジンの場合は速度重要なので、PForDeltaとか様々なデータ構造が研究されてる。

一方、H2O には、ブラウザキャッシュに載ってない js や css をサーバプッシュする仕組み「cache-aware server push」があって、何がキャッシュされているか判定するためにブルームフィルタを全ての HTTP リクエストに含める必要がある。

で、ブルームフィルタを圧縮しようと思うと、ブルームフィルタってのはソート済の整数列として表現できるので、これを圧縮しようって話になる。

検索エンジン等で使う場合は速度重要だけど、HTTPリクエストに載せる場合は空間効率のほうが重要になる。ってことで、空間効率が理論限界に近いゴロム符号(の特殊系であるライス符号)を使うことになる。

ってことで、作ったのがgithub.com/kazuho/golombset

今週ちょっとcodecをいじって、あと気軽に試せるようにコマンドラインインターフェイスを追加した。

なので、こいつを git clone して make して、以下のような感じで使うことができる。

(100, 155, 931) というソート済の整数列をエンコード
% (echo 100; echo 155; echo 931) | ./golombset --encode | od -t x1
0000000    41  90  6d  c0  ff
0000005

同じ整数列をエンコードしてデコード
% (echo 100; echo 155; echo 931) | ./golombset --encode | ./golombset --decode
100
155
931

(100,155,931)という3つの数値を含むソート済の整数列を5バイトにエンコードできていることがわかる。

もうちょっと実際的な例として、偽陽性が1/100の確率で発生するブルームフィルタに、100個の要素を突っ込むんでエンコードすることを考える。適当にランダムな値を用いてそのようなフィルタを作成しエンコードしてみると、結果が102バイトであることがわかる。

% perl -MList::MoreUtils=uniq -e 'my @a = (); while (@a < 100) { @a = uniq sort { $a <=> $b } (@a, int rand(10000)); } print "$_\n" for @a' | ./golombset --encode | wc -c
     102

つまり、CSSやJavaScriptのような、ブラウザのレンダリングにクリティカルな影響を与えるファイルが100個あるとして、それらがウェブブラウザのキャッシュ内に存在するかを判定するためのブルームフィルタをHTTPリクエストに添付するためのオーバーヘッドは100バイト程度である、ということになる。さらに、リクエストを2回以上繰り返す場合は、HPACKによる圧縮が効く。

以上が、これなら現実的だよねってんで H2O の cache-aware server push は実装されたのでした、という経緯と、それにあわせて作ったライブラリの紹介でした。

それでは、また。

参考:
ImperialViolet - Smaller than Bloom filters
Golomb-coded sets: smaller than Bloom filters (giovanni.bajo.it)

11 comments:

  1. Your blog was too good. i really appreciate with your blog.Thanks for sharing.
    Watch T20 World Cup 2016 Live Streaming
    Cricbuzz Live Streaming

    ReplyDelete
  2. http://blog.kazuhooku.com/2015/11/mruby.html

    ReplyDelete
  3. Massive post. Really good-looking blog. A lot of blogs, I observe these days don't really present anything that I'm interested in custom essay writing service .but I'm most definitely interest in this one. I am in reality happy with article quality and direction. This post is mark on in helpful how some thought apply to any script point. Thanks a lot for protection enormous things. I am enormously a good deal thankful used designed for this place.

    ReplyDelete
  4. Mother’s Day is celebrated for our family most special person our mother. Mother is a god gift for all people in the world. Every son/daughter is celebrated Mother’s Day for their mother; they express their feelings, love, and joy with their mom. Mother’s Day is celebrated in all over the world on different days; it means Mothers Day Date is not same in all over the world. In most countries, Mother’s Day is celebrated second Sunday of month May. Mother’s Day was first celebrated in 1908 when Anna Jarvis held a memorial for her mother at St Andrew’s Methodist Church in Grafton, happy mother's day West Virginia. St Andrew’s Methodist Church now holds the International Mother’s Day Shrine.

    ReplyDelete
  5. شركة نقل عفش بالدمام الشرق الاوسط متحصصه فى نقل عفش واثاث بالدمام ونقل العفش بالخبر كما انها توفر شركة نقل عفش بالجبيل والخبر وشركة نقل عفش بالقطيف والاحساء وجميع خدمات نقل العفش والاثاث بالمنطقة الشرقية بارخص اسعار نقل عفش بالدمام وتقدم ايضا شركة تخزين عفش بالدمام والخبر
    نقل عفش بالدمام
    شركة نقل اثاث بالدمام
    شركة نقل اثاث بالخبر
    شركة نقل اثاث بالجبيل

    ReplyDelete