需要帮助了解列文施泰因距离

本文关键字：施泰因 距离 了解 帮助 | 更新日期: 2023-09-27 18:35:53

我刚刚开始编程，我正在尝试Levenshtein距离的工作原理。

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

我正在使用来自 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];
}

需要帮助了解列文施泰因距离

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

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

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

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

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

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

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

相关文章：