Look: levdist has
D=.<./&....
while ld has
D=. <./\&.,,,
Henry Rich
On 11/15/2022 7:03 PM, 'Mike Day' via General wrote:
This is weird. I've copied & pasted from your msg below, defining a new "ld" ,
and compared its results with my earlier copy of levdist and named as such:
ld
4 : 0
'a b'=. (x;y) /: (#x),(#y)
D=. >: iz =. i.#b
for_j. a do.
D=. <./\&.(-&iz) (>: D) <. (j ~: b) + |.!.j_index D
end.
{:D
)
levdist
4 : 0
'a b'=. (x;y) /: (#x),(#y)
D=. >: iz =. i.#b
for_j. a do.
D=. <./&.(-&iz) (>: D) <. (j ~: b) + |.!.j_index D
end.
{:D
)
They look the same to me, but: (hope the alignment's ok)
'baa'(levdist;ld)'asap'
┌─┬─┐
│2│3│
└─┴─┘
'rosettacode'(levdist;ld)'raisethesword'
┌─┬─┐
│3│8│
└─┴─┘
So I seem to have raised a hare, but can't see what's going on! It's bedtime,
so I can't compare the codes' representations right now.
Testing just now was on this iPad running Ian's new jios, but my earlier msg
was using J904 beta on the laptop, so it's not one particular architecture at
fault.
Very sorry to have found a non-existent error,
Mike
Sent from my iPad
On 15 Nov 2022, at 20:20, Henry Rich <[email protected]> wrote:
I don't see the error:
levdist NB. Taken from Rosetta Code
4 : 0
'a b'=. (x;y) /: (#x),(#y)
D=. >: iz =. i.#b
for_j. a do.
D=. <./\&.(-&iz) (>: D) <. (j ~: b) + |.!.j_index D
end.
{:D
)
'baa' levdist 'asap'
3
Henry Rich
On 11/15/2022 1:57 PM, 'Michael Day' via General wrote:
Not sure if this is General or Programming - sorry if wrong.
The J entry for this Rosetta Code "task", at
https://rosettacode.org/wiki/Levenshtein_distance#J
offers 2 J functions;
the first, "levenshtein", is a "literal transcription of the Wikipedia
implementation", to be found at
https://en.wikipedia.org/wiki/Levenshtein_distance
The second more J-oriented "levdist" is quicker and uses less memory.
However, to my surprise, it has some error. Consider this simple example:
'baa' (levenshtein ; levdist) 'asap'
┌─┬─┐
│3│2│
└─┴─┘
I haven't found where levdist fails, though I suspect it's something to do
with insertion.
For what it's worth, I've worked up a J-version of the second function
suggested in
the Wikipedia article. The relevant paragraph is headed "Iterative with two matrix
rows."
It's apparently based on this reference:
https://www.codeproject.com/Articles/13525/Fast-memory-efficient-Levenshtein-algorithm-2
Here's my function, which I call levw, the w for Wiki:
NB. Single loop J implementation of above function
NB. Doesn't need explicit v1 array
levw =: 4 : 0
'm n'=. #each 's t'=. (x;y) /: (#x),(#y)
v0 =. i. n+1
for_i. i.m do.
scost =. (}:v0) + (i{s) ~: t{~ jl =. i.n NB. substitution cost
minsdcost=. scost <. >: v0{~ jl+1 NB. minimum of substition
cost and deletion cost
icost =. >:i NB. initial insertion cost
for row i (I think!)
v0 =. (<.>:) /\.&.: |. icost, minsdcost NB. minima of insertion, deletion
& substitution cost
end.
{:v0
)
(The Wiki function has a double loop, on i.m and i.n - the inner loop is replaced by the
(<.>:) /\.&.: |. stuff )
It performs correctly in the previous test; (but I haven't tested edge cases)
'baa' (levenshtein ; levw) 'asap'
┌─┬─┐
│3│3│
└─┴─┘
The RosettaCode examples are trivial in time & space, but, FWIW,
'kitten' (levenshtein;levdist;levw)'sitting'
┌─┬─┬─┐
│3│3│3│
└─┴─┴─┘
timespacex '''kitten'' levenshtein ''sitting'''
0.0001067 4992
timespacex '''kitten'' levdist ''sitting''' NB. levdist is correct in
this case
1.31e_5 3072
timespacex '''kitten'' levw ''sitting'''
2.17e_5 3200
I would have preferred to communicate directly with the author of the J entry,
but don't
know how to find their name/s. So I do apologise to them for this public
message.
Cheers,
Mike
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
