From: Tom Reilly <w3gat@...>
Date: 2006-08-01T22:54:47+09:00
Subject: Re: Detecting similar strings

Here is an implementation of levenstein distance.  It seems to me that 
there is another in ruby gems somewhere but I don't remember where.

# Determine Levenshtein distance of two strings

def Ld(s,t)

    #s string #1
    #t string #2
   
    n = s.size
    m = t.size
    a = Array.new

    if n != 0 && m != 0
   
        #2 create array
        r = Array.new
        rz = Array.new
   
        0.upto(m) {|x| r.push(0)}
   
        0.upto(n) {|x|a.push(r.dup)}
        a.each_index {|x| a[x][0] = x}
        0.upto(m) {|x| a[0][x] = x}
       
#a.each {|x| p x}
   
        cost =  0
        1.upto(n) do |i|
            1.upto(m) do |j|
                if s[i] == t[j]
                    cost =0
                else
                    cost = 1
                end
                a[i][j] = [a[ i- 1][j] +1,a[i][j - 1] + 1,a[i - 1][j - 
1] + cost].min
            end
        end
        a[n][m]
#a.each {|x| p x}
    else
        0
    end
end