J
Joe Smith
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.eql?(t)) then
d[i,j]=d[i-1,j-1]
end
if not (s.eql?(t)) 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!
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.eql?(t)) then
d[i,j]=d[i-1,j-1]
end
if not (s.eql?(t)) 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!