diff options
author | Hiroshi SHIBATA <hsbt@ruby-lang.org> | 2021-01-04 10:09:05 +0900 |
---|---|---|
committer | Hiroshi SHIBATA <hsbt@ruby-lang.org> | 2021-01-04 13:14:43 +0900 |
commit | 5537adf719a37a30b17d39111cc03700f353aa2d (patch) | |
tree | 7523de9950b8a0118143f4ee0029aee17d043e04 /lib/rubygems/text.rb | |
parent | 35c3a24c8cbcccff1108079360e2063fc354b4bd (diff) | |
download | ruby-5537adf719a37a30b17d39111cc03700f353aa2d.tar.gz |
Track RubyGems master(3.3.0.dev) branch at 55634a8af18a52df86c4275d70fa1179118bcc20
Diffstat (limited to 'lib/rubygems/text.rb')
-rw-r--r-- | lib/rubygems/text.rb | 41 |
1 files changed, 21 insertions, 20 deletions
diff --git a/lib/rubygems/text.rb b/lib/rubygems/text.rb index 667811192d..acf25a0bcd 100644 --- a/lib/rubygems/text.rb +++ b/lib/rubygems/text.rb @@ -49,37 +49,38 @@ module Gem::Text end end - # This code is based directly on the Text gem implementation # Returns a value representing the "cost" of transforming str1 into str2 + # Vendored version of DidYouMean::Levenshtein.distance from the ruby/did_you_mean gem @ 1.4.0 + # https://git.io/JJgZI def levenshtein_distance(str1, str2) - s = str1 - t = str2 - n = s.length - m = t.length - - return m if (0 == n) - return n if (0 == m) + n = str1.length + m = str2.length + return m if n.zero? + return n if m.zero? d = (0..m).to_a x = nil - str1.each_char.each_with_index do |char1,i| - e = i + 1 + # to avoid duplicating an enumerable object, create it outside of the loop + str2_codepoints = str2.codepoints - str2.each_char.each_with_index do |char2,j| - cost = (char1 == char2) ? 0 : 1 + str1.each_codepoint.with_index(1) do |char1, i| + j = 0 + while j < m + cost = (char1 == str2_codepoints[j]) ? 0 : 1 x = min3( - d[j + 1] + 1, # insertion - e + 1, # deletion - d[j] + cost # substitution - ) - d[j] = e - e = x + d[j + 1] + 1, # insertion + i + 1, # deletion + d[j] + cost # substitution + ) + d[j] = i + i = x + + j += 1 end - d[m] = x end - return x + x end end |