Count-Min Sketch のライブラリを公開しました
written by Susumu Yata.
はじめに
先日 groonga プロジェクトでの利用を目的として開発しているライブラリ Madoka を公開しました．Madoka は Count-Min Sketch という手法をライブラリ化したものであり，文書集合に含まれるキーワードの頻度を求める，クエリの頻度を求める，などの用途に使うことができます．
ライブラリの使い方についてはドキュメントに書いてあるので，こちらは Count-Min Sketch と Madoka の特徴をまとめた内容になっています．
Count-Min Sketch
頻度を求めることが目的であれば，ハッシュ表による連想配列を使うのが，おそらく一般的です．キーワードやクエリ（以降，キー）を指定すれば頻度への参照を返すという連想配列であれば，主要なプログラミング言語では標準的にサポートされていると思います．それでは，Count-Min Sketch のライブラリを開発する理由はどこにあったのでしょうか．Count-Min Sketch の特徴を以下に並べてみます．
- キーを取り出すことはできません．
- キーを渡せば頻度を返すというインタフェースは用意できますが，それまでにカウントしたキーを列挙するようなことはできません．
- 高頻度のキーだけを列挙したいなどの要求については，個別に対処する必要があります．
- 誤差を含みます．
- 正確な頻度が 10,000 であるキーに対して 10,010 などの誤差を含む値を返すことがあり，厳密な頻度を求めたい状況では，直接的に使うことはできません．
- 低頻度なキーは誤差を含みやすいという特徴があります．
- 最初にサイズを決定します．
- 作成するときに指定するパラメータによってスケッチのサイズが決定されます．
- どれほどのキーを入力してもサイズは変化しませんが，代わりに誤差が大きくなっていきます．
- 最悪時間計算量が O (1) になります．
- ハッシュ表の平均時間計算量を O (1) とするのであれば，Count-Min Sketch の最悪時間計算量は O (1) です．
- 正確にはスケッチのパラメータとキーの長さに依存します．そして，実際にはキャッシュミスがボトルネックになります．
まず重要なことは，スケッチのサイズが固定されるということです．メモリ使用量は簡単に求めることが可能であり，拡張によってメモリが不足する可能性はありません．誤差を許容できるのであれば，という条件が付くものの，魅力的な特徴です．その上，低頻度キーの誤差を無視できるのであれば，一般的なハッシュ表と比べて 1/10 程度のメモリ使用量でも十分な精度を確保できます．そのため，上手くハマると極めて強力なツールになります．
一方で，あらかじめスケッチのサイズを決定しなければならないことは，大きな欠点でもあります．スケッチのサイズを小さくすれば誤差が大きくなり，逆に，スケッチのサイズを大きくすればメモリ使用量が増えてしまいます．キャッシュミスが増えて遅くなるというおまけ付きです．そして，パラメータの設定に際して考慮すべきことはメモリ使用量，許容誤差，キーの規模・分布だと分かっているものの，具体的な設定指針はまだ見えていません．これからの評価で明らかにしていきたいところですが，できれば，興味のある方には実際に使ってみていただけると助かります．
Madoka - Count-Min Sketch のライブラリ
Madoka は Count-Min Sketch のライブラリですが，精度を高めるために Conservative Update を採用しています．実は Lossy Conservative Update にも対応していますが，こちらはおまけなので，ライブラリの利用者が Lossy Conservative Update のことを知らなければ適用できません．それから， ux-trie を参考に開発したライブラリが marisa-trie になったように，既存の手法や実装の段階で思い付いたアイデアを取り込んでいます．
- MurmurHash3
- ハッシュ関数には MurmurHash3 を使っています．
- 任意のバイト列から 128 ビットのハッシュ値を一度に生成できるので便利です．
- Xorshift
- 疑似乱数の生成には 128 ビット版 Xorshift を使っています．
- シンプルで高速なので重宝します．
- ビット単位のカウンタ
- 32 ビットの整数をカウンタに使うのは勿体ないため，上限に応じて 1, 2, 4, 8, 16 ビットの整数をカウンタとして使えるようになっています．
- 1 ビットのときは Bloom Filter のそっくりさんになります．
- たとえば，頻度 10 以上になるキーを判定したいときは 4 ビットのカウンタで十分です．
- 確率的なカウンタ
- 32 ビットの整数では飽和しかねず，64 ビットの整数では大きすぎる，という理由から開発されたカウンタです．
- 浮動小数点数 と Approximate Counting Algorithm のアイデアを組み合わせることで生まれたカウンタです．
- 14 ビットの仮数部と 5 ビットの指数部により構成されるカウンタであり，約 35 兆（2^45 - 1）までの数値を表現できます．
- 仮数部が 0, 1 以外のときは確率的に値が変化するという考え方を採用することで，インクリメントや加算を実現しました．
- カウントを繰り返すことによって誤差が発生するものの，ほとんどのカウンタでは 1% 以内に収まります．
- もっと Conservative Update
- 別のキーによるインクリメントをブロックするフラグの導入により誤差を抑えています．
- 確率的なカウンタを使うときだけ有効になります．
- カウンタのサイズは 21 ビットになりますが，カウンタ 3 つをまとめて 64 ビットに格納するため，1 ビットは無駄になります．
- フィルタの適用
- すべてのカウンタに対して同じ関数を適用します．
- Lossy Conservative Update に使えます．
- カウンタが飽和してしまったときは，フィルタを使って全カウンタを引き下げた上で使いつづけるという手があります．
- スケッチの縮小
- 元のサイズを割り切れるサイズへとスケッチを縮小することができます．
- 同時にカウンタの上限を変更したりフィルタを適用したりできます．
- たとえば，カウンタの上限を 1 にして { return value >= 10; } というフィルタを適用すれば，閾値を 10 とする 2 値のスケッチへと変換できます．
- 当初の想定では，誤差が許容できる程度に縮小するだけの機能でした．
- スケッチの合成
- 二つのスケッチを合成できるようになっています．
- 別々に作成したスケッチを 1 つにまとめるという使い道があります．
というわけで，なかなか味のあるライブラリに仕上がっています．実のところ，当初は Count-Min Sketch の実用性に懐疑的でした．それが今では，使いどころは難しいものの，かなり実用的なのではないかと考えるようになりました．今後の開発においては，Windows で動くようにすることや日本語のドキュメントを用意することに加えて，Count-Min Sketch の評価を進めることを予定しています．
おわりに
Count-Min Sketch は興味深い手法であり，いろいろなところに応用できるはずです．しかし，ハッシュ表ほど汎用的な手法ではなく，知名度が低くて実例が少ないため，まだまだ選択肢としては貧弱です．ライブラリの開発が Count-Min Sketch が普及する一助になれば，それはとっても嬉しいなって思います．
2 月 25 日に開催される 第9回自然言語処理勉強会 #TokyoNLP で発表する予定です．
