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