java中的高效字符串匹配

我有一串句子（推文）和超过1000万个名字。我想确定一个句子（tweet）是否包含提及1000万个名字中的一个。我可以为所有可能的模式编译正则表达式，但我真的很想知道是否有一个有效的算法来做到这一点。java中的高效字符串匹配

谢谢，

2012-09-22 DotNet

你是什么意思：1000万个正则表达式，还是一个正则表达式，所有千万个名字一起变成了一个交替？无论哪种方式，听起来都比应该允许的人更有趣。 ;）但严重的是，这不是一个正则表达式的工作。 –

2012-09-22 16:21:49 ruakh

谢谢，看着它。 – DotNet

您可以尝试使用Bloom filter。 Demo here。

2012-09-22 16:26:30 mindas

谢谢。这很有趣。 Bloom fliter可能会有所帮助。我现在会尝试。 – DotNet

我不认为你需要模式匹配，如果你只是寻求一个简单的字符串（名称）的发生。如果你实际上是在瞄准叽叽喳喳的名字 - 当他们在推文中提到时，他们是不是以@符号作为前缀的？如果是这样，首先寻找@符号并从那里继续。

要检查@之后的字符串是否是您的1,000万字符串中的一个，则ruakh提出的前缀树绝对是一个好主意。

2012-09-22 16:31:15 Ridcully

谢谢。它们并不总是以@作为前缀。有些品牌不是。 – DotNet

你可以从相反的方向去解决它。随着句子的进入，将其分成令牌并为每个令牌构建RegEx模式，如^ 令牌 \ s *。比较每一个与你的1000万个名字中的每一个，假设每个名字在线。

2012-09-22 16:31:24 milam

谢谢，但这涉及到分句，以检测给予数百万句子相当昂贵的名词。我希望我能正确理解你的建议。 – DotNet

回答