levenshtein_distance.rb

levenshtein_distance.rb

# http://en.wikipedia.org/wiki/Levenshtein_distance#Iterative_with_two_matrix_rows
def levenshtein_distance(s, t)
  # degenerate cases
  return 0 if (s == t)
  return t.length if (s.length == 0)
  return s.length if (t.length == 0)

  # create two work vectors of integer distances
  v0 = (0..t.length).to_a
  v1 = []

  # initialize v0 (the previous row of distances)
  # this row is A[0][i]: edit distance for an empty s
  # the distance is just the number of characters to delete from t
  i = 0
  while i < s.length
    v1[0] = i + 1

    # use formula to fill in the rest of the row
    j = 0
    while j < t.length
      cost = (s[i] == t[j]) ? 0 : 1
      v1[j + 1] = [v1[j] + 1, v0[j + 1] + 1, v0[j] + cost].min
      j += 1
    end

    # copy v1 (current row) to v0 (previous row) for next iteration
    v0[0..(v0.length-1)] = v1[0..(v0.length-1)]
    i += 1
  end
  v1[t.length]
end