Class: String
Instance Method Summary collapse
-
#levenshtein(other, ins = 2, del = 2, sub = 1) ⇒ Object
Calculates the levenshtein distance between strings This method was modified from the version appearing in The Ruby Way, 2nd Edition, Hal Fulton, pp.
Instance Method Details
#levenshtein(other, ins = 2, del = 2, sub = 1) ⇒ Object
Calculates the levenshtein distance between strings This method was modified from the version appearing in The Ruby Way, 2nd Edition, Hal Fulton, pp. 97-98
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
# File 'lib/string/levenshtein.rb', line 6 def levenshtein(other, ins=2, del=2, sub=1) # ins, del, sub are weighted costs return nil if self.nil? return nil if other.nil? dm = [] # distance matrix # Initialize first row values dm[0] = (0..self.length).collect { |i| i * ins } fill = [0] * (self.length - 1) # Initialize first column values for i in 1..other.length dm[i] = [i * del, fill.flatten] end # populate matrix for i in 1..other.length for j in 1..self.length # critical comparison comparisons_array = [ dm[i-1][j-1] + (self[j-1] == other[i-1] ? 0 : sub), dm[i][j-1] + ins, dm[i-1][j] + del ] dm[i][j] = comparisons_array.min end end # The last value in matrix is the # Levenshtein distance between the strings dm[other.length][self.length] end |