java - java中的高效字符串匹配

Question

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

谢谢，

Answer 1

您可以构建一个 trie（前缀树）。

Answer 2

您可以尝试使用Bloom filter。演示在这里。

Answer 3

如果您只寻找简单字符串（名称）的出现，我认为您根本不需要模式匹配。如果您实际上是针对推特名称 - 在推文中提及它们时，它们不是以@符号为前缀吗？如果是这样，首先只需寻找 @ 符号并从那里继续。

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

Answer 4

你可以从相反的方向着手。当句子进入时，将其拆分为标记并为每个标记构建一个正则表达式模式，例如 ^标记\s*。假设每一个都在线，将它们与你的 1000 万个名字进行比较。