Levenshtein距离。最大距离例外

Question

我有这个levenshtein算法：

public static int? GetLevenshteinDistance(string input, string output, int maxDistance)
        {
            var stringOne = String.Empty;
            var stringTwo = String.Empty;

            if (input.Length >= output.Length)
            {
                stringOne = input;
                stringTwo = output;
            }
            else
            {
                stringOne = output;
                stringTwo = input;
            }

            var stringOneLength = stringOne.Length;
            var stringTwoLength = stringTwo.Length;

            var matrix = new int[stringOneLength + 1, stringTwoLength + 1];

            for (var i = 0; i <= stringOneLength; matrix[i, 0] = i++) { }
            for (var j = 0; j <= stringTwoLength; matrix[0, j] = j++) { }

            for (var i = 1; i <= stringOneLength; i++)
            {
                bool isBreak = true;

                for (var j = 1; j <= stringTwoLength; j++)
                {
                    var cost = (stringTwo[j - 1] == stringOne[i - 1]) ? 0 : 1;

                    matrix[i, j] = Math.Min(
                        Math.Min(matrix[i - 1, j] + 1, matrix[i, j - 1] + 1),
                        matrix[i - 1, j - 1] + cost);

                    if (matrix[i, j] < maxDistance)
                    {
                        isBreak = false;
                    }
                }

                if (isBreak)
                {
                    return null;
                }
            }

            return matrix[stringOneLength, stringTwoLength];
        }

我检查了每个值，如果它>最大距离我打破了。但它并不总是正常工作。

例如：

string1 = "#rewRPAF"
string2 = "#rewQVRZP"
maxDistance = 4

我得到值5，但不要为空。

这个解决方案我得到了这个 - Levenstein distance limit

Answer 1

我们不会在这里修复代码，但我会帮你修复它。

改变这个

            if (matrix[i, j] < maxDistance)
            {
                isBreak = false;
            }

至

            if (matrix[i, j] < maxDistance)
            {
                isBreak = false;
            } else {
                System.Diagnostics.Debugger.Break();
            }

当你到达maxDistance时，它会破坏调试器，当调试器中的这一步发生时，并按照你的程序执行。这应该可以让你看到你不想要的东西。

Answer 2

看看内循环第一次发生了什么。此时费用不能超过一。因此，如果MaxDistance大于1，则IsBreak始终设置为false。

我的直觉说：

废弃与IsBreak有关的一切

int Distance = matrix[stringOneLength, stringTwoLength];
return Distance > MaxDistance ? null : Distance;

但我没试过。

或者（我对Levenshtein做得不够，对这种方法充满信心）：

废弃与IsBreak有关的一切

if (matrix[i, j] < maxDistance)
    {
        isBreak = false;
    }

变

if (matrix[i, j] > maxDistance)
    {
        return null;
    }

（请注意，您的终止测试有一个一个一个。）