Levenshtein Distance speedup

Oct 21, 2015 at 10:41 AM
I've implemented this library to sort and filter a search, however searches for more than 5 character took multiple seconds.
As most of the algorithms used here rely on the levenshtein distance I've replaced the given implementation with the reduced memory useage version from here: https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#C.23

(Just replace the contents of the function, everything works fine then)

With this implementation the search returns instantly.
public int LevenshteinDistance(string source, string target){
    if(String.IsNullOrEmpty(source)){
        if(String.IsNullOrEmpty(target)) return 0;
        return target.Length;
    }
    if(String.IsNullOrEmpty(target)) return source.Length;

    if(source.Length > target.Length){
        var temp = target;
        target = source;
        source = temp;
    }
 
    var m = target.Length;
    var n = source.Length;
    var distance = new int[2, m + 1];
    // Initialize the distance 'matrix'
    for(var j = 1; j <= m; j++) distance[0, j] = j;

    var currentRow = 0;
    for(var i = 1; i <= n; ++i){
        currentRow = i & 1;
        distance[currentRow, 0] = i;
        var previousRow = currentRow ^ 1;
        for(var j = 1; j <= m; j++){
            var cost = (target[j - 1] == source[i - 1] ? 0 : 1);
            distance[currentRow, j] = Math.Min(Math.Min(
                        distance[previousRow, j] + 1,
                        distance[currentRow, j - 1] + 1),
                        distance[previousRow, j - 1] + cost);
        }
    }
    return distance[currentRow, m];
}