Source code in the rexx programming language

/*REXX program  calculates and displays the  Levenshtein distance  between two strings. */
call Levenshtein   'kitten'                        ,     "sitting"
call Levenshtein   'rosettacode'                   ,     "raisethysword"
call Levenshtein   'Sunday'                        ,     "Saturday"
call Levenshtein   'Vladimir Levenshtein[1965]'    ,     "Vladimir Levenshtein[1965]"
call Levenshtein   'this algorithm is similar to'  ,     "Damerau─Levenshtein distance"
exit                                             /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
Levenshtein: procedure; parse arg o,t;  oL= length(o);   tL= length(t);     @.= 0
    say '        original string  = '    o                          /*show   old  string*/
    say '          target string  = '    t                          /*  "   target   "  */
                     do #=1  for tL;   @.0.#= #;   end  /*#*/       /*the   drop  array.*/
                     do #=1  for oL;   @.#.0= #;   end  /*#*/       /* "   insert   "   */
         do    j=1  for tL;   jm= j-1;    q= substr(t, j, 1)        /*obtain character. */
            do k=1  for oL;   km= k-1
            if q==substr(o, k, 1)  then @.k.j= @.km.jm              /*use previous char.*/
                                   else @.k.j= 1   +   min(@.km.j,  @.k.jm,  @.km.jm)
            end   /*k*/
         end      /*j*/                                             /* [↑]  best choice.*/
    say '   Levenshtein distance  = '  @.oL.tL;    say;      return


/*rexx*/

call test 'kitten'      ,'sitting'
call test 'rosettacode' ,'raisethysword'
call test 'Sunday'      ,'Saturday'
call test 'Vladimir_Levenshtein[1965]',,
          'Vladimir_Levenshtein[1965]'
call test 'this_algorithm_is_similar_to',,
          'Damerau-Levenshtein_distance'
call test '','abc'
exit 0


test: Procedure
  Parse Arg s,t
  ld.=''
  Say '          1st string  = >'s'<'
  Say '          2nd string  = >'t'<'
  Say 'Levenshtein distance  =' Levenshtein(s,length(s),t,length(t))
  Say ''
  Return


Levenshtein: Procedure
Parse Arg s,t
/* for all i and j, d[i,j] will hold the Levenshtein distance between     */
/* the first i characters of s and the first j characters of t;           */
/* note that d has (m+1)*(n+1) values                                     */
  m=length(s)
  n=length(t)
  d.=0
  Do i=1 To m  /* source prefixes can be transformed into empty string by */
    d.i.0=i    /* dropping all characters                                 */
    End
  Do j=1 To n  /* target prefixes can be reached from empty source prefix */
    d.0.j=j    /* by inserting every character                            */
    End
  Do j=1 To n
    jj=j-1
    Do i=1 To m
      ii=i-1
      If substr(s,i,1)=substr(t,j,1) Then
        d.i.j=d.ii.jj          /* no operation required                   */
      else
        d.i.j=min(d.ii.j+1,,   /* a deletion                              */
                  d.i.jj+1,,   /* an insertion                            */
                  d.ii.jj+1)   /* a substitution                          */
      End
    End
  Say '          1st string  = '    s
  Say '          2nd string  = '    t
  say 'Levenshtein distance  = ' d.m.n;   say ''
  Return d.m.n


/*rexx*/

call test 'kitten'      ,'sitting'
call test 'rosettacode' ,'raisethysword'
call test 'Sunday'      ,'Saturday'
call test 'Vladimir_Levenshtein[1965]',,
          'Vladimir_Levenshtein[1965]'
call test 'this_algorithm_is_similar_to',,
          'Damerau-Levenshtein_distance'
call test '','abc'
exit 0


test: Procedure
  Parse Arg s,t
  ld.=''
  Say '          1st string  = >'s'<'
  Say '          2nd string  = >'t'<'
  Say 'Levenshtein distance  =' LevenshteinDistance(s,length(s),t,length(t))
  Say ''
  Return


LevenshteinDistance: Procedure
Parse Arg s,t
If s==t Then Return 0;
sl=length(s)
tl=length(t)
If sl=0 Then Return tl
If tl=0 Then Return sl
Do i=0 To tl
  v0.i=i
  End
Do i=0 To sl-1
  v1.0=i+1
  Do j=0 To tl-1
    jj=j+1
    cost=substr(s,i+1,1)<>substr(t,j+1,1)
    v1.jj=min(v1.j+1,v0.jj+1,v0.j+cost)
    End
  Do j=0 to tl-1
    v0.j=v1.j
    End
  End
return v1.tl


/*rexx*/

call test 'kitten'      ,'sitting'
call test 'rosettacode' ,'raisethysword'
call test 'Sunday'      ,'Saturday'
call test 'Vladimir_Levenshtein[1965]',,
          'Vladimir_Levenshtein[1965]'
call test 'this_algorithm_is_similar_to',,
          'Damerau-Levenshtein_distance'
call test '','abc'
Exit


test: Procedure
  Parse Arg s,t
  ld.=''
  Say '          1st string  = >'s'<'
  Say '          2nd string  = >'t'<'
  Say 'Levenshtein distance  =' LevenshteinDistance(s,length(s),t,length(t))
  Say ''
  Return


LevenshteinDistance: Procedure Expose ld.
/* sl and tl are the number of characters in string s and t respectively */
  Parse Arg s,sl,t,tl
  If ld.sl.tl<>'' Then
    Return ld.sl.tl
  Select
    When sl=0 Then ld.sl.tl=tl
    When tl=0 Then ld.sl.tl=sl
    Otherwise Do
      /* test if last characters of the strings match */
      cost=substr(s,sl,1)<>substr(t,tl,1)
      /* return minimum of delete char from s, delete char from t,
         and delete char from both */
      ld.sl.tl=min(LevenshteinDistance(s,sl-1,t,tl  )+1,,
                   LevenshteinDistance(s,sl  ,t,tl-1)+1,,
                   LevenshteinDistance(s,sl-1,t,tl-1)+cost)
      End
    End
  Return ld.sl.tl