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

我有一组相当大的字符串（比如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答：也许名字是因为我首先想到的不是很好的例子。作为一个起点，我认为我可以假设在我将要使用的数据中，字符串的小改动不会使它从一个组跳到另一个组。

来源

2010-07-25 latentflip

你怎么想你的算法，以应对串序列，其中每一个都是有用与前一个非常微妙的不同，但第一个与上一个非常不同？ – Eric 2010-07-25 13:16:23

好问题。作为一个起点，我并不太在意，因为我期望字符串组在我所期望的数据中有相当不同的地方。我还应该补充一点，对于列表中的每个实体，我将至少有一个其他维（它已经是数字）来帮助进行分组，所以字符串比较部分不必是100％完美的。 – latentflip 2010-07-25 13:21:16

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

这里有一个关于使用杰卡德指数（和一对夫妇的其他方法）来解决你们这样一个问题的文章：

http://matpalm.com/resemblance/

来源

2010-07-25 13:24:55

仅当您将字符串视为一组字词时（即字词的顺序及其基数都不重要）。如果顺序很重要，Levenshtein距离（如罗马提到的）更精确（尽管计算速度较慢）。 – 2010-07-25 16:07:02

您试图解决的问题是典型的clusterization问题。

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

BTW，算法Levenshtein距离计算在Apache的百科全书StringUtils的实现 - StringUtils.getLevenshteinDistance

K均值的主要问题是，你应该指定集群（亚组在术语）的数量。因此，您将有两种选择：用一些euristic改进K-Means，或者使用另一种不需要指定簇编号的簇化算法（但该算法可能会表现出更差的性能，并且如果您决定实施该算法会非常困难你自己）。

来源

2010-07-25 13:20:20 Roman

我知道“分组”并不完全是我正在尝试做的事。这些链接也非常有用。谢谢！ – latentflip 2010-07-25 13:34:00

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

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

来源

2010-07-25 13:21:01

William - > Bill ...如果这是一个现实世界的问题，那么它的解决方案根本就不是微不足道的，并且需要一些已经在语言学方面进行的研究，并且可能已经填充了DB。 – Roman 2010-07-25 13:28:19

如果我们谈论的实际pronouncable的话，比较（开始的），他们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

来源

2010-07-25 13:37:06 Wrikken

-2

这里是一个莱文斯坦功能的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, @[email protected]_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, @[email protected]_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

来源

2016-02-03 04:52:59 user1884677

我已经解决了这样的问题，首先我规范化了文本，然后从整个字符串中取出字符串，比如InC。 OF USA ...

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

正常化后，我使用Jaro Winkler距离按名称执行检查，然后使用类似对象列表在对象中摸索结果。

这真的很好。

我在30K的人的名字跑这在java中

我希望这个想法是要有人

来源

2016-09-01 23:14:53 Sibok666

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

回答

相关问题