class Bundler::SimilarityDetector
def levenshtein_distance(this, that, ins=2, del=2, sub=1)
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 for i in 1..that.length dm[i] = [i * del, fill.flatten] end # populate matrix for i in 1..that.length for j in 1..this.length # 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