module Gem::Text

def levenshtein_distance str1, str2
  s = str1
  t = str2
  n = s.length
  m = t.length
  max = n/2
  return m if (0 == n)
  return n if (0 == m)
  return n if (n - m).abs > max
  d = (0..m).to_a
  x = nil
  n.times do |i|
    e = i+1
    m.times do |j|
      cost = (s[i] == t[j]) ? 0 : 1
      x = [
           d[j+1] + 1, # insertion
           e + 1,      # deletion
           d[j] + cost # substitution
          ].min
      d[j] = e
      e = x
    end
    d[m] = x
  end
  return x
end