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)

23 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. 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
  4. Thank you for the auspicious writeup. It if truth be told used to be an amusement account it. Glance complex to more brought agreeable from you! Also Check: Latest WhatsApp DP

    ReplyDelete
  5. Excellent Blog! I would like to thank for the efforts you have made in writing this post. I am hoping the same best work from you in the future as well. I wanted to thank you for this websites! Thanks for sharing. Great websites! for More visit:- Whatsapp Group Names for Friends

    ReplyDelete
  6. I posted this article to my favorites and intend to return to for more outstanding articles.
    It’s all too easy to read and comprehend and
    also clever post.
    Love Shayari in Hindi

    ReplyDelete
  7. Great article. really happy to read. It’s all too easy to read and comprehend and also clever post. Read Good Night Status in English | Attitude Shayari

    ReplyDelete
  8. Thank you for sharing the post. Glad to hear the information.
    instagram

    ReplyDelete
  9. The bank at that point stores an electronic duplicate of the check, called a substitute check, in the database while the real check is stamped electronically, showing that it has been gotten the money for.Check Cashing chicago

    ReplyDelete
  10. whatsapp dp profile picture colelction best of new DP Pics
    Whatsapp dp

    ReplyDelete
  11. Thanks for Sharing Awesome Information
    Birthday Wishes for Husband is awesome way to express your feeling to your husbands
    more Happy Birthday Images

    ReplyDelete
  12. Thank you for the auspicious writeup. It if truth be told used to be an amusement account it. Glance complex to more brought agreeable from you! Also Check: Latest WhatsApp DP

    Reply

    ReplyDelete
  13. thank you for you article as i daily follows your content
    www.techchotu.com

    ReplyDelete

Note: Only a member of this blog may post a comment.