damerau_levenshtein.rb

# An implementation of the Damerau–Levenshtein algorithm for string distance
# See: http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance
# Also based on: http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Levenshtein_distance#Ruby

module DamerauLevenshtein
  
  def self.distance(a, b)
    return b.length if a.empty?
    return a.length if b.empty?

    d = []
    0.upto(a.length) {|i| d[i] = [i]}
    0.upto(b.length) {|j| d[0][j] = j}

    1.upto(a.length) do |i|
      1.upto(b.length) do |j|
        cost = (a[i-1] == b[j-1]) ? 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
        if i > 1 and j > 1 and a[i] == b[j-1] and a[i-1] == b[j] # transposition
          d[i][j] = [d[i][j], d[i-2][j-2] + cost].min
        end
      end
    end
    d[a.length][b.length]
  end

end

if __FILE__ == $0
  puts DamerauLevenshtein.distance('String1 String2', 'String3 Strnig4')
end