Is it possible to make Levenshtein distance in Excel without having to resort to macros?

Question

Let me explain.

I need to make a fuzzy comparison for the company, so in the bank I use the levenshtein distance calculator, and then I calculate the percentage ratio between the two terms. If the conditions are more than 80% similar, Fuzzymatch returns "TRUE".

My problem is that I am on an internship and will leave soon. People who will continue to do this do not know how to use excel with macros and want me to implement what I have done as much as possible.

So my question is: how inefficient is the function, is there any way to make a standard function in Excel that will calculate what I did before without resorting to macros?

Thanks.

Answer 1

While it cannot be executed in one formula for any lines with a reasonable size, you can only use formulas to calculate the Levenshtein distance between lines using a worksheet.

Here is an example that can handle strings up to 15 characters long; it could be easily expanded for more:

https://docs.google.com/spreadsheet/ccc?key=0AkZy12yffb5YdFNybkNJaE5hTG9VYkNpdW5ZOWowSFE&usp=sharing

This is impractical for nothing but ad-hoc comparisons, but it does a decent job of showing how the algorithm works.

Answer 2

If you came to this googling something like levenshtein distance google sheets

I threw it along with a comment from milot-midia code on this value ( https://gist.github.com/andrei-m/982927 - code under the MIT license)

• From the sheets in the header menu Tools → Script Editor
• Name the project
  • The name of the function (not the project) will allow you to use func
• Paste the following code

 function Levenshtein(a, b) { if(a.length == 0) return b.length; if(b.length == 0) return a.length; // swap to save some memory O(min(a,b)) instead of O(a) if(a.length > b.length) { var tmp = a; a = b; b = tmp; } var row = []; // init the row for(var i = 0; i <= a.length; i++){ row[i] = i; } // fill in the rest for(var i = 1; i <= b.length; i++){ var prev = i; for(var j = 1; j <= a.length; j++){ var val; if(b.charAt(i-1) == a.charAt(j-1)){ val = row[j-1]; // match } else { val = Math.min(row[j-1] + 1, // substitution prev + 1, // insertion row[j] + 1); // deletion } row[j - 1] = prev; prev = val; } row[a.length] = prev; } return row[a.length]; } 

You can run it from a spreadsheet using

=Levenshtein(cell_1,cell_2)

Answer 3

looking at the previous answers to calculating the Levenshtein distance, I think it would be impossible to create it as a formula.

Take a look at the code here