railties/guides/rails_guides/levenshtein.rb


1
2
3
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
30
31

module RailsGuides
  module Levenshtein
    # Based on the pseudocode in http://en.wikipedia.org/wiki/Levenshtein_distance
    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
  end
end