比较2个字符串

Question

我有以下2个字符串:

String A: Manchester United
String B: Manchester Utd

两个字符串表示相同,但​​包含不同的值.

如何比较这些字符串以获得"匹配分数",在这种情况下,第一个单词相似,"曼彻斯特",第二个单词包含相似的字母,但不在正确的位置.

在提供2个字符串后,是否有任何简单的算法返回"匹配分数"？

Answer 1

您可以计算两个字符串之间的Levenshtein距离,如果它小于某个值(您必须定义),您可能会认为它们非常接近.

Answer 2

我需要做这样的事情并使用Levenshtein距离.

我将它用于SQL Server UDF,它用于具有超过一百万行的查询(以及最多6或7个字的文本).

我发现如果你分别比较每个单词,算法运行得更快,"相似性指数"更精确.即,您将每个输入字符串拆分为单词,并将一个输入字符串的每个单词与另一个输入字符串的每个单词进行比较.

请记住,Levenshtein给出了差异,你必须将其转换为"相似性指数".我使用的东西比如距离除以最长单词的长度(但有一些变化)

第一条规则:单词的顺序和数量

你还必须考虑:

• 如果两个输入中的单词数量必须相同,或者可以更改
• 如果两个输入的订单必须相同,或者它可以改变.

根据此,算法会发生变化.例如,如果单词的数量不同,则应用第一个规则非常快.并且,第二条规则减少了比较次数,特别是如果比较文本中有许多单词.稍后将通过示例进行解释.

第二条规则:加权每个比较对的相似性

我还将较长的单词加权比较短的单词加权以获得全局相似性指数.我的算法采用比较对中两个单词中最长的一个,并且对于具有较长单词的对而言赋予较高权重而对于具有较短单词的对具有较高权重,尽管与对长度不完全成比例.

样本比较:相同的顺序

使用此示例,它使用不同数量的单词:

• 比较"曼联"和"曼联Utd FC"

如果两个输入中的单词顺序相同,则应比较这些对:

Manchester United
Manchester Utd    FC

(曼彻斯特,曼彻斯特)(联合国,联合国)(FC:未比较)

Manchester     United
Manchester Utd FC

(曼彻斯特,曼彻斯特)(联队:未比较)(曼联,FC)

           Machester United
Manchester Utd       FC

(Mancheter:未比较)(曼彻斯特,联队)(联队,FC)

显然,最高分将是第一组对.

履行

比较相同顺序的单词.

具有较高字数的字符串是固定向量,在该示例中显示为A,B,C,D,E.其中v [0]是单词A,v [1]是单词B,依此类推.

对于具有较少字数的字符串,我们需要创建可与第一组进行比较的所有可能的索引组合.在这种情况下,具有较少字数的字符串由a,b,c表示.

您可以使用一个简单的循环来创建表示要进行比较的对的所有向量,如此

A,B,C,D,E   A,B,C,D,E   A,B,C,D,E   A,B,C,D,E   A,B,C,D,E   A,B,C,D,E
a,b,c       a,b,  c     a,b,    c   a,  b,c     a,  b,  c   a,    b,c
0 1 2       0 1   3     0 1     4   0   2 3     0   2   4   0     3 4

A,B,C,D,E   A,B,C,D,E   A,B,C,D,E   A,B,C,D,E
  a,b,c       a,b,  c     a,  b,c       a,b,c
  1 2 3       1 2   4     1   3 4       2 3 4

样本中的数字是具有第一组单词的索引的向量,其必须与第一组中的索引一起被映射.即v [0] = 0,表示将短集合(a)的索引0与长集合(A)的索引0进行比较,v [1] = 2表示将短(b)集的索引1与索引2进行比较长集(C),等等.

要计算此向量,只需从0,1,2开始.向右移动可以移动的最新索引,直到无法再移动它为止:

Strat移动最后一个:

0,1,2 -> 0,1,3 -> 0,1,4 
No more moves possible, move the previous index, and restore the others
to the lowest possible values (move 1 to 2, restore 4 to 3)

当最后一个不能再移动时,移动最后一个,并将最后一个重置到最近的可能位置(1移到2,4移到3):

0,2,3 -> 0,2,4
No more moves possible of the last, move the one before the last

再次移动前一个.

0,3,4
No more moves possible of the last, move the one before the last
Not possible, move the one before the one before the last, and reset the others:

移动前一个:

1,2,3 -> 1,2,4

等等.看图

当您拥有所有可能的组合时,您可以比较定义的对.

第三条规则:停止比较的最小相似度

达到最小相似度时停止比较:取决于您想要做什么,您可以设置一个当达到时,停止比较对的thresold.

如果你不能设置一个thresold,至少你可以随时停止,如果你对每对单词100%相似.这样可以节省大量时间.

在某些情况下,如果相似性至少为75%,您可以简单地决定停止比较.如果要向用户显示与用户提供的字符串类似的所有字符串,则可以使用此选项.

示例:与单词顺序的变化进行比较

如果顺序可能有变化,则需要将第一组中的每个单词与第二组中的每个单词进行比较,并对结果组合取最高分,其中包括所有最短对中的所有单词.与第二对的不同单词相比,可能的方式.为此,您可以填充(n X m)个矩阵的上三角或下三角,然后从矩阵中获取所需的元素.

第四条规则:正常化

您还必须在比较之前对单词进行标准化,如下所示:

• 如果不区分大小写,则将所有单词转换为大写或小写
• 如果不是重音敏感,请删除所有单词中的重音
• 如果你知道有通常的缩写,你也可以将它们标准化,缩写以加速它(即将联合转换为联合国,而不是联合国转换为联合)

缓存优化

为了优化程序,我尽可能地缓存,即不同大小的比较向量,如A中的向量0,1,2-0,1,3,-0,1,4-0,2,3 ,B,C,D,E到a,b,c比较例:长度为3,5的所有比较将在首次使用时计算,并在所有3个字到5个字的传入比较中再循环.

其他算法

我尝试了汉明距离,结果不太准确.

你可以做更复杂的事情如语义比较,语音比较,考虑到某些字母是一样的(如b和v,几种语言,如西班牙语,其中疗法是没有区别).其中一些很容易实现,而另一些则非常困难.

注意:我没有包括Levenhstein距离的实现,因为你可以很容易地找到它在不同的laguages上实现

Answer 3

看一下这篇文章,它解释了如何做到这一点并给出了示例代码:)

模糊匹配(Levenshtein距离)

更新:

这是方法代码,它将两个字符串作为参数并计算两个字符串的"Levenshtein距离"

public static int Compute(string s, string t)
    {
    int n = s.Length;
    int m = t.Length;
    int[,] d = new int[n + 1, m + 1];

    // Step 1
    if (n == 0)
    {
        return m;
    }

    if (m == 0)
    {
        return n;
    }

    // Step 2
    for (int i = 0; i <= n; d[i, 0] = i++)
    {
    }

    for (int j = 0; j <= m; d[0, j] = j++)
    {
    }

    // Step 3
    for (int i = 1; i <= n; i++)
    {
        //Step 4
        for (int j = 1; j <= m; j++)
        {
        // Step 5
        int cost = (t[j - 1] == s[i - 1]) ? 0 : 1;

        // Step 6
        d[i, j] = Math.Min(
            Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
            d[i - 1, j - 1] + cost);
        }
    }
    // Step 7
    return d[n, m];
    }