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を実装してみたいと思う。