在一大组string中查找类似的string组

我有一个相当大的string集合（比如说100），它有许多以相似性为特征的小组。 我试图find/devise一个能够合理高效地find这些组的algorithm。

举个例子，假设input列表在左边，输出组在右边。

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 

有谁知道有什么办法来合理有效地解决这个问题？

find相似的string的标准方法似乎是Levenshtein距离，但我不明白如何在这里使用它，而不必将每个string与列表中的每个string进行比较，然后以某种方式决定差异决定两个string是否在同一组中的阈值。

另一种方法是将string散列到一个整数的algorithm，其中相似的string散列到在数字行上靠近的整数。 我不知道什么algorithm，即使有，即使存在

有人有任何想法/指针吗？

---

更新：@威尔 – 答：也许名字是不是我第一次想到的例子。 作为一个起点，我认为我可以假定在我将要处理的数据中，string的小改动不会使它从一个组跳到另一个组。

Answer 1

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

这里有一篇关于使用Jaccard-index（和其他一些方法）来解决像你这样的问题的文章：

http://matpalm.com/resemblance/

Answer 2

您试图解决的问题是典型的集群化问题。

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

BTW，Levenshtein距离计算algorithm在Apache Commons中实现StringUtils – StringUtils.getLevenshteinDistance

K-Means的主要问题是你应该指定簇的数量（在你的术语中是子组）。 所以，你可以有两个select：用一些euristic改进K-Means，或者使用另一个不需要指定簇编号的分簇algorithm（但是如果你决定实现它，那么algorithm可能会performance出更差的性能，你自己）。

Answer 3

如果我们正在谈论实际的代名词 ，比较（他们的） 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 

Answer 4

对于你给的例子，我认为Levenshtein距离是不合适的，因为“Bonny Smith”与“Jonny Smith”非常相似，几乎肯定会被同一个class级所考虑。

我认为你需要从某些具有同义词的名称（如“John”，“Jon”，“Jonny”，“Johnny”等）的angular度来处理这个（如果使用名字）并且基于这些。

Answer 5

我已经解决了这样的问题，首先我规范化了文本，然后从整个string中取出string，比如InC。 美国…

这个不值得的单词必须由你定义。

规范化之后，我使用Jaro Winkler距离进行名称检查，然后使用类似对象的列表摸索结果。

这真的很好。

我在java中运行了这个3万个人的名字

我希望这个想法对某个人有用

Answer 6

这里是一个Levenshtein函数的SQL代码：

 CREATE FUNCTION [Levenshtein](@str_1 nvarchar(4000), @str_2 nvarchar(4000)) RETURNS int AS BEGIN DECLARE @str_1_len int , @str_2_len int , @str_1_itr int , @str_2_itr int , @str_1_char nchar , @Levenshtein int , @LD_temp int , @cv0 varbinary(8000) , @cv1 varbinary(8000) SELECT @str_1_len = LEN(@str_1) , @str_2_len = LEN(@str_2) , @cv1 = 0x0000 , @str_2_itr = 1 , @str_1_itr = 1 , @Levenshtein = 0 WHILE @str_2_itr <= @str_2_len SELECT @cv1 = @cv1 + CAST(@str_2_itr AS binary(2)) , @str_2_itr = @str_2_itr + 1 WHILE @str_1_itr <= @str_1_len BEGIN SELECT @str_1_char = SUBSTRING(@str_1, @str_1_itr, 1) , @Levenshtein = @str_1_itr , @cv0 = CAST(@str_1_itr AS binary(2)) , @str_2_itr = 1 WHILE @str_2_itr <= @str_2_len BEGIN SET @Levenshtein = @Levenshtein + 1 SET @LD_temp = CAST(SUBSTRING(@cv1, @str_2_itr+@str_2_itr-1, 2) AS int) + CASE WHEN @str_1_char = SUBSTRING(@str_2, @str_2_itr, 1) THEN 0 ELSE 1 END IF @Levenshtein > @LD_temp SET @Levenshtein = @LD_temp SET @LD_temp = CAST(SUBSTRING(@cv1, @str_2_itr+@str_2_itr+1, 2) AS int)+1 IF @Levenshtein > @LD_temp SET @Levenshtein = @LD_temp SELECT @cv0 = @cv0 + CAST(@Levenshtein AS binary(2)), @str_2_itr = @str_2_itr + 1 END SELECT @cv1 = @cv0, @str_1_itr = @str_1_itr + 1 END RETURN @Levenshtein END