我有一组相当大的字符串(比如 100 个)，其中有许多以相似性为特征的子组。我正在尝试寻找/设计一种能够相当有效地找到这些组的算法。
例如，假设输入列表在下方左侧，输出组在右侧。
Input Output
----------------- -----------------
Jane Doe Mr Philip Roberts
Mr Philip Roberts Phil Roberts
Foo McBar Philip Roberts
David Jones
Phil Roberts Foo McBar
Davey Jones =>
John Smith David Jones
Philip Roberts Dave Jones
Dave Jones Davey Jones
Jonny Smith
Jane Doe
John Smith
Jonny Smith
有人知道有什么方法可以合理有效地解决这个问题吗？
查找相似字符串的标准方法似乎是 Levenshtein 距离，但我看不出如何在这里充分利用它，而不必将每个字符串与列表中的每个其他字符串进行比较，然后以某种方式决定在决定两个字符串是否在同一组中的差异阈值上。
另一种方法是将字符串散列为整数的算法，其中相似的字符串散列为在数字行上靠在一起的整数。我不知道那会是什么算法，如果存在的话
有没有人有任何想法/指示？
更新: @Will A:也许名字并不像我最初想的那么好。作为起点，我认为我可以假设在我将要处理的数据中，字符串中的微小变化不会使其从一组跳到另一组。
最佳答案
另一种流行的方法是通过 Jaccard 索引关联字符串。从 http://en.wikipedia.org/wiki/Jaccard_index 开始.
这是一篇关于使用 Jaccard-index(以及其他几种方法)解决像您这样的问题的文章:
关于algorithm - 在大量字符串中查找相似字符串组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3329297/