method

levenshtein_distance

v5.0.0.1 - Show latest stable - 0 notes - Class: Rails::Generators

1.0.0
1.1.6
1.2.6
2.0.3
2.1.0
2.2.1
2.3.8
3.0.0
3.0.9
3.1.0
3.2.1
3.2.8
3.2.13
4.0.2
4.1.8
4.2.1 (0)
4.2.7 (0)
4.2.9 (0)
5.0.0.1 (0)
5.1.7
5.2.3
6.0.0
6.1.3.1
6.1.7.7
7.0.0
7.1.3.2
7.1.3.4
What's this?

levenshtein_distance(str1, str2) protected

This code is based directly on the Text gem implementation Returns a value representing the “cost” of transforming str1 into str2

Show source

# File railties/lib/rails/generators.rb, line 282
      def self.levenshtein_distance str1, str2
        s = str1
        t = str2
        n = s.length
        m = t.length

        return m if (0 == n)
        return n if (0 == m)

        d = (0..m).to_a
        x = nil

        # avoid duplicating an enumerable object in the loop
        str2_codepoint_enumerable = str2.each_codepoint

        str1.each_codepoint.with_index do |char1, i|
          e = i+1

          str2_codepoint_enumerable.with_index do |char2, j|
            cost = (char1 == char2) ? 0 : 1
            x = [
                 d[j+1] + 1, # insertion
                 e + 1,      # deletion
                 d[j] + cost # substitution
                ].min
            d[j] = e
            e = x
          end

          d[m] = x
        end

        x
      end

levenshtein_distance

Related methods