diff options
author | Pratik Naik <pratiknaik@gmail.com> | 2009-04-05 23:02:44 +0100 |
---|---|---|
committer | Pratik Naik <pratiknaik@gmail.com> | 2009-04-05 23:08:02 +0100 |
commit | 32ca9a133837b2fb48d9d751f87043deed129f71 (patch) | |
tree | 7c7e5873ab4632990f5d7a25deeb8d201693b925 | |
parent | dda04f700e5d4fe7b40194555f2edbf55c02bd8c (diff) | |
download | rails-32ca9a133837b2fb48d9d751f87043deed129f71.tar.gz rails-32ca9a133837b2fb48d9d751f87043deed129f71.tar.bz2 rails-32ca9a133837b2fb48d9d751f87043deed129f71.zip |
Namespace under RailsGuides
-rw-r--r-- | railties/guides/rails_guides/levenshtein.rb | 48 |
1 files changed, 25 insertions, 23 deletions
diff --git a/railties/guides/rails_guides/levenshtein.rb b/railties/guides/rails_guides/levenshtein.rb index 4010b61e26..f99c6e6ba8 100644 --- a/railties/guides/rails_guides/levenshtein.rb +++ b/railties/guides/rails_guides/levenshtein.rb @@ -1,29 +1,31 @@ -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 +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 } + # 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 + # 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 - end - # all done - return d[m][n] + # all done + return d[m][n] + end end end |