algorithm - 如何实现 "trending counter"用滑动窗口来统计单词数？

Question

我有多个进程来计算单词数。例如，我有多个 kafka 消费者，消费单个 kafka 主题的不同分区。该主题的每条消息都是一个单词(字符串)。这个词既是我的卡夫卡主题的关键又是值(value)。消费者将消费一条消息并将该单词的计数器增加 1。

我希望能够查询过去5分钟内最流行的10个单词。一旦某个单词不再出现在当前窗口中，我就不想对其进行计数。假设我们使用处理时间作为时间戳。

最好的方法是什么？

与语言无关

Answer 1

RedisBloom 有一个 Top-K 解决方案，可能适合您的用例，以防您的流有大量不同的单词需要计数。

在 this blog post (对我来说:)你可以看到 Top-K 在执行时间和内存需求方面都优于排序集。在我的 benchamrk 中，对于 k=10，内存消耗小于 10kb，而排序集的内存消耗约为 6mb。数据集是《 war 与和平》一书，总共有约 500,000 个单词，大约 41,000 个不同的单词。

我的建议是保留几个 Top-K key 并在 5 分钟后停用它们。键的数量取决于您想要的分辨率。

Top-K 的另一个不错的功能是，您可以在元素被从 Top-K 列表中驱逐时获取它们。这使您可以跟踪趋势。此功能不适用于排序集。