Sha256: 89af7ef0372ae8ab57d9a5fb04cf8831c6748eb55e878c637c43a72300c284e5

Contents?: true

Size: 853 Bytes

Versions: 20

Compression:

Stored size: 853 Bytes

Contents

module RailsGuides
  module Levenshtein
    # This code is based directly on the Text gem implementation
    # Returns a value representing the "cost" of transforming str1 into str2
    def self.distance str1, str2
      s = str1
      t = str2
      n = s.length
      m = t.length
      max = n/2

      return m if (0 == n)
      return n if (0 == m)
      return n if (n - m).abs > max

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

      str1.each_char.each_with_index do |char1,i|
        e = i+1

        str2.each_char.each_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

      return x
    end
  end
end

Version data entries

20 entries across 19 versions & 5 rubygems

Version Path
activejob-lock-0.0.2 rails/guides/rails_guides/levenshtein.rb
solidus_backend-1.0.0.pre vendor/bundle/gems/rails-4.2.2/guides/rails_guides/levenshtein.rb
solidus_backend-1.0.0.pre vendor/bundle/gems/rails-4.2.1/guides/rails_guides/levenshtein.rb
rails-4.2.2 guides/rails_guides/levenshtein.rb
shoppe-paypal-1.1.0 vendor/bundle/ruby/2.1.0/gems/rails-4.2.1/guides/rails_guides/levenshtein.rb
rails-4.2.1 guides/rails_guides/levenshtein.rb
rails-4.2.1.rc4 guides/rails_guides/levenshtein.rb
rails-4.2.1.rc3 guides/rails_guides/levenshtein.rb
rails-4.2.1.rc2 guides/rails_guides/levenshtein.rb
rails-4.2.1.rc1 guides/rails_guides/levenshtein.rb
activejob-lock-0.0.1 rails/guides/rails_guides/levenshtein.rb
rails-4.2.0 guides/rails_guides/levenshtein.rb
rails_test-4.2.0.beta1 guides/rails_guides/levenshtein.rb
rails-4.2.0.rc3 guides/rails_guides/levenshtein.rb
rails-4.2.0.rc2 guides/rails_guides/levenshtein.rb
rails-4.2.0.rc1 guides/rails_guides/levenshtein.rb
rails-4.2.0.beta4 guides/rails_guides/levenshtein.rb
rails-4.2.0.beta3 guides/rails_guides/levenshtein.rb
rails-4.2.0.beta2 guides/rails_guides/levenshtein.rb
rails-4.2.0.beta1 guides/rails_guides/levenshtein.rb