Wrong version (last line) of Levdist1, should be
Levdist1=: 4 : 0
'a b'=. (/: #&>)x;y
z=. i.>:#b
for_j. a do.
z=. (<. >:)/\.&.|.(>:{.z) , ((j ~: b) + }:z) (<. }.) >:z
t=:t,z
end.
{:z
)
R.E. Boss
> -----Oorspronkelijk bericht-----
> Van: [email protected] [mailto:programming-
> [email protected]] Namens R.E. Boss
> Verzonden: zondag 3 mei 2009 17:04
> Aan: 'Programming forum'
> Onderwerp: Re: [Jprogramming] Levenshtein distance
>
> Thanks, but my algorithm is wrong as Cerovski pointed out in
> http://jsoftware.com/pipermail/programming/2009-April/014546.html
> It does not seem trivial to repair it.
>
>
> Better is
>
> Levdist1=: 4 : 0
> 'a b'=. (/: #&>)x;y
> z=. i.>:#b
> for_j. a do.
> z=. (<. >:)/\.&.|.(>:{.z) , ((j ~: b) + }:z) (<. }.) >:z
> end.
> <./z
> )
>
> 'L R'=:(95{.32}.a.){~ 2 100 10 ?...@$95
>
> ts'T1=: L Levdist1"1 R'
> 0.025052141 7104
>
> ts'T2=: L Levenshtein"1 R'
> 0.32898822 134336
>
> ts'T3=: L levdist"1 R'
> 0.23164638 76992
>
> 2-:/\T1,T2,T3,:T4
> 1 1 1
>
>
> R.E. Boss
>
>
> > -----Oorspronkelijk bericht-----
> > Van: [email protected] [mailto:programming-
> > [email protected]] Namens Devon McCormick
> > Verzonden: dinsdag 28 april 2009 23:39
> > Aan: Programming forum
> > Onderwerp: Re: [Jprogramming] Levenshtein distance
> >
> > Mr. Boss -
> >
> > running your code, I get
> >
> > 'kitten'Levdist 'sitting'
> > |domain error: Levdist
> > | 'a b' =:t}.&.>a;b
> > |Levdist[:7]
> >
> > because of the global assignment on this line. Changing "=:" to "=."
> > seems
> > to fix it.
> >
> > Regards,
> >
> > Mr. McCormick
> >
> > 2009/4/28 R.E. Boss <[email protected]>
> >
> > > Correction:
> > >
> > > Levdist=: 4 : 0
> > > 'a b'=. (\:#&>) x;y
> > > p=: 2 0$0
> > > z=.0
> > > while. a *.&# b do.
> > > t=. a ((i.<./)@:(+...@#)([>:@,~{)])@:i. b
> > > z=.z+<:>./t
> > > p=:p,.t {.&.> a;b
> > > 'a b'=: t }.&.> a;b
> > > end.
> > > if. a +&# b do. p=:p,.a;b end.
> > > z=.z+ a +&# b
> > > )
> > >
> > > 'kitten'Levdist 'sitting'
> > > 3
> > >
> > > p
> > > +--+-+-+--+-+
> > > |si|t|t|in|g|
> > > +--+-+-+--+-+
> > > |ki|t|t|en| |
> > > +--+-+-+--+-+
> > >
> > >
> > > R.E. Boss
> > >
> > >
> > > > -----Oorspronkelijk bericht-----
> > > > Van: [email protected] [mailto:programming-
> > > > [email protected]] Namens R.E. Boss
> > > > Verzonden: dinsdag 28 april 2009 19:52
> > > > Aan: 'Programming forum'
> > > > Onderwerp: Re: [Jprogramming] Levenshtein distance
> > > >
> > > > Levdist=: 4 : 0
> > > > 'a b'=. (\:#&>) x;y
> > > > p=: 2 0$0
> > > > z=.0
> > > > while. a *.&# b do.
> > > > t=. a ((i.<./)@:(+...@#)([>:@,~{)])@:i. b
> > > > z=.z+<:>./t
> > > > p=:p,.t {.&.> a;b
> > > > 'a b'=. t }.&.> a;b
> > > > end.
> > > > z=.z+ a +&# b
> > > > )
> > > >
> > > > 'excused' Levdist 'exhausted'
> > > > 3
> > > >
> > > > p NB. exhibits distance cf.
> http://www.levenshtein.net/index.html
> > > > +-+-+---+-+--+-+
> > > > |e|x|hau|s|te|d|
> > > > +-+-+---+-+--+-+
> > > > |e|x|cu |s|e |d|
> > > > +-+-+---+-+--+-+
> > > >
> > > > 'levenshtein' Levdist 'malenstein'
> > > > 5 NB. is the right answer
> > > >
> > > > p
> > > > +---+-+---+-+--+-+-+-+
> > > > |l |e|ven|s|ht|e|i|n|
> > > > +---+-+---+-+--+-+-+-+
> > > > |mal|e|n |s|t |e|i|n|
> > > > +---+-+---+-+--+-+-+-+
> > > >
> > > >
> > > > ts'''excused'' Levdist&(100,@(#,:)]) ''exhausted'''
> > > > 0.062798674 88000
> > > >
> > > > ts'''excused'' levdist&(100,@(#,:)]) ''exhausted'''
> > > > |limit error: levdist
> > > > | stap"1 xs,"0/&}.ys
> > > >
> > > > ts'''excused'' levdist&(10,@(#,:)]) ''exhausted'''
> > > > 0.34071143 2.6334221e8
> > > >
> > > > ts'''excused'' Levdist&(10,@(#,:)]) ''exhausted'''
> > > > 0.0019793917 4672
> > > >
> > > > 'excused' (Levdist-:levdist)&(10,@(#,:)]) 'exhausted'
> > > > 1
> > > >
> > > >
> > > > R.E Boss
> > > >
> > > >
> > > > > -----Oorspronkelijk bericht-----
> > > > > Van: [email protected] [mailto:programming-
> > > > > [email protected]] Namens Aai
> > > > > Verzonden: dinsdag 28 april 2009 17:15
> > > > > Aan: Programming forum
> > > > > Onderwerp: Re: [Jprogramming] Levenshtein distance
> > > > >
> > > > > Here are IMO some optimizations:
> > > > >
> > > > > offsets for indices of neighbors advance : B
> > > > > sentence for initial matrix C much shorter
> > > > > 'match' matrix of same size, in advance : M
> > > > > no boxing of indices
> > > > >
> > > > > levdist=: 3 : 0
> > > > > :
> > > > > B=: 3 2$_1 0 0 _1 _1 _1
> > > > > M=: 0,0,. x =/ y
> > > > > C=: (ys=.i.>:#y),,.}.xs=.i.>:#x
> > > > > stap"1 xs ,"0/&}. ys
> > > > > {:, C
> > > > > )
> > > > >
> > > > > stap=: 3 : 0
> > > > > u=. >: <./ (0 0,- M {~ <y) + C{~;/B +"1/ y
> > > > > C=: u (<y)}C
> > > > > )
> > > > >
> > > > >
> > > > > 'excused' levdist 'exhausted'
> > > > > 3
> > > > >
> > > > > 'levenshtein' levdist 'malenstein'
> > > > > 4
> > > > >
> > > > >
> > > > >
> > > > >
> > > > > Hallo Jan Jacobs, je schreef op 28-04-09 11:42:
> > > > > > ls,
> > > > > > I modeled the edit-distance (or Levenshtein-distance
> > > > > > http://en.wikipedia.org/wiki/Levenshtein_distance) function for
> > > > > > strings, see below. I am not very proud of it. Hints for
> > improvements
> > > > > > on elegancy
> > > > > > are welcomed (perhaps by using Sequential Machine ;: ??).
> > > > > > Thanks in advance,
> > > > > > Jan.
> > > > > >
> > > > > > NB. Levenshtein
> > > > > > NB. y. ~ word1
> > > > > > NB. x. ~ word2
> > > > > > Levenshtein=:3 : 0
> > > > > > :
> > > > > > ]C=:(i.>:#x)(<"1(0,.~xs=.i.>:#x))}
> > > > > > (ys=.i.>:#y)(0)}0$~>:(#X=:x),#Y=:y NB. init
> > > > > > ]ind=.,<"1 (}.xs),"0/ }.ys
> > > > > > NB. relevant indices
> > > > > > step&.> ind
> > > > > > {:{:"1 C
> > > > > > )
> > > > > > NB. make single step in C matrix
> > > > > > NB. y. ~ current position
> > > > > > step=:3 : 0
> > > > > > ]ins=.>:C{~<_1 0+y
> > > > > > ]del=.>:C{~<0 _1+y
> > > > > > ]nochxc=.(>:C{~<_1 _1+y)-(X{~<:{.y)=Y{~<:{:y
> > > > > > ]C=:(<./ins,del,nochxc)(<y)}C
> > > > > > )
> > > > > > d=:1!:2&2
> > > > > > d 'asap'Levenshtein'aap' NB. 1
> > > > > > d 'excused'Levenshtein'exhausted' NB. 3
> > > > > >
> > > > > >
> > > > > >
> > > > > > Jan Jacobs
> > > > > > Esdoornstraat 33
> > > > > > 5995AN Kessel
> > > > > > T: +31 77 462 1887
> > > > > > M: +31 6 23 82 55 21
> > > > > > E: [email protected]
> > > > > >
> > > ----------------------------------------------------------------------
> > > > > > For information about J forums see
> > > http://www.jsoftware.com/forums.htm
> > > > > >
> > > > >
> > > > > --
> > > > > =@@i
> > > > >
> > > > > ------------------------------------------------------------------
> --
> > --
> > > > > 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
> > >
> >
> >
> >
> > --
> > Devon McCormick, CFA
> > ^me^ at acm.
> > org is my
> > preferred e-mail
> > ----------------------------------------------------------------------
> > 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
