ColdFusion Levenshtein Distance: String comparison and highlighting

Excellent work!

I was about to add a feature to a project that needs to tell the user that two pieces of text aren't different enough (for SEO purposes) and this looks like it'll work a treat.

Many thanks.

Glad it's useful to you!

Thanks this worked perfectly and was very useful.

You know there is a Java implementation of the Levenshtein algorithm under StringUtils in the Jakarta Commons lang package that you ought to be able to access directly from ColdFusion? That being said, I'm very interested in how you did your highlighting, and almost wish I was using ColdFusion instead of JSP so I could just use yours ;)

Legend! You just saved me a monkey load of work. I need to correct an error in some software that has led to a database being out of touch with another reference database - don't ask about the bad DB design.

If this works, I'll owe you a cupcake!

@Topper: I hope it helps you. I like chocolate :)

Seriously though, if you need to compare two databases, Redgate software makes some very kick butt tools for that. They will show you line by line comparisons of stored procs and stuff, but when it comes to the differences in data I think it just tells you they aren't the same.

Very nice work, Brad. I was all set to dive into this when I found your blog post. Thanks much!

Hey, after a year I actually find this post :) Thanks for linking my blog and for using my algorithm! Your explanations are so much cooler and visually nice than mine. Good job!

Hey, Nice script! .. .but you need to var the return_stuct too. / Andy www.cfwheels.org

Good call, Andy.

I updated the post and the download.

Hey guys, I know I'm late to the game here, though wanted to extend my thanks. I was looking for a ColdFusion implementation of string comparison highlighting, and Brad's solution works great! I did add a couple function arguments for the highlighting markup used, but other than that the original function was left untouched.

Hi, Anyone knows how to compare two strings, then returns the diff. For example: s1 = 'GIT-04 (INT) AMT DR' s2 = 'GIT-04 (INT)' it will returns 'AMT DR' I spent hours using Javascript and Coldfusion, but there is no luck. Any advise, anyone?

Great post. One comment: 177 distance = (len(s1) + len(s2))/2 - lcs; 178 // Whcih string was longest? 179 maxLen = iif(len(s1) gt len(s2),de(len(s1)),de(len(s2))); 180 // Similarity is the distance divided by the max length 181 similarity = iif(maxLen eq 0,1,1-(distance/maxLen)); Should/could be 177 var distance = (len(s1) + len(s2))/2 - lcs; 178 // Whcih string was longest? 179 var maxLen = iif(len(s1) gt len(s2),de(len(s1)),de(len(s2))); 180 // Similarity is the distance divided by the max length 181 var similarity = iif(maxLen eq 0,1,1-(distance/maxLen));

You might also be interested in http://cfdiff.googlecode.com/ . Keep up the good work.

The script is great to compare char by char. Is there a script to highlight whole word if one char is different?

I needed this function to be in Cso I converted the code from the original CF but am getting index out of bounds error. Attached is the code. Can someone please try this out in Cand help me figure out why it is crashing. Perhaps my manual conversion is not adequate.

Val

    public string GetFixedLengthString(string input, int length)
    {
        input = input ?? string.Empty;
        input = input.Length > length ? input.Substring(0, length) : input;
        return string.Format("{0,-" + length + "}", input);
    }

    // define the resulting variables
    private int return_struct_lcs;
	private float return_struct_similarity;
	private int return_struct_distance;
	private string return_struct_s1; 
	private string return_struct_s2; 
    /*
	StringSimilarity
	Brad Wood
	[email protected]

	May 2007

	Code adopted from Siderite Zackwehdex's Blog
		http://siderite.blogspot.com/2007/04/super-fast-and-accurate-string-distance.html

	Parameters:
		s1:			First string to be compared
		s2:			Second string to be compared
		maxOffset:	Average number of characters that s1 will deviate from s2 at any given point.
					This is used to control how far ahead the function looks to try and find the 
					end of a peice of inserted text.  Play with it to suit.
*/
    /// <summary>
    /// Val converted manually form the Cold Fusion code at
    /// http://www.codersrevolution.com/index.cfm/2008/7/29/ColdFusion-Levenshtein-Distance-String-comparison-and-highlighting
    /// </summary>
    /// <param name="s1"></param>
    /// <param name="s2"></param>
    /// <param name="maxOffset"></param>
    public void stringSimilarity(string s1, string s2, int maxOffset)
    {
        int c = 0;
        int offset1 = 0;
        int offset2 = 0;
        int lcs = 0;

		// These two strings will contain the "highlighted" version
		// was: string _s1 = createObject("java","java.lang.StringBuffer").init(javacast("int",s1.Length*3));
		// Was: string _s2 = createObject("java","java.lang.StringBuffer").init(javacast("int",s2.Length*3));

        string _s1 = ""; // Val
        string _s2 = ""; // Val
        _s1 = GetFixedLengthString(_s1, s1.Length * 3); // Val
        _s2 = GetFixedLengthString(_s2, s2.Length * 3); // Val

		// These charactes will surround differences in the strings 
		// (Inserted into _s1 and _s2)
        //was: string h1 = "<span style="/"background: yellow;"/">";
        //was: string h2 = "</span>";
        string h1 = "<font color=red>";
        string h2 = "</font>";

		// was: var return_struct = structNew();

        s1 = s1.Trim();
        s2 = s2.Trim();
		// If both strings are empty 
        if (String.IsNullOrEmpty(s1) && String.IsNullOrEmpty(s2)) // was: (!s1.Length && !s2.Length)
			{	
				return_struct_lcs = 0;
				return_struct_similarity = 1;
				return_struct_distance = 0;
				return_struct_s1 = "";
				return_struct_s2 = "";

	            //return return_struct;
			}

		// If s2 is empty, but s1 isn't
            if (!String.IsNullOrEmpty(s1) && String.IsNullOrEmpty(s2))// was:(s1.Length && !s2.Length)
			{
				return_struct_lcs = 0;
				return_struct_similarity = 0;
				return_struct_distance = s1.Length;
				return_struct_s1 = h1 + s1 + h2;
				return_struct_s2 = "";

	            //return return_struct;
			}

		// If s1 is empty, but s2 isn't
            else if (String.IsNullOrEmpty(s1) && !String.IsNullOrEmpty(s2))// was:(s2.Length && !s1.Length)
			{
				return_struct_lcs = 0;
				return_struct_similarity = 0;
				return_struct_distance = s2.Length;
				return_struct_s1 = "";
				return_struct_s2 = h1 + s2 + h2;

	            //return return_struct;
			}

		
		// Examine the strings, one character at a time, anding at the shortest string
		// The offset adjusts for extra characters in either string.

            while ((c + offset1 < s1.Length) 
               && (c + offset2 < s2.Length)) 
        {
			// Pull the next charactes out of s1 and s2
            //was: string next_s1 = mid(s1,c + offset1+1,iif(!c,3,1)); // First time through check the first three
            //was: string next_s2 = mid(s2,c + offset2+1,iif(!c,3,1)); // First time through check the first three

            int iif; // Val
            if (c == 0) iif = 3; else iif = 1; // Val 

            string next_s1 = s1.Substring(c + offset1 + 1, iif); // First time through check the first three
            string next_s2 = s2.Substring(c + offset2 + 1, iif); // First time through check the first three

			// If they are equal
            if (next_s1 == next_s2) //was:(compare(next_s1,next_s2) == 0)
				{
					// Our longeset Common String just got one bigger
					lcs = lcs + 1;

					// Append the characters onto the "highlighted" version
					// was: _s1.append(left(next_s1,1));
					// was: _s2.append(left(next_s2,1));
                    _s1 = _s1 + next_s1.Substring(0,1);
                    _s2 = _s2 + next_s2.Substring(0,1);
				}

			// The next two charactes did not match
			// Now we will go into a sub-loop while we attempt to 
			// find our place again.  We will only search as long as
			// our maxOffset allows us to.

            else
                {
					// Don't reset the offsets, just back them up so you 
					// have a point of reference
                    int old_offset1 = offset1;
                    int old_offset2 = offset2;
					string _s1_deviation = "";
					string _s2_deviation = "";

					// Loop for as long as allowed by our offset 
					// to see if we can match up again
                    for (int i = 0; i < maxOffset; i++)
                    {
						//was: next_s1 = mid(s1,c + offset1 + i+1,3); // Increments each time through.
                        next_s1 = s1.Substring(c + offset1 + i + 1, 3); // Increments each time through.

                        int len_next_s1 = next_s1.Length;
						// was: string bookmarked_s1 = mid(s1,c + offset1+1,3); // stays the same
                        string bookmarked_s1 = s1.Substring(c + offset1 + 1,3);

						//was: next_s2 = mid(s2,c + offset2 + i+1,3); // Increments each time through.
                        next_s2 = s2.Substring(c + offset2 + i + 1, 3); // Increments each time through.

                        int len_next_s2 = next_s2.Length;
						//was: string bookmarked_s2 = mid(s2,c + offset2+1,3); // stays the same
                        string bookmarked_s2 = s2.Substring(c + offset2 + 1, 3); // stays the same


						// If we reached the end of both of the strings
                        if ((len_next_s1 == 0) && (len_next_s2 == 0)) // was: (!len_next_s1 && !len_next_s2)
							{
								// Quit
								break;
							}

						// These variables keep track of how far we have deviated in the
						// string while trying to find our match again.
                            _s1_deviation = _s1_deviation + next_s1.Substring(0, 1); // was: left(next_s1,1);
                            _s2_deviation = _s2_deviation + next_s2.Substring(0, 1); // was; left(next_s2,1);

						// It looks like s1 has a match down the line which fits
						// where we left off in s2

                        if (next_s1 == bookmarked_s2)// was: (compare(next_s1,bookmarked_s2) == 0)
	                        {
								// s1 is now offset THIS far from s2
	                            offset1 =  offset1+i;

								// Our longeset Common String just got bigger
								lcs = lcs + 1;

								// Now that we match again, break to the main loop
	                            break;
	                        }
							

						// It looks like s2 has a match down the line which fits
						// where we left off in s1

                            if (next_s2 == bookmarked_s1) // was: (compare(next_s2,bookmarked_s1) == 0)
	                        {
								// s2 is now offset THIS far from s1
	                            offset2 = offset2+i;

								// Our longeset Common String just got bigger
								lcs = lcs + 1;

								// Now that we match again, break to the main loop
	                            break;
	                        }
                    }

					//This is the number of inserted characters were found
					int added_offset1 = offset1 - old_offset1;
					int added_offset2 = offset2 - old_offset2;

					
					// We reached our maxoffset and couldn't match up the strings
					if(added_offset1 == 0 && added_offset2 == 0)
						{
							// was: _s1.append(h1 + left(_s1_deviation,added_offset1+1) + h2);
							// was: _s2.append(h1 + left(_s2_deviation,added_offset2+1) + h2);
                            _s1 = _s1 + h1 + _s1_deviation.Substring(0, added_offset1 + 1) + h2;
                            _s2 = _s2 + h1 + _s2_deviation.Substring(0, added_offset2 + 1) + h2;	
                    }

					// s2 had extra characters
					else if(added_offset1 == 0 && added_offset2 > 0)
                    {
                            // was: _s1.append(left(_s1_deviation,1));
                            // was: _s2.append(h1 + left(_s2_deviation,added_offset2) + h2 + right(_s2_deviation,1));
                        _s1 = _s1 + _s1_deviation.Substring(0, 1);
                        _s2 = _s2 + h1 + _s2_deviation.Substring(0, added_offset2) + h2 + _s2_deviation.Substring(_s2_deviation.Length - 1, 1); // ?? Length -1

                    }

					// s1 had extra characters
					else if(added_offset1 > 0 && added_offset2 == 0)
						{
                            // was: _s1.append(h1 + left(_s1_deviation,added_offset1) + h2 + right(_s1_deviation,1));
                            // was: _s2.append(left(_s2_deviation,1));
                            _s1 = _s1 + h1 + _s1_deviation.Substring(0, added_offset1) + h2 + _s1_deviation.Substring(_s1_deviation.Length - 1, 1);
                            _s2 = _s2 + _s2_deviation.Substring(0, 1);
                        }
                }
                c++;
            // was: c=c+1;	
        }

		// Anything left at the end of s1 is extra

		if(c + offset1 < s1.Length)
			{
				// was: _s1.append(h1 + right(s1,s1.Length-(c + offset1)) + h2);
                _s1 = _s1 + h1 + s1.Substring(s1.Length - 1, s1.Length - (c + offset1)) + h2;
            }

		// Anything left at the end of s2 is extra
		if(c + offset2 < s2.Length)
			{
				// was: _s2.append(h1 + right(s2,s2.Length-(c + offset2)) + h2);
                _s2 = _s2 + h1 + s2.Substring(s2.Length - 1, s2.Length - (c + offset2)) + h2;
            }

		// Distance is the average string length minus the longest common string
		int distance = (s1.Length + s2.Length)/2 - lcs;

		// Which string was longest?
		// was: int maxLen = iif(s1.Length > s2.Length,de(s1.Length),de(s2.Length));
        int maxLen; 
        if(s1.Length > s2.Length) maxLen = s1.Length;
        else maxLen = s2.Length;

		// Similarity is the distance divided by the max length
        // was: similarity = iif(maxLen eq 0,1,1-(distance/maxLen));
		float similarity; 
        if(maxLen == 0) similarity =1;
        else similarity = 1-(distance/maxLen);

		// Return what we found.
		return_struct_lcs = lcs;
		return_struct_similarity = similarity;
		return_struct_distance = distance;
		return_struct_s1 = _s1; // "highlighted" version
		return_struct_s2 = _s2; // "highlighted" version

        //return return_struct;
    }

@Valeriy: Sorry, I'm not much of a Cguru, but one thing to keep in mind is that ColdFusion uses 1-based arrays instead of 0-based arrays. In other words, an array with only 1 item in it is accessed as myArray[1].

Lol! The original code was C#. You are converting something back. Although it would make an interesting analysis of how Cto CF to Cchanges code.

Wonderful. Thanks!