diff options
Diffstat (limited to 'lib/rubygems/text.rb')
-rw-r--r-- | lib/rubygems/text.rb | 41 |
1 files changed, 41 insertions, 0 deletions
diff --git a/lib/rubygems/text.rb b/lib/rubygems/text.rb index c694e8a9c0..ddf1e820a7 100644 --- a/lib/rubygems/text.rb +++ b/lib/rubygems/text.rb @@ -1,3 +1,9 @@ +###################################################################### +# This file is imported from the rubygems project. +# DO NOT make modifications in this repo. They _will_ be reverted! +# File a patch instead and assign it to Ryan Davis or Eric Hodel. +###################################################################### + require 'rubygems' ## @@ -26,5 +32,40 @@ module Gem::Text result.join("\n").gsub(/^/, " " * indent) end + # This code is based directly on the Text gem implementation + # Returns a value representing the "cost" of transforming str1 into str2 + def levenshtein_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 + + n.times do |i| + e = i+1 + + m.times do |j| + cost = (s[i] == t[j]) ? 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 |