Skip to content

Instantly share code, notes, and snippets.

@JulesWang
Forked from abangratz/levenshtein.rb
Created July 30, 2012 05:10
Show Gist options
  • Save JulesWang/3204916 to your computer and use it in GitHub Desktop.
Save JulesWang/3204916 to your computer and use it in GitHub Desktop.
Quick implementation of the Levenshtein (Edit Distance) Algorithm
#!/usr/bin/env ruby
class String
def levenshtein(other)
range_self_end = self.size
range_other_end = other.size
data =
(0..range_self_end).map {|s|
(0..range_other_end).map {|t|
t + s unless t>0 && s>0
}
}
(1..range_self_end).each {|s|
(1..range_other_end).each {|t|
cost = (self[s-1] == other[t-1]) ? 0 : 1
data[s][t] = [
data[s-1][t]+1,
data[s][t-1]+1,
data[s-1][t-1] + cost
].min
}
}
data.last.last
end
end
if $0 == __FILE__
puts "123".levenshtein("123")
puts "1234".levenshtein("123")
puts "123".levenshtein("1234")
puts "ruby".levenshtein("levenshtein")
puts "levenshtein".levenshtein("meilenstein")
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment