我有一组相当大的字符串(比如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距离,但我无法看到如何在这里很好地使用它,而不必将每个字符串与列表中的每个字符串进行比较,然后以某种方式决定两个字符串是否在同一组中的差异阈值。
另一种方法是将字符串散列到整数的算法,其中类似的字符串散列到在数字行上靠近的整数。我不知道什么算法,但如果有的话,甚至存在
有没有人有任何想法/指针?
UPDATE: @Will答:也许名字是因为我首先想到的不是很好的例子。作为一个起点,我认为我可以假设在我将要使用的数据中,字符串的小改动不会使它从一个组跳到另一个组。
你怎么想你的算法,以应对串序列,其中每一个都是有用与前一个非常微妙的不同,但第一个与上一个非常不同? – Eric 2010-07-25 13:16:23
好问题。作为一个起点,我并不太在意,因为我期望字符串组在我所期望的数据中有相当不同的地方。 我还应该补充一点,对于列表中的每个实体,我将至少有一个其他维(它已经是数字)来帮助进行分组,所以字符串比较部分不必是100%完美的。 – latentflip 2010-07-25 13:21:16