LevenshteinDistance

levenshtein_distance.rb

# coding: utf-8

class LevenshteinDistance
  def self.analyze(str1, str2, options = {})
    _options = {:insert_cost => 1, :delete_cost => 1, :replace_cost => 1}.merge(options)
    # remove Line feed code
    x = str1.chomp
    y = str2.chomp
    return 0 if x == y

    x = x.split(//)
    y = y.split(//)

    # str1 and str2 distance 2 dimensiton array
    d = initalize_table(x.size, y.size)
    (1..d.size - 1).each do |i|
      (1..d[i].size - 1).each do |j|
        d[i][j] = [
          d[i-1][j] + _options[:delete_cost],
          d[i][j-1] + _options[:insert_cost],
          d[i-1][j-1] + (x[i-1] == y[j-1] ? 0 : _options[:replace_cost])
        ].min
      end
    end
    d.last.last
  end

  # @example LevenshteinDistance.initalize_table(3,2)
  #   [
  #     [0, 1, 2],
  #     [1, 0, 0],
  #     [2, 0, 0],
  #     [3, 0, 0]
  #   ]
  def self.initalize_table(x_size, y_size)
    raise if x_size == 0 or y_size == 0
    Array.new(x_size + 1) do |i|
      i==0 ? (0..y_size).to_a : Array.new(y_size).unshift(i).map{|k| k.nil?? 0 : k}
    end
  end
end