diff options
author | Pratik Naik <pratiknaik@gmail.com> | 2009-03-24 12:15:43 +0000 |
---|---|---|
committer | Pratik Naik <pratiknaik@gmail.com> | 2009-03-24 12:15:43 +0000 |
commit | f97832b1e4406a76d268a96b521d2297adec0ae3 (patch) | |
tree | ec54e4d91113e8d3b6a481912a687aa97e3c63e2 /railties/guides/rails_guides/levenshtein.rb | |
parent | 6ed42ebdff05f9d28a60e91093d8f9afad03a958 (diff) | |
download | rails-f97832b1e4406a76d268a96b521d2297adec0ae3.tar.gz rails-f97832b1e4406a76d268a96b521d2297adec0ae3.tar.bz2 rails-f97832b1e4406a76d268a96b521d2297adec0ae3.zip |
Merge docrails
Diffstat (limited to 'railties/guides/rails_guides/levenshtein.rb')
-rw-r--r-- | railties/guides/rails_guides/levenshtein.rb | 29 |
1 files changed, 29 insertions, 0 deletions
diff --git a/railties/guides/rails_guides/levenshtein.rb b/railties/guides/rails_guides/levenshtein.rb new file mode 100644 index 0000000000..4010b61e26 --- /dev/null +++ b/railties/guides/rails_guides/levenshtein.rb @@ -0,0 +1,29 @@ +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 } + + # 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 + + # all done + return d[m][n] + end +end |