8

我有以下两个字符串：

String A: Manchester United
String B: Manchester Utd

两个字符串的含义相同，但包含不同的值。

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

在我提供 2 个字符串后，是否有任何简单的算法可以返回“匹配分数”？

4

6 回答 6

9

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

于 2012-05-08T09:25:18.837 回答
6

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

我将它用于 SQL Server UDF，该 UDF 用于超过一百万行的查询（以及最多 6 或 7 个单词的文本）。

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

请记住，Levenshtein 给出了差异，您必须将其转换为“相似性指数”。我使用了距离除以最长单词的长度之类的东西（但有一些变化）

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

您还必须考虑：

  • 如果两个输入中的单词数必须相同，或者可以更改
  • 如果两个输入的顺序必须相同，或者它可以改变。

根据这一点，算法会发生变化。例如，如果字数不同，应用第一条规则非常快。而且，第二条规则减少了比较的次数，特别是在比较文本中有很多单词的情况下。稍后将通过示例进行解释。

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

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

样品比较：相同的顺序

在这个例子中，它使用了不同数量的单词：

  • 将“曼联”与“曼彻斯特联队”进行比较

如果保证两个输入中的单词顺序相同，则应比较这些对：

Manchester United
Manchester Utd    FC

(Manchester,Manchester) (Utd,United) (FC: 未比较)

Manchester     United
Manchester Utd FC

(Manchester,Manchester) (Utd: 未比较) (United,FC)

           Machester United
Manchester Utd       FC

（曼彻斯特：未比较）（Manchester,Utd）（United,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

等等。看图片

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

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

达到最小相似性时停止比较：根据您想要执行的操作，您可以设置一个阈值，当达到该阈值时，停止对的比较。

如果你不能设置一个阈值，至少你可以在每对单词的相似度达到 100% 的情况下停下来。这样可以节省大量时间。

在某些情况下，如果相似度至少达到 75%，您可以简单地决定停止比较。如果您想向用户显示与用户提供的字符串相似的所有字符串，则可以使用此选项。

示例：与单词顺序变化的比较

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

第四条规则：标准化

您还必须在比较之前对单词进行规范化，如下所示：

  • 如果不区分大小写，则将所有单词转换为大写或小写
  • 如果不区分重音，请删除所有单词中的重音
  • 如果你知道有常用的缩写，你也可以将它们规范化，为缩写加速（即转换united to utd，not utd to united）

缓存优化

为了优化该过程，我缓存了我可以缓存的任何一个，即不同大小的比较向量，例如 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 距离的实现，因为你可以很容易地发现它在不同的语言上实现

于 2012-05-08T11:14:01.920 回答
5

看看这篇文章，它解释了如何做到这一点并提供了示例代码:)

模糊匹配（Levenshtein 距离）

更新：

这是以两个字符串为参数并计算两个字符串的“Levenshtein Distance”的方法代码

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];
    }
于 2012-05-08T09:26:21.877 回答
1

有时检测重复项可能比计算 Levenshtein 实例复杂“一点”。考虑以下示例：

1. Jeff, Lynch, Maverick, Road, 181, Woodstock  
2. Jeff, Alf., Lynch, Maverick, Rd, Woodstock, NY

这种重复可以通过复杂的聚类算法进行匹配。

有关更多信息，您可能需要查看一些研究论文，例如“Effective Incremental Clustering for Duplicate Detection in Large Databases”。

（示例来自论文）

于 2012-05-08T10:10:47.640 回答
1

您正在寻找的是字符串相似性度量。有多种方法可以做到这一点：

  1. 编辑两个字符串之间的距离（如答案＃1）
  2. 将字符串转换为字符集（通常在二元组或单词上），然后计算两组的布鲁斯系数或骰子系数。
  3. 将字符串投影到词向量（单词或二元组）并计算两个向量之间的余弦距离。

我通常发现选项 #2 是最容易实现的，如果您的字符串是短语，那么您可以简单地在单词边界上对它们进行标记。在上述所有情况下，您可能需要先删除停用词（常用词，如 and、a、the 等），然后再进行标记。 更新：链接

骰子系数

余弦相似度

在 C# 中实现朴素相似度引擎*警告：不要脸的自我提升

于 2012-05-08T09:51:28.900 回答
0

这是使用 Levenshtein 距离算法的替代方法。这根据 Dice 系数比较字符串，它比较每个字符串中常见字母对的数量以生成 0 和 1 之间的值，0 表示不相似，1 表示完全相似

    public static double CompareStrings(string strA, string strB)
    {
        List<string> setA = new List<string>();
        List<string> setB = new List<string>();

        for (int i = 0; i < strA.Length - 1; ++i)
            setA.Add(strA.Substring(i, 2));

        for (int i = 0; i < strB.Length - 1; ++i)
            setB.Add(strB.Substring(i, 2));

        var intersection = setA.Intersect(setB, StringComparer.InvariantCultureIgnoreCase);

        return (2.0 * intersection.Count()) / (setA.Count + setB.Count);
    }

像这样调用方法：

CompareStrings("Manchester United", "Manchester Utd");

输出是：0.75862068965517238

于 2017-08-11T19:04:09.217 回答