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
