How Can We Efficiently Calculate the Damerau-Levenshtein Distance Between Two Strings?

Efficiently calculate string distance similarity

In applications such as spell checking and text analysis, it is often necessary to calculate the distance similarity between two strings. The Damerau-Levenshtein algorithm is a commonly used method that measures the number of modifications required to transform one string into another.

High performance code implementation

In order to optimize performance, we adopt an improved Damerau-Levenshtein algorithm implementation. It contains the following performance-enhancing technologies:

1. Convert strings to arrays of code points to speed up comparisons.
2. Using the short-circuit mechanism, the calculation will be terminated if the distance exceeds the specified threshold.
3. Use three rotated arrays instead of matrices to optimize array slicing operations for short strings.

Sample code

The following code demonstrates an improved Damerau-Levenshtein algorithm that performs much faster than existing implementations:

public static int DamerauLevenshteinDistance(int[] source, int[] target, int threshold)
{
    // ... 代码略 ...

    //// 旋转数组
    dSwap = dMinus2;
    dMinus2 = dMinus1;
    dMinus1 = dCurrent;
    dCurrent = dSwap;

    int jm1 = 0, im1 = 0, im2 = -1;

    for (int j = 1; j  1 && j > 1 && source[im2] == target[jm1] && source[im1] == target[j - 2])
                min = Math.Min(min, dMinus2[im2] + cost);

            dCurrent[i] = min;
            if (min  threshold) { return int.MaxValue; }
    }

    int result = dCurrent[maxi];
    return (result > threshold) ? int.MaxValue : result;
}

Performance Considerations

The performance enhancements implemented in the above code result in significant speed improvements:

• About 10 times faster than the C# example on Wikipedia (even without the maximum distance limit).
• When providing the maximum distance, the performance advantage can be increased to 30 times to 100 times.

The above is the detailed content of How Can We Efficiently Calculate the Damerau-Levenshtein Distance Between Two Strings?. For more information, please follow other related articles on the PHP Chinese website!