gistfile1.rb

class Levenshtein
  def initialize(str)
    @str = str.downcase
  end

  def distance(str2)
    distances = (0..str2.length.next).to_a
    @str.each_char.with_index do |char, i|
      distances[0] = i + 1
      sub_cost     = i
      str2.downcase.each_char.with_index do |char2, j|
        next_cost      = distances[j + 1]
        sub_cost      += 1 unless char == char2
        distances[j+1] = [next_cost    + 1,  # insertion
                          distances[j] + 1,  # deletion
                          sub_cost].min      # sub
        sub_cost       = next_cost
      end
    end
    distances[str2.length]
  end

  class Array
    def initialize(array)
      @array = array
    end

    def sort_by(str)
      levenshtein = ::Levenshtein.new(str)
      @array.sort_by! {|elem| levenshtein.distance(elem) }
    end
  end
end



lev = Levenshtein.new("migrato0n")
puts lev.distance("migration")
# => 2

# useful for finding misspellings
array = Levenshtein::Array.new(%w{cat dog migration})
array.sort_by("migrato0n").first
# => "migration"

The version in RubyGems is about 2x faster, but it isn't released yet. :'(

diff --git a/gistfile1.rb b/gistfile1.rb
index 27d6b0d..19b71b1 100644
--- a/gistfile1.rb
+++ b/gistfile1.rb
@@ -1,4 +1,9 @@
+require 'benchmark/ips'
+require 'rubygems/text'
+
 class Levenshtein
+  include Gem::Text
+
   def initialize(str)
     @str = str.downcase
   end
@@ -20,6 +25,10 @@ class Levenshtein
     distances[str2.length]
   end

+  def distance2(str2)
+    levenshtein_distance @str, str2
+  end
+
   class Array
     def initialize(array)
       @array = array
@@ -35,11 +44,8 @@ end


 lev = Levenshtein.new("migrato0n")
-puts lev.distance("migration")
-# => 2
-
-# useful for finding misspellings
-array = Levenshtein::Array.new(%w{cat dog migration})
-array.sort_by("migrato0n").first
-# => "migration"

+Benchmark.ips do |x|
+  x.report("original") { lev.distance("migration") }
+  x.report("rubygems") { lev.distance2("migration") }
+end

Result against released:

[aaron@higgins a04e51d549cc0041c48b (master)]$ ruby gistfile1.rb 
Calculating -------------------------------------
            original      1144 i/100ms
            rubygems      1210 i/100ms
-------------------------------------------------
            original    11923.7 (±5.6%) i/s -      59488 in   5.006259s
            rubygems    12899.0 (±5.0%) i/s -      65340 in   5.080290s

Against master:

[aaron@higgins a04e51d549cc0041c48b (master)]$ ruby -I~/git/rubygems/lib gistfile1.rb 
Calculating -------------------------------------
            original       968 i/100ms
            rubygems      2121 i/100ms
-------------------------------------------------
            original    12052.6 (±5.5%) i/s -      60984 in   5.076677s
            rubygems    22728.3 (±3.9%) i/s -     114534 in   5.047308s

Someday we'll have a RubyGems release!