performance - 查找文本是否包含列表中的任何单词。哪个更快，为什么？

Question

可能有更好的解决方案，但我首先想到的两个是：

1) 对于列表中的每个单词，检查文本是否包含该单词 2) 将单词存储在集合中。将单词（用空格分隔的任何内容 - 不必太准确）从另一个集合中的文本存储并检查 2 个集合的交集是否为空

我不知道哪个会更好，或者它们是否差不多。

Answer 1

这就是集合匹配问题。

让S一组模式、T你的文本和nS 中的元素数量在 T 中找到。然后你可以在时间 O(|T| + |S| + n) [*]中找到文本中 S 中所有元素的出现使用Aho–Corasick 字符串匹配算法。

鉴于您只想找到第一次出现，在最坏的情况下，执行时间会减少到 O(|T| + |S|)，如果 S 足够小，那么它在文本长度上是线性的！

[*] |S| 是集合中所有单词的长度

Answer 2

从其中一个集合中创建一个trie，并在其中查找第二个集合的每个单词。考虑到字符串的平均长度为k，trie 构造需要Θ(n*k)时间，并且检查字符串是否属于 trie 需要O(k)。
为简单起见，您可以将运行时间视为O((n+m)*k)。然而，更精确的分析给出了Θ(n*k) + O(n*k)，因为您实际上可以在扫描整个第二组之前很久就完成。这表明最好从较小的集合构建特里树并从较大的集合中查找元素。

Answer 3

n Java、Python 和 C++ 最复杂的实现不使用单一算法进行此类搜索。

使用哪种算法的决定将取决于文本大小、搜索频率、单词分布等。（多种算法也可以一起使用）

如果文本很大，并且您只需要在文本中搜索几个单词，则大多数实现都使用 Boyer-Moore 或 Rabin-Karp 算法的扩展版本。

像 Rabin-Karp 这样的算法，例如搜索一个哈希匹配，如果找到它而不是搜索整个单词，具有良好的滚动哈希函数，它很少发生，

与您的第一个建议相比，存储一组文本单词似乎是一个更好的解决方案，尽管存储单词的哈希值可能是更好的解决方案（哈希值和真实单词之间的附加映射）。

如果您的文本具有很高的独特性，它将无法保持集合。你有更多你所建议的解决方案，我建议你使用谷歌。