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
