Class: String

Inherits:
Object show all
Defined in:
lib/string/levenshtein.rb

Instance Method Summary collapse

Instance Method Details

#levenshtein(other, ins = 2, del = 2, sub = 1) ⇒ Object

Calculates the levenshtein distance between strings. This method was taken from The Ruby Way, 2nd Edition, Hal Fulton, pp. 97-98



5
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
 
# File 'lib/string/levenshtein.rb', line 5

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
      dm[i][j] = [
           dm[i-1][j-1] +
             (self[j-1] == other[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[other.length][self.length]
end