levenshtein.rb

require 'rubygems'
require 'benchmark'
require 'amatch'

def levenshtein(a, b)
  return b.length if a.empty?
  return a.length if b.empty?
  asub = a[1..-1]
  bsub = b[1..-1]
  offset = (a[0] == b[0] ? 0 : 1)
  [ offset + levenshtein(asub, bsub),
    1 + levenshtein(asub, b),
    1 + levenshtein(a, bsub) ].min
end

puts "Pure Ruby\n=========\n\n"
Benchmark.bmbm do |x|
  x.report do
    50.times { levenshtein('carsten', 'carston') }
  end
end

puts "\n\nAmatch\n======\n\n"
Benchmark.bmbm do |x|
  x.report do
    50.times { Amatch::Levenshtein.new('carsten').match('carston') }
  end
end

# Pure Ruby
# =========
#
# Rehearsal ------------------------------------
#    6.240000   0.010000   6.250000 (  6.283066)
# --------------------------- total: 6.250000sec
#
#        user     system      total        real
#    6.190000   0.020000   6.210000 (  6.230275)
#
#
# Amatch
# ======
#
# Rehearsal ------------------------------------
#    0.000000   0.000000   0.000000 (  0.000137)
# --------------------------- total: 0.000000sec
#
#        user     system      total        real
#    0.000000   0.000000   0.000000 (  0.000109)