algorithm - 在大量字符串中查找相似字符串组

Question

我有一组相当大的字符串(比如 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:也许名字并不像我最初想的那么好。作为起点，我认为我可以假设在我将要处理的数据中，字符串中的微小变化不会使其从一组跳到另一组。

Answer 1

另一种流行的方法是通过 Jaccard 索引关联字符串。从 http://en.wikipedia.org/wiki/Jaccard_index 开始.

这是一篇关于使用 Jaccard-index(以及其他几种方法)解决像您这样的问题的文章:

http://matpalm.com/resemblance/