well, I'm trying to get the levenshtein function to work, and it's

close, but it's not quite giving me the right answer and i have no idea

why.

here's the code:

class Array2D

def initialize(width, height)

@data = Array.new(width) { Array.new(height) }

end

def [](x, y)

@data[x][y]

end

def []=(x, y, value)

@data[x][y] = value

end

end

def levenshtein(s, t)

#include cost?

m = s.size

n = t.size

d = Array2D.new(m+1,n-1)

for i in 0..m

d[i,0]=i

end

for j in 0..n

d[0,j]=j

end

for j in 1..n

for i in 1..m

if(s[i].eql?(t[i])) then

d[i,j]=d[i-1,j-1]

end

if not (s[i].eql?(t[i])) then

d[i,j] = [ (d[i-1,j]+1), (d[i,j-1]+1), (d[i-1,j-1]+1)

].min

end

end

end

puts "After:"+ d.inspect

puts "Ans: "

return d[m,n]

end #end func

## ···

=================================================

# when I call it:

puts "Call to levenshtein():"

puts levenshtein("string1","2strings")

# and the output...

here's the output:

Call to levenshtein():

After:#<Array2D:0x283ee90 @data=[[0, 1, 2, 3, 4, 5, 6, 7, 8], [1, 1, 2,

3, 4, 5,

6, 7, 8], [2, 2, 2, 3, 4, 5, 6, 7, 8], [3, 3, 3, 3, 4, 5, 6, 7, 8], [4,

4, 4, 4

, 4, 5, 6, 7, 8], [5, 5, 5, 5, 5, 5, 6, 7, 8], [6, 6, 6, 6, 6, 6, 6, 7,

8], [7,

7, 7, 7, 7, 7, 7, 7, 8]]>

Ans:

8

If you check those two strings I tested with at this URL, my resulting

matrix is wrong (no idea why), and the answer should be 2...

check it here:

http://www.miislita.com/searchito/levenshtein-edit-distance.html

=

THANK YOU SO MUCH FOR ANY HELP!

--

Posted via http://www.ruby-forum.com/.