在一大组字符串中查找类似字符串的组
我有一个相当大的一组字符串（比如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距离，但我无法看到如何在这里使用它，而不必将每个字符串与列表中的每个字符串进行比较，然后以某种方式决定差异决定两个字符串是否在同一组中的阈值。
另一种方法是将字符串散列为整数的算法，其中类似的字符串散列为数字行上相近的整数。 即使存在，我也不知道会是什么算法
有人有任何想法/指针吗？
更新：@愿意A：或许名字并不是我第一次想到的那么好的例子。 作为一个起点，我认为我可以假设在我将要使用的数据中，字符串的小改动不会使它从一个组跳到另一个组。
另一个流行的方法是通过Jaccard索引关联字符串。 从http://en.wikipedia.org/wiki/Jaccard_index开始。
这里有一篇关于使用Jaccard-index（和其他一些方法）来解决像你这样的问题的文章：
http://matpalm.com/resemblance/
您试图解决的问题是典型的集群问题。
从简单的K-Means算法开始，并使用Levenshtein距离作为计算元素和聚类中心之间距离的函数。
BTW，Levenshtein距离计算算法在Apache Commons StringUtils中实现 - StringUtils.getLevenshteinDistance
K-Means的主要问题是你应该指定簇的数量（在你的术语中是子组）。 因此，您将有两种选择：用一些euristic改进K-Means，或者使用另一种不需要指定簇编号的簇化算法（但该算法可能会表现出更差的性能，并且如果您决定实施该算法会非常困难你自己）。
如果我们正在谈论实际的代名词，比较他们的metaphone（的开始）可能会有所帮助：
MRFLPRBRTS: Mr Philip Roberts
FLRBRTS: Phil Roberts
FLPRBRTS: Philip Roberts
FMKBR: Foo McBar
TFTJNS: David Jones
TFJNS: Dave Jones
TFJNS: Davey Jones
JNT: Jane Doe
JNSM0: John Smith
JNSM0: Jonny Smith
上一篇: Finding groups of similar strings in a large set of strings
下一篇: Efficiently estimating the number of unique elements in a large list