Tom Reilly
8/1/2006 1:55:00 PM
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