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