Jaccard coeff against shingles.

example.rb

require 'shingles'

compare = %w{
  foo    foo
  foo    bar
  baz    boz
  foofoo foobar
}.each_slice(2)

compare.each do |a, b|
  puts 'jaccard_distance: %s ~ %s == %f' % [a, b, a.jaccard_distance(b)]
end

shingles.rb

require 'set'

#==== See
# * http://github.com/matpalm/resemblance
class String
  module Shingles
    N_GRAM_LENGTH = 3

    def shingles
      @shingles ||= -> do
        str     = dup.to_s.downcase
        n_grams = Set.new
        (length - N_GRAM_LENGTH + 1).times{|i| n_grams << str.slice(i, N_GRAM_LENGTH)}
        n_grams
      end.call
    end

    def jaccard_similarity_coeff(b)
      sa          = shingles
      sb          = b.shingles
      numerator   = (sa.intersection sb).size
      denominator = (sa.union sb).size
      numerator.to_f / denominator
    end

    def jaccard_distance(b)
      xor = 0
      union = 0
      shingles.union(b.shingles).each do |shingle|
        in_a = shingles.include? shingle
        in_b = b.shingles.include? shingle
        xor += 1 if in_a ^ in_b
        union += 1 if in_a & in_b
      end
      xor.to_f / (xor + union)
    end

    def invalidate_cache
      @shingles = nil
    end
  end

  include Shingles
end