-1

我刚刚开始编程，我正在尝试 Levenshtein 距离是如何工作的。

我正在比较用户数据库中两个帐户名之间的相似程度。

我正在使用来自 wiki 的 c# 代码，它提供了一个数字，用于定义源字符串最终作为目标字符串需要多少操作（插入/删除/替换）。但是，我想要的是 2 个字符串的匹配/不匹配百分比，而不是数字。

我该怎么做？

public static int DamerauLevenshteinDistance(string source, string target)
{
    if (String.IsNullOrEmpty(source))
    {
        if (String.IsNullOrEmpty(target))
        {
            return 0;
        }
        else
        {
            return target.Length;
        }
    }
    else if (String.IsNullOrEmpty(target))
    {
        return source.Length;
    }

    var score = new int[source.Length + 2, target.Length + 2];

    var INF = source.Length + target.Length;
    score[0, 0] = INF;
    for (var i = 0; i <= source.Length; i++) { score[i + 1, 1] = i; score[i + 1, 0] = INF; }
    for (var j = 0; j <= target.Length; j++) { score[1, j + 1] = j; score[0, j + 1] = INF; }

    var sd = new SortedDictionary<char, int>();
    foreach (var letter in (source + target))
    {
        if (!sd.ContainsKey(letter))
            sd.Add(letter, 0);
    }

    for (var i = 1; i <= source.Length; i++)
    {
        var DB = 0;
        for (var j = 1; j <= target.Length; j++)
        {
            var i1 = sd[target[j - 1]];
            var j1 = DB;

            if (source[i - 1] == target[j - 1])
            {
                score[i + 1, j + 1] = score[i, j];
                DB = j;
            }
            else
            {
                score[i + 1, j + 1] = Math.Min(score[i, j], Math.Min(score[i + 1, j], score[i, j + 1])) + 1;
            }

            score[i + 1, j + 1] = Math.Min(score[i + 1, j + 1], score[i1, j1] + (i - i1 - 1) + 1 + (j - j1 - 1));
        }

        sd[source[i - 1]] = i;
    }

    return score[source.Length + 1, target.Length + 1];
}
4

1 回答 1

2

Levenshtein 距离（正如 Wikipedia 很乐意告诉您的那样）是将一个字符串更改为另一个字符串所需的最小单字符更改（插入、修改或删除）次数。您可以使用它来确定两个字符串的相似程度，因为相似的字符串将具有较低的 Levenshtein 距离。

两个不相似的字符串之间的最大可能的 Levenshtein 距离是两个字符串中较长的字符串的长度：

int maxLD = Math.Max(s1.Length, s2.Length);

鉴于此，您可以通过计算实际距离来计算相似度：

int actualLD = LevenshteinDistance(s1, s3);
float LDratio = 1 - (float)actualLD / maxLD;

相同的字符串将LDratio等于 1。非常相似的字符串将具有较高的LDratio值，而非常不同的字符串将具有LDratio接近 0 的值。

乘以 100 以获得您的百分比匹配。

于 2013-10-17T07:27:31.560 回答