CFLib.org – Common Function Library Project

levDistance(s, t)

Last updated March 15, 2004

author

Nicholas Zographos

Version: 1 | Requires: CF5 | Library: StrLib

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>
<!--- should output 6 --->

Parameters:

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

Full UDF Source:

/**
 * 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];
}
blog comments powered by Disqus

Search CFLib.org


Latest Additions

Kevin Cotton added
date2ExcelDate
May 5, 2016

Raymond Camden added
CapFirst
April 25, 2016

Chris Wigginton added
loremIpsum
January 18, 2016

Gary Stanton added
calculateArrival...
November 19, 2015

Sebastiaan Naafs - van Dijk added
getDaysInQuarter
November 13, 2015

Created by Raymond Camden / Design by Justin Johnson