35x Improved T-SQL LevenShtein Distance Algorithm...at a cost
At work, we noticed a considerable performance hit using a T-SQL implementation of the Levenshtein algorithm created by Michael Gilleland found here . It seems to me that his approach was to replicate the C-code algorithm found in Wikipedia in T-SQL rather than taking a step back and re-conceptualizing the algorithm from a T-SQL standpoint. Feel free to correct me, but it see ms that the algorithm focues on three things to find the shortest distance between two strings (what it takes to make them the same): How many character insertions are necessary How many character deletions are necessary How many character substitutions are necessary These three traits are necessary to accommodate mis-aligned strings because of typos. If the algorithm is not designed with these constraints, one missing letter will result in inaccurate reporting because it throws the indexing off. The C-code example in Wikipedia uses a 2-D matrix approach, which is a natural, compact, and performant fit for ...