LevenshteinDistance方法不能提供最准确的结果

Question

我有一个名称为"X“的文件，我需要将这些名称中的每一个与另一个文件进行匹配，看看该名称是否在其中，但以不同的方式写入( "Verizon”->“Verizon ltd.”)。

我在visual Studio2008上使用了一个“模糊查找”互操作来做这件事，并且得到了很好的结果。

现在，我正在尝试实现LevenshteinDistance方法来实现此结果，以便该方法对具有完整列表的其他文件迭代我需要的名称，并返回得分/相同概率最高的名称。

我使用的代码如下：

public static int LevenshteinDistance(string src, string dest)
{
    int[,] d = new int[src.Length + 1, dest.Length + 1];
    int i, j, cost;

    for (i = 0; i <= src.Length; i++)
    {
        d[i, 0] = i;
    }
    for (j = 0; j <= dest.Length; j++)
    {
        d[0, j] = j;
    }


    for (i = 1; i <= src.Length; i++)
    {
        for (j = 1; j <= dest.Length; j++)
        {

            if (src[i - 1] == dest[j - 1])
                cost = 0;
            else
                cost = 1;

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

        }
    }

    return d[src.Length, dest.Length];
}

public static List<string> Search(string word, List<string> wordList, double fuzzyness)
{
    List<string> foundWords = new List<string>();

    foreach (string s in wordList)
    {
        // Calculate the Levenshtein-distance:
        int levenshteinDistance =
            LevenshteinDistance(word.ToUpper(), s.ToUpper());

        // Length of the longer string:
        int length = Math.Max(word.Length, s.Length);

        // Calculate the score:
        double score = 1.0 - (double)levenshteinDistance / length;

        // Match?
        if (score >= fuzzyness)
        {
            foundWords.Add(s);
        }
    }
    return foundWords;
}

下面的例子是我运行的一个测试，其中我们想要匹配的单词是"ILCA INC"，我们按如下方式运行它：

相似性集：>= 0.77

搜索单词列表"ILCA“0.5 aprox -->这是我们用VS2008”模糊查找“得到的结果。"ICE INC“0.77 aprox -->这是我的代码带来的。

如果我能在这个主题上得到任何输入，我会非常高兴，因为我很难让这个应用程序达到和“模糊查找”相同的结果。

如果我可以提供更多的信息，或者如果我的问题表达错了，请告诉我。

Answer 1

根据搜索结果，微软的模糊搜索结果并不像1 - EditDistance / WordLength那么简单。"ILCA INC“和"ICE INC”之间的编辑距离是2 --一次插入和一次替换。这比Microsoft的Fuzzy Lookup返回的更好的结果要少一些。

虽然模糊查找可能使用编辑距离作为其等式的一部分，但我假设确定匹配分数的整体方法是专有的，本质上是算法和启发式的。正如您可能知道的，Fuzzy Lookup将子字符串匹配从0开始的单词优先于编辑距离较小的单词。

Answer 2

可以非常方便地编写一个调试例程来转储d数组的内容，这样您就可以确保它正常工作。例如，对于您提到的比较：

    I C E   I N C
  0 1 2 3 4 5 6 7
I 1 0 1 2 3 4 5 6
L 2 1 1 2 3 4 5 6
C 3 2 1 2 3 4 5 5
A 4 3 2 2 3 4 5 6
  5 4 3 3 2 3 4 5
I 6 5 4 4 3 2 3 4
N 7 6 5 5 4 3 2 3
C 8 7 6 6 5 4 3 2

正如另一个帖子提到的，距离2是正确的，在你的比较中有2个打字错误(去掉了L和E代表A)。我得到的分数是.75，我不知道你怎么得到.77的。

我敢打赌，微软的算法正在以不同的方式计算分数。它可能是取两个长度中的最小值或平均值，而不是像您所做的那样取最大值。

使用Levenshtein等算法计算“正确百分比”是一个困难的问题。正如您在示例中所看到的，短字符串比较收益率在百分比中的剧烈波动，而使用阈值进行较长的比较并不适用于较短的字符串(反之亦然)。

Threshold Ramp:您当前的决策逻辑使用一个常量值，而不考虑输入字符串的长度。但是，有时使用'ramp‘更实用，其中over/under值随字符串长度而变化。例如，您可能决定三个字符以下的字符串必须完全匹配(100%)，四个字符串必须匹配70%以上，五个字符字符串的匹配率为75%，六个字符的匹配率为80%，依此类推。在某个时刻(大约8-10个字符之后)，您通常可以坚持使用单个值。

使用int[]查找表，实现相当简单：

double[] thresholds=new double[] {100, 100, 100, 70, 75, 80, (etc) };
double targetThreshold=thresholds[Math.Max(src.Length,dest.Length)-1];

...

if (score >= targetThreshold)
  foundWords.Add(s);

(使用适合您需要的阈值)。它通常会提供更实际的结果。

这种技术的缺点是，如果您想要一个真正可变的阈值百分比，则很难编写代码。正如您在我的示例中看到的，我忽略了fuzzyness输入参数。