Levenshtein distance

levenshtein_distance.rb

# coding: utf-8

def get_cost(d, c1, x, c2, y)
  costs = []
  if c1 == c2
    # 同じ場合
    costs << d[y-1][x-1]
  end

  if c1 != c2
    # 違う場合
    costs << d[y][x-1] + 1
    costs << d[y-1][x] + 1

    # 置換ありの場合
    costs << d[y-1][x-1] + 1
  end
  costs.min
end

def levenshtein_distance(str1, str2)

  # init
  w = str1.size
  h = str2.size

  d = Array.new(h+1).map{Array.new(w+1,0)}
  (w+1).times { |i| d[0][i] = i }
  (h+1).times { |i| d[i][0] = i }
  # init end

  h.times do |n2|
    w.times do |n1|
      x = n1+1
      y = n2+1
      d[y][x] = get_cost d, str1[x-1], x, str2[y-1], y
    end
  end
  d[h][w]
end

p levenshtein_distance("おおた", "とよた")
p levenshtein_distance("おおた", "おくら")
p levenshtein_distance("おおた", "かおす")