在一大组字符串中查找类似字符串的组

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/

Answer 2

您尝试解决的问题是典型的群集问题.

从简单的K-Means算法开始,并使用Levenshtein距离作为计算元素和聚类中心之间距离的函数.

BTW,Levenshtein距离计算算法在Apache Commons StringUtils中实现 - StringUtils.getLevenshteinDistance

K-Means的主要问题是你应该指定集群的数量(你的术语中的子集).因此,您将有两个选择:使用一些euristic改进K-Means或使用另一个不需要指定簇编号的聚类算法(但该算法可能会显示更差的性能,如果您决定实施它可能非常难以实现你自己).