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
