我正在寻找一种基于共享字母来检测单词（文本字符串）相似性的方法。

我研究了哈希函数，特别是拉宾-卡普算法，以在较大的字符串中查找相似的单词。

但这并不适用于我想要的情况：基于德国银行的三个例子，我认为“相似”的单词有：有“德意志银行”、“邮政银行”和“州立银行”。这三个名字中都包含“银行”这个词，但只有德意志银行是以独立的词形式出现的。因此，基本上有必要基于共享字符来衡量单词的相似性。我认为应该设定一个限制，只考虑长度大于或等于4个字符的相似性，如果可能的话。

如果我只是在寻找“银行”这个词，我会硬编码一些东西。但我正在寻找一种方法，能够在事先不知道的情况下找到这样的相似名称/字符串。

回答：

为了比较任意两个给定的字符串，我们可以根据超过阈值的每个子字符串的长度，计算出一个数字来表示匹配的程度。

将给定的字符串与所有其他字符串进行比较，并找出匹配数最高的那些字符串，就能得到最“相似”的字符串。

我的方法假设子字符串匹配是按顺序进行的。如果子字符串的顺序不重要，例如，如果abcdXXefgh应该与abcdYYefgh和efghYYabcd同样相似，那么这种方法就不适用。尽管可以通过最后检查c的值，并从那里计算匹配数来进行修改。

如果您想考虑字符串的长度或其他因素，可以对其进行一些调整。

我们可以使用一种类似于用于Levenshtein距离的动态编程方法的方法。

所有可能的前缀的距离可能会存储在一个数组d[][]中，其中d[i][j]是字符串s的前i个字符和字符串t的前j个字符之间的距离。

我们可以有一个额外的数组c，它跟踪当前子字符串匹配的长度。

然后，任何给定的单元格值[i,j]将是以下各项的最大值：

• 当前子字符串匹配之前的成本（d[i-length,j-length]）加上当前匹配的成本（如果length < threshold，则为0，其中length = c[i,j]）
• 如Levenshtein距离中定义的：（值直接复制，这些操作没有成本）
  • 插入（d[i, j-1]）
  • 删除（d[i-1, j]）
  • 替换（相同或不同字符）（d[i-1, j-1]）

此方法的伪代码如下：

set each cell in c and d to 0threshold = 4     // shortest possible substring to considerfor j = 1 to nfor i = 1 to m   currentSubstringCost = 0   if s[i] == t[j]     // there's a matching substring      c[i, j] = c[i-1, j-1]      if c[i, j] >= threshold          currentSubstringCost = d[i - c[i, j], j - c[i, j]]                                 + calculateSubstringCost(c[i, j])   d[i, j] = maximum(currentSubstringCost,      // substring match                     d[i-1, j],                 // deletion                     d[i, j-1],                 // insertion                     d[i-1, j-1])               // substitutionreturn d[m, n]

您需要确定如何计算任何给定子字符串的成本（calculateSubstringCost）。

一个简单的方法是取子字符串长度的平方，因此长度为4的子字符串的成本将是16，而长度为6的子字符串的成本将是36。

您还可以优化这一点，只需要两行，通过另一个数组来跟踪当前子字符串匹配之前的成本，这样我们最多只需要向后查看一行（参见上述链接的示例）。