CFLib.org – levDistance

levDistance(s, t)

Last updated March 15, 2004

author

Nicholas Zographos
Send Email

Version: 1 | Requires: ColdFusion 5 | Library: StrLib

Rated 0 time(s). Average Rating: 0

Description:
Computes the Levenshtein distance between two strings which is defined as the number of replacements, insertions or deletions necessary to transform the first string into the second. Ported from the Java version at http://www.merriampark.com/ld.htm

Return Values:
Returns a number.

Example:

<cfoutput>#levDistance("first string", "second string")#</cfoutput>

Parameters:

Name	Description	Required
s	First string.	Yes
t	Second string.	Yes

Full UDF Source:

	
	<cfscript>
/**
 * Computes the Levenshtein distance between two strings.
 * 
 * @param s      First string. (Required)
 * @param t      Second string. (Required)
 * @return Returns a number. 
 * @author Nicholas Zographos (nicholas@nezen.net) 
 * @version 1, March 15, 2004 
 */
function levDistance(s,t) {
    var d = ArrayNew(2);
    var i = 1;
    var j = 1;
    var s_i = "A";
    var t_j = "A";
    var cost = 0;
    
    var n = len(s)+1;
    var m = len(t)+1;
    
    d[n][m]=0;
    
    if (n is 1) {
        return m;
    }
    
    if (m is 1) {
        return n;
    }
    
     for (i = 1; i lte n; i=i+1) {
      d[i][1] = i-1;
    }

    for (j = 1; j lte m; j=j+1) {
      d[1][j] = j-1;
    }
    
    for (i = 2; i lte n; i=i+1) {
      s_i = Mid(s,i-1,1);

      for (j = 2; j lte m; j=j+1) {
          t_j = Mid(t,j-1,1);

        if (s_i is t_j) {
          cost = 0;
        }
        else {
          cost = 1;
        }
        d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1);
        d[i][j] = min(d[i][j], d[i-1][j-1] + cost);
      }
    }
    
    return d[n][m];
}
</cfscript>