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

本文关键字:结果 方法 不能 levenshteinstance | 更新日期: 2023-09-27 18:06:47

我有一个文件与"X"数的名称,我需要匹配每个这些名称对另一个文件,看看是否说的名字是其中,但以不同的方式写("Verizon" -> "Verizon LTD")。

我是用visual studio 2008上的"模糊查找"互操作来做这个的,并且得到了一个很好的结果。

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

我使用的代码如下:

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 ->这是我的代码带来的。

如果我能得到关于这个主题的任何输入,我会非常感激,我很难让这个应用程序达到与"模糊查找"相同的结果。

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

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

从结果来看,微软的模糊搜索结果并不像1 - EditDistance / WordLength那么简单。"ILCA INC"answers"ICE INC"的编辑距离为2,即一次插入和一次替换。这比微软的模糊查找返回的更好的结果更少的编辑。

虽然模糊查找可能使用编辑距离作为其方程的部分,但我认为确定匹配分数的总体方法是专有的,本质上是算法和启发式的。您可能已经知道,Fuzzy Lookup会优先考虑从0开始的子字符串匹配的单词,而不是编辑距离较低的单词。

编写一个调试例程来转储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个错别字(将A省略了L和E),我的分数是。75,我不知道你是怎么得到。77的。

我敢打赌,微软的算法是不同的计算分数。它可能取两个长度的最小值或平均值,而不是像您那样取最大值。

用Levenshtein等算法计算"正确率百分比"是一个难题。正如您在示例中看到的那样,短字符串比较会产生百分比的剧烈波动,并且使用适用于较长比较的阈值并不适用于较短比较(反之亦然)。

阈值增加:无论输入字符串的长度如何,当前的决策逻辑都使用恒定值。然而,有时使用'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输入参数。