Rubyでb-Bit MinHashを実装してみた。 - タチコマ好きなエンジニアのブログ

昨日に引き続き、SmartNews開発者ブログの「b-Bit MinHashによる高速かつ省スペースな類似度判定」を参考に、Rubyでb-Bit MinHashを実装してみた。 ビット数は1、ハッシュ関数の個数は128で計算させている。 ただし、1ビット値は最初から50％の確率で衝突するので、単に一致した回数をkで割っただけでは、真のJaccard係数が0の場合でも0.5くらいの推定値が出てきてしまいます。 とのことなので、一致数をハッシュ関数の個数で割った値から0.5を引いて2倍したものを表示させてみた。（calc_jaccardのコメントを外すと表示される） だいたい0.4に近い値が出るので多分合っているはず。 ベンチマーク的にはMinHashと大差がなかったけれど、popcountの処理をきちんと実装すれば速くなるかもしれない。 ソースコード require 'murmurhash3