Module: Guides::Levenshtein

Defined in:
lib/guides/levenshtein.rb

Class Method Summary collapse

Class Method Details

.distance(s1, s2) ⇒ Object

Based on the pseudocode in en.wikipedia.org/wiki/Levenshtein_distance.



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

def self.distance(s1, s2)
  s = s1.unpack('U*')
  t = s2.unpack('U*')
  m = s.length
  n = t.length

  # matrix initialization
  d = []
  0.upto(m) { |i| d << [i] }
  0.upto(n) { |j| d[0][j] = j }

  # distance computation
  1.upto(m) do |i|
    1.upto(n) do |j|
      cost = s[i] == t[j] ? 0 : 1
      d[i][j] = [
        d[i-1][j] + 1,      # deletion
        d[i][j-1] + 1,      # insertion
        d[i-1][j-1] + cost, # substitution
      ].min
    end
  end

  # all done
  return d[m][n]
end