我需要计算两个字符串之间的相似度。那么我到底是什么意思呢？让我用一个例子来解释:

• 真实的词:医院
• 错误的词:haspita

现在我的目标是确定需要修改多少个字符才能获得真正的单词。在这个例子中，我需要修改 2 个字母。那么百分比是多少？我总是把真实的词的长度。所以它变成 2/8 = 25% 所以这 2 个给定的字符串 DSM 是 75%。

如何在性能成为关键考虑因素的情况下实现这一目标？

最佳答案

几周前我刚刚解决了这个完全相同的问题。既然现在有人问，我会分享代码。在我详尽的测试中，即使没有提供最大距离，我的代码也比维基百科上的 C# 示例快 10 倍。当提供最大距离时，此性能增益增加到 30x - 100x +。请注意性能的几个关键点:

• 如果您需要反复比较相同的单词，请先将单词转换为整数数组。 Damerau-Levenshtein 算法包括许多 >、<、== 比较，并且="">ints 比较比 chars 快得多。
• 它包括一个短路机制，如果距离超过规定的最大值则退出
• 使用一组旋转的三个数组，而不是像我在其他地方看到的所有实现中那样使用巨大的矩阵
• 确保您的数组切片横跨较短的字宽。

代码(如果您在参数声明中将 int[] 替换为 String，它的工作原理完全相同:

/// <summary>
/// Computes the Damerau-Levenshtein Distance between two strings, represented as arrays of
/// integers, where each integer represents the code point of a character in the source string.
/// Includes an optional threshhold which can be used to indicate the maximum allowable distance.
/// </summary>
/// <param name="source">An array of the code points of the first string</param>
/// <param name="target">An array of the code points of the second string</param>
/// <param name="threshold">Maximum allowable distance</param>
/// <returns>Int.MaxValue if threshhold exceeded; otherwise the Damerau-Leveshteim distance between the strings</returns>
public static int DamerauLevenshteinDistance(int[] source, int[] target, int threshold) {

    int length1 = source.Length;
    int length2 = target.Length;

    // Return trivial case - difference in string lengths exceeds threshhold
    if (Math.Abs(length1 - length2) > threshold) { return int.MaxValue; }

    // Ensure arrays [i] / length1 use shorter length 
    if (length1 > length2) {
        Swap(ref target, ref source);
        Swap(ref length1, ref length2);
    }

    int maxi = length1;
    int maxj = length2;

    int[] dCurrent = new int[maxi + 1];
    int[] dMinus1 = new int[maxi + 1];
    int[] dMinus2 = new int[maxi + 1];
    int[] dSwap;

    for (int i = 0; i <= maxi; i++) { dCurrent[i] = i; }

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

    for (int j = 1; j <= maxj; j++) {

        // Rotate
        dSwap = dMinus2;
        dMinus2 = dMinus1;
        dMinus1 = dCurrent;
        dCurrent = dSwap;

        // Initialize
        int minDistance = int.MaxValue;
        dCurrent[0] = j;
        im1 = 0;
        im2 = -1;

        for (int i = 1; i <= maxi; i++) {

            int cost = source[im1] == target[jm1] ? 0 : 1;

            int del = dCurrent[im1] + 1;
            int ins = dMinus1[i] + 1;
            int sub = dMinus1[im1] + cost;

            //Fastest execution for min value of 3 integers
            int min = (del > ins) ? (ins > sub ? sub : ins) : (del > sub ? sub : del);

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

            dCurrent[i] = min;
            if (min < minDistance) { minDistance = min; }
            im1++;
            im2++;
        }
        jm1++;
        if (minDistance > threshold) { return int.MaxValue; }
    }

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

Swap 是:

static void Swap<T>(ref T arg1,ref T arg2) {
    T temp = arg1;
    arg1 = arg2;
    arg2 = temp;
}

关于c# - 如何计算给定 2 个字符串的距离相似性度量？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9453731/