Search Smith

ColdFusion, SQL queries, and, of course, searching

Levenshtein Distance in ColdFusion

Posted by David Faber on March 14, 2013

It’s been a good long time since I’ve posted here — to be honest, apart from personal and family issues (new baby, moving, etc.) which took away a good chunk of the time that I had formerly set aside for blogging, there just haven’t been any “blog-worthy” technical issues that have come up.

We were tasked with the following: Given a particular document, search Solr with using the original document’s keywords to find unique related documents of another type. The related documents are already indexed, so it practically writes itself, right?

In the course of developing a solution for this, we discovered that the related documents had been copied many times, so we would need to filter for uniqueness (these are not large records to string comparison is not terribly expensive). However, and this is the kicker, not only had they been copied, but also their wording slightly tweaked — and these tweaks could be found anywhere in the copied document. It would not be as easy as comparing the first 100 characters, or even the first 30 characters; the changes could be found literally anywhere, but to the human eye the copied document would look practically identical to its source. For various reasons, we did not want to display these (yes, SEO was one of our concerns).

A quick Google search led me to the Levenshtein distance, or edit distance, between two strings. Further searching also turned up a couple of ColdFusion solutions: one given by Brad Wood (with whose blogging I had previously been unfamiliar) and another (CFLib) cited by Ray Camden. I am not at all eager to copy large blocks of code or to rely on external CF libraries (my first attempt at using such a library, CFSolr, turned out poorly — but that’s a topic for another time), and continued searching. It turns out that there is a method for computing the Levenshtein distance between two strings in the Apache Commons Java library — specifically, the StringUtils object in the Commons Lang library. This library appears to be available in ColdFusion 9 by default (perhaps because of its inclusion of Apache Solr?); I could not say whether it is also available in any other version of ColdFusion (7, 8, or even 10). However loading an external Java library into ColdFusion for usage by developers is not difficult, and in this case I think it is worth it.

Step 1: Create a StringUtils object

<cfset string_utils_obj = createObject("java", "org.apache.commons.lang.StringUtils") />

That’s all! There isn’t really a step 2. 😉

More seriously, step 2 in our case involved executing a Solr query via <CFHTTP>, looping over the results, comparing each result’s Levenshtein “ratio” (the ratio of the result’s Levenshtein distance to the length of the larger of the two compared strings) against all previous unique results, and storing the result if its minimum ratio was 25% or greater (lower = less difference).

Step 2

<cfloop array="#result_array#" index="current_result">
    <cfset min_levenshtein_ratio = 1 />
    <cfloop array="#doc_array#" index="current_doc">
        <cfset temp_levenshtein_distance = string_utils_obj.getLevenshteinDistance(the_result, current_doc) />

        <!--- Levenshtein ratio = Levenshtein distance / max(length of strings compared) --->
        <cfset temp_levenstein_ratio = temp_levenshtein_distance / max( len(the_result), len(current_doc) ) />
        <cfif temp_levenstein_ratio LT min_levenshtein_ratio>
            <cfset min_levenshtein_ratio = temp_levenstein_ratio />
        </cfif>
        <cfif min_levenshtein_ratio LT 0.25>
            <cfbreak />
        </cfif>
    </cfloop>
    <cfif min_levenshtein_ratio LT 0.25>
        <cfcontinue />
    </cfif>
    <!--- This is a unique result, let's save it! --->
    <cfset arrayAppend(doc_array, the_result) />
</cfloop>

Leave a Comment

Your email address will not be published. Required fields are marked *