FileMaker Pro Custom Functions

/** * 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 )
 Then copy & paste into FileMaker Advanced's Edit Custom Function window.