根据字母查找相似词的算法

Question

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

我正在研究哈希函数，尤其是 Rabin-Karp 算法，以在较大的字符串中找到相似的词。

但它不适用于我想要的情况：在我的案例中，我认为 "similar" 的单词的三个示例基于德国银行：有 "Deutsche Bank"、"Postbank" 和 "Landesbank"。这三个人的名字中都有 "bank" 这个词，但只有德意志银行将它作为一个单独的词。所以基本上是根据单词的共享字符来衡量单词的相似度。我认为应该有一个限制，如果可能的话，应该只考虑 >=4 个字符的相似性。

如果我只是在寻找 "bank" 这个词，我会硬编码一些东西。但是我正在寻找一种方法来找到这样的相似 names/strings 而一开始就不知道它。

Answer 1

如果我错了请纠正我。根据您的问题，我了解到您需要找到所有具有某些共同点的字符串。

我们能否找到所有字符串之间的公共子字符串。根据 Substring 的长度，我们可以给出一个分数。根据阈值，您可以决定字符串是否属于同一组。

Answer 2

为了比较任何 2 个给定的字符串，我们可以根据每个子字符串的长度超过我们的阈值得出一个数字来表示匹配的好坏。

将给定的字符串与所有其他字符串进行比较并找到具有最高匹配数的字符串会给我们最多 "similar" 个字符串。

我的方法假定子字符串匹配是有序的。如果子字符串的顺序无关紧要，这将不起作用，例如如果 abcdXXefgh 应该与 abcdYYefgh 和 efghYYabcd 同样相似。尽管可以通过最后检查 c 的值并从那里计算匹配数来修改它。

如果您想考虑字符串的长度或其他因素，可以稍微调整一下。

我们可以使用类似于 Levenshtein distance.

中使用的动态规划方法的方法

The distance of all possible prefixes might be stored in an array d[][] where d[i][j] is the distance between the first i characters of string s and the first j characters of string t.

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

那么任何给定的单元格值 [i,j] 将是以下最大值：

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

伪代码：

set each cell in c and d to 0

threshold = 4     // shortest possible substring to consider

for j = 1 to n
for 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])               // substitution

return d[m, n]

您需要弄清楚您希望如何计算任何给定子字符串的成本 (calculateSubstringCost)。

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

您还可以优化它只需要 2 行，方法是让另一个数组跟踪当前子字符串匹配之前的成本，这导致我们最多只需要向后查看 1 行（参见 above link 例如）。

Answer 3

获取一个嵌入模型（有经过训练的 word2vec 或 glove），它可以为您提供单词语义的密集向量表示。

然后您可以通过嵌入向量表示通过单词之间的余弦距离轻松找到语义相似度。与通常提出的信息检索技术（如 levenshtein 或公共子串/单词重叠）相比，此处的重大改进在于它实际上是基于这些单词的抽象上下文的相似性。因此，Postbank 将非常接近 Barclays 或 HSBC，因为它是一家银行公司，而不仅仅是共享子字符串。

相反，一旦通过嵌入获得了单词的向量，就可以使用任何聚类算法来查找具有语义相似性的单词集群，即使不知道描述该集群的特定分类法确实存在。

Answer 4

听起来像是 Levenshtein 距离的一个很好的用例。简而言之，这会计算从一个字符串转到另一个字符串所需的 "edits" 数。您也可以通过在模型中添加发生编辑的概率来变得更好，但这可能不是必需的。通常我发现 2 次编辑限制对基本的拼写更正有好处。

维基页面：Levenshtein Distance

根据字母查找相似词的算法

Algorithm that finds similar words based on their letters

algorithm

machine-learning

data-mining