ほぼランダムな2^d個のn-bit値を効率的に圧縮する手法
Googleの中の人の論文、Detecting Near-duplicate for Web Crawling(PDF)に書かれているハッシュ値の圧縮アルゴリズムを実装、テストしてみた。
この論文ではsimhashと言うアルゴリズムによって生成される64bitのハッシュ値を使用して、かなり効率的に、内容が近いウェブページを判定する手法が解説されている。GFSとMapReduceをうまく使うことで、1日あたり10億クエリをさばくことができるらしい。
実際に内容が近いかどうかという判定は、各ウェブページのハッシュ値間のハミング距離問題に置き換えて処理している。それを効率よくこなすためにハッシュ値のテーブルをいくつか用意するわけだが、サイズが大変な事になってしまうので、圧縮できそうならした方が良いよねという感じで圧縮アルゴリズムが紹介されていた。(ただし、MapReduceを使って分散処理をするときは、圧縮しなくてもテーブルがメモリにのるので圧縮しなくても良いかも、という事らしい)
で、この圧縮アルゴリズムはものすごく実装が楽(アホな理由でデバッグに5時間くらい使ったのは秘密)。基本的にやることは
- ハッシュ値の配列をソート
- 1個前の要素とxorを取った値の配列を作る
- number of leading zerosの頻度を計算
- 3.を元にハフマン木を構築
- 圧縮されたnlz + 残りのbitを出力
- データが終わるまで5を繰り返し
という感じ。今64bitのハッシュ値を2^29個単位で圧縮しているが、大体61%程度のサイズに圧縮されている。100億個単位だと半分くらいになるらしい。2.は
for (i = hash_values.size() - 1; i > 0; i--) hash_values[i] ^= hash_values[i - 1];
と言う感じ。
また、オリジナルの解説がそうであるように、ハッシュ値に重複が発生しない、または発生させないようになっている事がわかっていれば、3.でnlzではなく、最上位の1であるbitの位置を使うことで1bit余分に圧縮できる。
そんなわけで、結構お手軽かつ高速＆比較的高圧縮率なので、使ってみると良いかもしれない。ちなみに、現在は106億個のハッシュ値を、様々なハッシュ関数に対して生成する必要があるので、効率のためにこのアルゴリズムを実装してみた感じ。nlzはHacker's Delightの方法でかなり高速に計算できるので、それを使うと良い。
追記:
肝心な事を書き忘れた。ランダムなn-bit値が2^d個あると、nlzの分布がn-dを中心に、1/2倍ずつ減っていくような分布になるので、それを元にエントロピーが計算できる。なので、使う前に大体どのくらい圧縮されるか知ることができる。
