LevenshteinDistance.rb

#!/usr/bin/ruby
# レーベンシュタイン距離を算出するスクリプト

def LevenshteinDistance(s1, s2)
  arr = Array.new(s1.size+1)
  (0..(s1.size)).each do |i|
    arr[i] = Array.new(s2.size+1)
    arr[i][0] = i
  end
  (0..(s2.size)).each do |i|
    arr[0][i] = i
  end

  (1..(s1.size)).each do |i1|
    (1..(s2.size)).each do |i2|
      cost = s1[i1-1] == s2[i2-1] ? 0 : 1
      arr[i1][i2] = [arr[i1-1][i2]+1,
                        arr[i1][i2-1]+1,
                        arr[i1-1][i2-1]+cost].min
    end
  end

  return arr[s1.size][s2.size]
end

puts LevenshteinDistance("abc", "abcd")