创建关键字过滤器的最快方法？

Question

我正在试着根据关键词过滤来过滤推文。过滤器可以有10个或更多的单词。因此，如果tweet包含关键字，则该tweet通过。我唯一能想到的就是将tweet的文本分割成标记。然后，我将遍历过滤器中的单词，并将每个标记与过滤器中的每个单词进行比较。然而，这种方式似乎非常慢。假设关键字过滤器有N个关键字，令牌数为M，则需要O(N*M)。

有没有更好的方法？

Answer 1

我想解决这个问题的一种方法是创建一个HashSet，并将推文的所有文本标记都放入其中。然后，我将遍历单词filter中的单词，并检查它们是否都在HashSet中

Answer 2

如果您有足够的时间进行预处理，您可以建立一个索引:所有tweet中包含的所有单词的列表(在某种易于搜索的数据结构中，如树或哈希表)。每个单词都有包含该单词的tweet的ids。

然后，您可以在索引中查找关键字并计算ID的交集。

这种技术称为inverted index。

Answer 3

在HashMap中搜索或多或少是O(1)，因此如果您将密钥存储在HashMap中(例如)，您将只需要检查M次，因此它将是O(M)。