Quick implementation of the Levenshtein (Edit Distance) Algorithm

levenshtein.rb

#!/usr/bin/env ruby

class String
  def levenshtein(other)
    range_self_end = self.size 
    range_other_end = other.size 
    data =
    (0..range_self_end).map {|s|
      (0..range_other_end).map {|t|
        t + s unless t>0 && s>0
      }
    }
    (1..range_self_end).each {|s|
      (1..range_other_end).each {|t|
        cost = (self[s-1] == other[t-1]) ? 0 : 1
        data[s][t] = [
          data[s-1][t]+1,
          data[s][t-1]+1,
          data[s-1][t-1] + cost
        ].min
      }
    }
    data.last.last
  end
end

if $0 == __FILE__
  puts "123".levenshtein("123")
  puts "1234".levenshtein("123")
  puts "123".levenshtein("1234")
  puts "ruby".levenshtein("levenshtein")
  puts "levenshtein".levenshtein("meilenstein")
end