RubyでMinHashを実装してみた。
SmartNews開発者ブログのb-Bit MinHashによる高速かつ省スペースな類似度判定を見て、おもしろそうだったのでMinHashをRubyで実装してみた。
MurmurHash3の実装はmurmurhash3-rubyを使わせてもらった。
% bundle init
% vi Gemfile
gem 'murmurhash3'
% bundle install
で準備完了。
require 'murmurhash3' require 'benchmark' def init_seeds(num) seeds = Array.new num.times do seeds << Random.rand(999999999) end seeds end def calc_minhash(targets, seed) hash_values = Array.new targets.each do |str| hash_values << MurmurHash3::V32.str_hash(str, seed) end hash_values.sort[0] end def calc_jaccard(str_a, str_b) k = 128 seeds = init_seeds(k) correct = 0.0 seeds.each do |seed| minhash_a = calc_minhash(str_a, seed) minhash_b = calc_minhash(str_b, seed) correct += 1 if minhash_a == minhash_b end correct/ k end puts Benchmark.measure { str_a = %w(巨人 中井 左膝 靭帯 損傷 登録 抹消) str_b = %w(中井 左膝 登録 抹消 歩行 問題) i = 10 sum = 0 i.times do jaccard = calc_jaccard(str_a, str_b) sum += jaccard puts jaccard end puts "avg = #{(sum / i.to_f)}" }
calc_jaccardのkでHash関数の個数を調整できる。
実行すると
% bundle exec ruby minhash.rb 0.3984375 0.390625 0.4453125 0.5 0.40625 0.4296875 0.4609375 0.4140625 0.3671875 0.4140625 avg = 0.42265625 0.000000 0.000000 0.000000 ( 0.005013)
のようになる
4/9 = 0.4444… となるのが理想なので、だいたい合っていると思う。
結構値がバラつく感じ。
次はb-Bit MinHashを実装してみたいと思う。