From: thunk <gmkoller@...>
Date: 2010-12-15T03:30:28+09:00
Subject: Re: do your bit for my mental health - how to find the difference between two strings?



This is likely not what you are looking for directly, but it my give
you some ideas...

class String
    def levenshtein( other, ins=2, del=2, sub=1)
        #ins, del, sub are weighted costs
        return nil if self.nil?
        return nil if other.nil?
        dm = []      #distance matrix

        #Initialize first row values
        dm[0] 	= (0..self.length).collect { | i | i * ins }
        fill  	= [0] * (self.length - 1)

        #initialize first column values
        for i in 1..other.length
            dm[i] = [i * del, fill.flatten]
        end

        #populate matrix
        for i in 1..other.length
           for j in 1..self.length
            #critical comparison
            dm[i][j] =
            [dm[i-1][j-1] + (self[j-1] == other[i-1] ? 0 : sub),  dm[i]
[j-1] + ins,  dm[i-1][j] + del ].min
           end
        end

        #The last value in the matrix is the Levenshtein distance betw
the strings
        dm[other.length][self.length]
    end

end

def ls( ar, threshold=3 )#Array must have at least 2 elements
   word1, word2, nRslt, lRslt = ar.first.to_s, ar[1].to_s, 999, false
   if ar.size == 2
        nRslt = word1.levenshtein( word2 )
        lRslt = nRslt <= threshold
   elsif ar.size > 2
        range = 1..ar.size - 1
        range.each do | n |
            word2 = ar[n]
            nRslt = word1.levenshtein( word2 )
            puts "word2 = " + word2.to_s + ", ls value = " +
nRslt.to_s
            if nRslt <= threshold
                lRslt = true
                break
            end
        end
   end

   puts "word1 = " + word1.to_s + ", and word2 = " + word2.to_s + "
Result = " + nRslt.to_s + " Passed? " + lRslt.to_s
   lRslt
end