获取最频繁的项目，而不计算每个项目

Question

我想知道是否有一种算法可以计算“最频繁的项目”，而不必保留每个项目的计数？例如，假设我是一个搜索引擎，想要跟踪10个最受欢迎的搜索。我不想做的是为每个查询保留一个计数器，因为可能有太多的查询让我无法计数(而且大多数查询都是单例查询)。有没有简单的算法来解决这个问题？也许是一些概率上的东西？谢谢!

Answer 1

好吧，如果你有非常多的查询(就像搜索引擎可能会做的那样)，那么你可以对查询进行“采样”。因此，你可能每秒收到1000个查询，但如果你只是保持每秒一个的计数，那么在较长的一段时间内，你会得到一个相对接近“真正”答案的答案。

例如，这就是“采样”分析器的工作方式。每隔n毫秒，它会查看当前正在执行的函数。经过很长一段时间(几秒钟)，您会对“昂贵”函数有一个很好的了解，因为它们是在您的示例中出现频率更高的函数。

你仍然需要做“计数”，但通过周期性采样，你可以得到实际需要存储的数据量的上限，而不是计算每个查询的上限(例如，每秒最多一个查询，等等)。

Answer 2

如果您希望在任何给定时间进行最频繁的搜索，则不需要使用无尽的计数器来跟踪每个提交的查询。相反，您需要一种算法来衡量任何给定查询的提交数量除以一段时间。这是一个非常简单的算法。提交给搜索引擎的任何搜索，例如单词“cache”，都会存储一段固定的时间，称为刷新率(刷新率的长度取决于搜索引擎获得的流量类型和您想要跟踪的“前几个结果”的数量)。如果刷新率时间段期满并且对单词“cache”的搜索没有持续，则查询被删除存储器。如果对单词“cache”的搜索仍然存在，您的算法只需要跟踪单词“cache”的搜索速度。要做到这一点，只需将所有搜索存储在“泄漏计数器”上。每个条目都被推送到计数器上，并带有过期日期，在过期日期之后，查询将被删除。您的活动计数器是您的热门查询的指示器。

Answer 3

存储每个查询都很昂贵，但要确保前10个查询实际上是前10个查询，就必须作弊。

一种想法是存储一个表，其中包含URL、命中计数器和时间戳，按计数索引，然后按时间戳索引。当表达到某个任意的接近最大大小时，开始删除超过给定天数的低端条目。虽然旧的、不频繁的查询不会被计算在内，但可能进入前10名的查询应该会出现在表中，因为查询速度更快。

另一个想法是为搜索查询编写一个16位(或更多)的散列函数。有一个包含65536个条目的表，其中包含计数器和URL。执行搜索时，如果需要，请递增相应的表项并设置URL。然而，这种方法有一个很大的缺点。垃圾邮件机器人可能会重复查询“廉价的伟哥”，可能会使合法查询增加垃圾邮件查询计数器，将它们的消息放在您的主页上。