c# - Damerau - Levenshtein 距离，添加一个阈值

Question

我有以下实现，但我想添加一个阈值，所以如果结果要大于它，就停止计算并返回。

我该怎么做？

编辑:这是我当前的代码，threshold 尚未使用...目标是使用它

    public static int DamerauLevenshteinDistance(string string1, string string2, int threshold)
    {
        // Return trivial case - where they are equal
        if (string1.Equals(string2))
            return 0;

        // Return trivial case - where one is empty
        if (String.IsNullOrEmpty(string1) || String.IsNullOrEmpty(string2))
            return (string1 ?? "").Length + (string2 ?? "").Length;


        // Ensure string2 (inner cycle) is longer
        if (string1.Length > string2.Length)
        {
            var tmp = string1;
            string1 = string2;
            string2 = tmp;
        }

        // Return trivial case - where string1 is contained within string2
        if (string2.Contains(string1))
            return string2.Length - string1.Length;

        var length1 = string1.Length;
        var length2 = string2.Length;

        var d = new int[length1 + 1, length2 + 1];

        for (var i = 0; i <= d.GetUpperBound(0); i++)
            d[i, 0] = i;

        for (var i = 0; i <= d.GetUpperBound(1); i++)
            d[0, i] = i;

        for (var i = 1; i <= d.GetUpperBound(0); i++)
        {
            for (var j = 1; j <= d.GetUpperBound(1); j++)
            {
                var cost = string1[i - 1] == string2[j - 1] ? 0 : 1;

                var del = d[i - 1, j] + 1;
                var ins = d[i, j - 1] + 1;
                var sub = d[i - 1, j - 1] + cost;

                d[i, j] = Math.Min(del, Math.Min(ins, sub));

                if (i > 1 && j > 1 && string1[i - 1] == string2[j - 2] && string1[i - 2] == string2[j - 1])
                    d[i, j] = Math.Min(d[i, j], d[i - 2, j - 2] + cost);
            }
        }

        return d[d.GetUpperBound(0), d.GetUpperBound(1)];
    }
}

Answer 1

这是关于你的回答:Damerau - Levenshtein Distance, adding a threshold(抱歉不能发表评论，因为我还没有 50 个代表)

我认为你在这里犯了一个错误。你初始化了:

var minDistance = threshold;

你的更新规则是:

if (d[i, j] < minDistance)
   minDistance = d[i, j];

此外，您的提前退出标准是:

if (minDistance > threshold)
   return int.MaxValue;

现在，观察上面的 if 条件永远不会成立!您应该将 minDistance 初始化为 int.MaxValue