String Comparison - Damerau-Levenshtein Algorithm

When creating a set of test records for a new Identity Insight installation, one of the things you will want to identify are pairs of string values that are similar, but not exact.  This applies to names, attributes, and numbers.

One way to evaluate the difference between two strings is to identify the changes needed to change one string to the other; the fewer the changes, the more similar the strings.  The Damerau-Levenshtein Distance algorithm counts the minimum number of insertions, deletions, substitutions, and transpositions needed to change one string to another.

Here is a Javascript function that implements the Damerau-Levenshtein algorithm.  This was written to run with cscript in a Windows environment.

function fnDamerauLevenshtein(a, b ) {
   
   //Initialize distance matrix
   var d = [];
   for (i = 0; i <= a.length; i++) {
      d[i] = [];
   }
   
   //If either string is zero length, then return the length of the other string (all insertions)
   if (a.length == 0)
      return b.length;
   if (b.length == 0)
      return a.length;
   
   //Populate initial values in matrix
   for(i = 0; i <= a.length; i++)
      d[i][0] = i;
   for(j = 0; j <= b.length; j++)
      d[0][j] = j;
   
   //Populate distance matrix
   for(i = 1; i<= a.length; i++) {
      for(j = 1; j <= b.length; j++) {
         if (a.substring(i-1, i) == b.substring(j-1, j))
            cost = 0;
         else
            cost = 1;
         
         //Levenshtein portion of algorithm, determines insertions, deletions, substitutions
         min1 = d[i - 1][j] + 1;
         min2 = d[i][j - 1] + 1;
         min3 = d[i - 1][j - 1] + cost;
         d[i][j] = Math.min(min1, min2, min3);
         
         //Damerau portion of algorithm, determines transpositions
         if(i > 1 && j > 1)
            if (a.substring(i-1, i) == b.substring(j - 2, j-1) && a.substring(i - 2, i-1) == b.substring(j-1, j))
               d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + cost);
      }
   }
   
   //The final distance value is stored in the last corner of the matrix
   return d[a.length][b.length];
}

WScript.Echo('Distance between ' + WScript.Arguments.Item(0) + ' and ' + WScript.Arguments.Item(1));
WScript.Echo(fnDamerauLevenshtein(WScript.Arguments.Item(0),WScript.Arguments.Item(1)));

Save the code as DamerauLevenshtein.js.  To test the code, open a command prompt and type:

>cscript DamerauLevenshtein.js accept except

Distance between accept and except
2

>