Newest functions Upload a function Leave a tip My account

There are 2,521 functions in this library.

Levenshtein ( str1 ; str2 ; damerau ; caseSensitive )

Finds the Levenshtein or Damerau-Levenshtein distance between two strings.

  Average rating: 3.5 (72 votes) Log in to vote

Steve Allen Richard Carlton Consulting, Inc. http://www.rcconsulting.com

  Function definition: (Copy & paste into FileMaker's Edit Custom Function window)

/** * Levenshtein ( str1 ; str2 ; damerau ; caseSensitive ) * * by Steve Allen; Lead Engineer; Richard Carlton Consulting, Inc. * P: (707) 422-4053 * E: info@rcconsulting.com * * @version 1.0 * * @requirements * * function: Levenshtein_Array_Load ( lenStr1 ; lenStr2 ; i ; j ; pad ) * http://www.briandunning.com/cf/963 * * function: Levenshtein_Array_Process ( str1 ; str2 ; lenStr1 ; lenStr2 ; i ; j ; caseSensitive ; damerau ; pad ) * http://www.briandunning.com/cf/964 * * function: Levenshtein_Array_Clean ( lenStr1 ; lenStr2 ; i ; j ; pad ) * http://www.briandunning.com/cf/962 * * @description * * Finds the Levenshtein or Damerau-Levenshtein distance between two strings, as described at: * * http://en.wikipedia.org/wiki/Levenshtein_distance * http://en.wikipedia.org/wiki/Damerau–Levenshtein_distance * * (both pages accessed January 29, 2009 at 4:00 p.m.) * * @param string str1 * * First string to compare * * @param string str2 * * Second string to compare * * @param Boolean damerau * * True to return Damerau-Levenshtein distance. * False to return Levenshtein distance * * @param Boolean caseSensitive * * True to compare the strings on a Case Sensitive basis * False to compare the strings regardless of case. * * i.e. the Case Sensitive distance between "Steve" and "steve" is 1, whereas * the Case Insenseitive distance between "Steve" and "steve" is 0. * * @result number * * Returns the Distance requested, as a number. * * @notes * * 1. The "pad" var being set in the second line is to allow for longer strings. * The way the algorithm works, I needed a 2-dimensional array. * I chose to implement this in FM using the repetitions of a global variable. * These are, unfortunately, one-dimensional. So I made the array two dimensional by the * using the concatenation (&) of the two individual dimensional coordinates <as a number>. * * For example, array coordinate (3, 5) becomes variable repetition number 35, or $$_ld_array[35]. * * However, you may notice that I run out of storage space very quickly: I start running into myself * with numbers over 10. I.e. - (11, 1) is the same result (111) as (1, 11). * * No padding only allows for strings where Length ( string ) <= 10. * * So I added padding to the numbers, so that now my concatenation of the * above-mentioned coordinate yields "003005", which, when gotten as a number and used as the * repetition number, yields $$_ld_array[3005]. * * So it is evident that each "0" in the padding adds 2 powers of 10 to the maximum possible * string parameter length (1 for each coordinate). In other words, with padding the new * Maximum String Length is 10^(Length ( pad ) * 2). That means that my default * Maximum String length (for 3 "0"'s) is 10^(6), or 1,000,000 (0-999,999). * * That should be plenty. :) * * 2. This custom function cleans up after itself, too. :) * * 3. There appears to have been (at the time of this writing, a typographical error in the psuedocode * on the Wikipedia page for the Damerau-Levenshtein distance, line 9. This conclustion is based on * the same (functionally) line (actually line 7) in the Levenshtein page's psuedocode. * * The Damerau-Levenshtein page says, "for j from 1 to lenStr2", whereas the Levenshtein page * says, "for j from 0 to n". * * It does not appear from my tests that this affects anything. However, just to be on the safe side, * I implemented the calculation to feed "1" to the Levenshtein_Array_Load() sub-function if the user has * asked for the Damerau-Levenshtein distance, and "0" if not. * * This was easily accomplished, since FileMaker views False as 0 (and vice versa), * and True as 1 (and vice versa). :) * * 4. Careful examination of the Wikipedia article for the Damerau-Levenshtein algorithm (and of the results * of this calculation!) will reveal that the algorithm as it currently stands only accounts "properly" * for transpositions of <obligatory adjacent> characters. * In other words, in order to only count as one edit, a transposition must be of two characters that * are <next to each other>. * * For example: "Steve" and "Stvee" (transposing the first "e" with the "v") gives an edit distance of * 1 in the Damerau-Levenshtein function, whereas "Steve" and "Svete" (transposition of the "t" and the "v") * gives an edit distance of 2 (substitute "t" for "v", substitute "v" for "t"). * * This is, naturally, a failing of the Damerau-Levenshtein function. I am working on improving this function * to include <all> transposition as one edit, hopefully for inclusion in v2.0. */ Let ([ pad = "000" ; str1 = Case ( caseSensitive ; str1 ; Lower ( str1 ) ) ; str2 = Case ( caseSensitive ; str2 ; Lower ( str2 ) ) ; lenPad = Length ( pad ) ; lenStr1 = Length ( str1 ) ; lenStr2 = Length ( str2 ) ; loadArray = Levenshtein_Array_Load ( lenStr1 ; lenStr2 ; 0 ; damerau ; pad ) ; processArray = Levenshtein_Array_Process ( str1 ; str2 ; lenStr1 ; lenStr2 ; 1 ; 1 ; caseSensitive ; damerau ; pad ) ; finalCell = GetAsNumber ( Right ( pad & lenStr1 ; lenPad ) & Right ( pad & lenStr2 ; lenPad ) ) ; levDist = $$_ld_array[finalCell] ; cleanArray = Levenshtein_Array_Clean ( lenStr1 ; lenStr2 ; 0 ; 0 ; pad ) ]; levDist ) Click to copy

Finds the Levenshtein or Damerau-Levenshtein distance between two strings, as described at:

http://en.wikipedia.org/wiki/Levenshtein_distance

http://en.wikipedia.org/wiki/Damerau–Levenshtein_distance

(both pages accessed January 29, 2009 at 4:00 p.m.)

Note: best viewed in a large text space, or at least without word wrap, for formatting reasons.

 

Comments

Log in to post comments.

 

Note: these functions are not guaranteed or supported by BrianDunning.com. Please contact the individual developer with any questions or problems.

Support this website.

This library has been a free commmunity resource for FileMaker users and developers for 20 years. It receives no funding and has no advertisements. If it has helped you out, I'd really appreciate it if you could contribute whatever you think it's worth: