# File lib/bundler/similarity_detector.rb, line 32
def levenshtein_distance(this, that, ins = 2, del = 2, sub = 1)
# ins, del, sub are weighted costs
return nil if this.nil?
return nil if that.nil?
dm = [] # distance matrix
# Initialize first row values
dm[0] = (0..this.length).collect {|i| i * ins }
fill = [0] * (this.length - 1)
# Initialize first column values
(1..that.length).each do |i|
dm[i] = [i * del, fill.flatten]
end
# populate matrix
(1..that.length).each do |i|
(1..this.length).each do |j|
# critical comparison
dm[i][j] = [
dm[i - 1][j - 1] + (this[j - 1] == that[i - 1] ? 0 : sub),
dm[i][j - 1] + ins,
dm[i - 1][j] + del
].min
end
end
# The last value in matrix is the Levenshtein distance between the strings
dm[that.length][this.length]
end