Googleの分散データ処理言語Sawzallの統計ライブラリをC++, Ruby, Pythonから利用するライブラリSZaruを公開しました

Googleで利用されている分散データ処理言語SawzallのOSS実装 szl が公開されました。

公開されたソースの中にはSawzallの実行環境の他に大規模データ向けの統計ライブラリが含まれています。この統計ライブラリには高度なアルゴリズムが実装されているので、これを他の言語からも利用できると便利だなと思い、C++, Ruby, Pythonから利用できるようにしました。

便利な統計アルゴリズムの1つに出現回数が上位のN件の要素の抽出(top-N)があります。

top-Nを求める具体例としては、自然言語処理でよく使う、出現回数上位の単語を求める処理があります。この処理の単純な実装では、まず全単語の出現回数を求めておき、次に各単語を出現回数の降順でソートして出現回数上位の単語を求めます。しかし、この実装ではユニークな単語数K（数十万から数百万）に比例したメモリと計算量が必要となります。

それにたいしてSawzallの統計ライブラリでは、Nに比例したメモリと計算量*1でtop-Nを求められます。通常 N は K より非常に小さいので非常に少ないメモリで上位要素を求めることができます。そのかわり、ペナルティもあり、厳密なtop-Nではなく誤差を含む推定量となりますが、データ量が大きい場合は誤差は無視できます。*2

公開元は次のページとなります。
SZaru: Porting of excellent Sawzall aggregators.
今のところ有用性が高そうな3つの集計処理(top, unique, quantile)を移植しています。

SZaruの実装の過程でsawzallの内部実装を色々とみてみたのですが、オブジェクトのバイナリ列へのシリアライズが言語レベルで結びついているのが面白かったです。分散処理ではプロセス間でオブジェクトをやり取りするにシリアライズが必須なので、言語レベルで統合されている方が色々と便利なのでしょう。

なお、名前の意味は笊（ざる）になんとなくSをつけてSawzallに近い語感にしてみまいた。名前をつけてから知ったのですがszaruはハンガリー語だとツノの意味みたいです。

*1:厳密にはやや違いますが。

*2:top-Nの推定アルゴリズムはCount-Sketchと呼ばれており日本語での解説記事があります。radiumsoftware.com