Rough thinking...

一直都是前十名

• 使用散列集合，其中存储每个术语的计数(清除术语等)
• 一个已排序的数组，其中包含正在进行的前10个项，每当一个项的计数等于或大于该数组中的最小计数时，该数组就会添加一个项/计数

每月前十名每小时更新一次:

• 使用一个数组索引自启动模744(一个月中的小时数)以来的小时数，这个数组条目由散列集合组成，其中存储在这个小时时隙中遇到的每个项的计数。每当时隙计数器发生变化时，就会重置条目
• 每当当前时隙计数器发生变化时(最多一小时一次) ，就需要收集时隙索引的数组中的统计信息，方法是复制并平坦时隙索引的数组内容

呃... 有道理吗? 我没有像在现实生活中那样考虑清楚

啊，是的，忘了提到，每小时的“复制/扁平化”所需的每月统计数据实际上可以重用相同的代码用于前10所有的时间，一个很好的副作用。

完全正确

首先，一个保证正确结果，但需要大量内存的解决方案(大型映射)。

“空前绝后”的变体

维护一个哈希映射，查询作为键，它们的计数作为值。此外，保留目前为止最频繁的10个查询的列表和第10个最频繁查询的计数(阈值)。

在读取查询流时不断更新映射。每次计数超过当前阈值时，执行以下操作: 从“ Top 10”列表中删除第10个查询，将其替换为您刚刚更新的查询，并同时更新阈值。

“过去一个月”的变体

保持同样的“前10名”列表，并按照上面的方式更新。另外，保持一个类似的映射，但是这次将向量30 * 24 = 720计数(每小时一个)存储为值。每小时对每个键执行以下操作: 从向量中删除最老的计数器，在结尾处添加一个新计数器(初始化为0)。如果向量为全零，则从映射中删除键。此外，每个小时你都必须从头计算“十大”排行榜。

注意: 是的，这次我们存储的是720个整数而不是一个，但是键要少得多(所有时间变量都有一个 真的长尾)。

近似值

这些近似不能保证正确的解，但是减少了内存消耗。

1. 处理每个 N 次查询，跳过其余的。
2. (仅适用于所有时间变量)在映射中最多保留 M 个键-值对(M 应该尽可能大)。它是一种 LRU 缓存: 每次读取映射中没有的查询时，用计数1删除最近使用次数最少的查询，并用当前处理的查询替换它。

这是我目前正在进行的研究项目之一。这个需求几乎和你的一模一样，我们已经开发了很好的算法来解决这个问题。

输入

输入是源源不断的英语单词或短语(我们称之为 tokens)。

输出

1. 输出顶部 N 个令牌，我们已经看到了这一点 远离(我们所有的象征物) 看见了!)
2. 中的输出 top N 标记 historical window, say, last day or 上周。

这项研究的一个应用是找出 Twitter 或 Facebook 上的热门话题或话题趋势。我们有一个爬虫，在网站上爬行，它生成一个字流，这将进入系统饲料。然后系统将输出总体或历史上最高频率的单词或短语。想象一下，在过去的几周里，“世界杯”这个短语在 Twitter 上出现了很多次。“章鱼保罗”也是。:)

字符串转换为整数

系统对每个单词都有一个整数 ID。虽然网络上可能存在的单词几乎无穷无尽，但是在积累了大量的单词之后，找到新单词的可能性越来越小。我们已经找到了400万个不同的单词，并为每个单词分配了唯一的 ID。整个数据集可以作为一个散列表加载到内存中，消耗大约300MB 的内存。(我们实现了自己的哈希表。Java 的实现需要巨大的内存开销)

然后，每个短语可以被标识为一个整数数组。

This is important, because sorting and comparisons on integers is 快多了 than on strings.

档案资料

系统保存每个令牌的归档数据。基本上就是成对的 (Token, Frequency)。但是，存储数据的表将非常庞大，因此我们必须对表进行物理分区。一旦分区方案基于令牌的 ngram。如果标记是一个单词，则为1克。如果标记是两个单词短语，则为2克。然后这样继续下去。大约在4克，我们有10亿条记录，表大小在60 GB 左右。

处理传入流

该系统将吸收传入的句子，直到内存被充分利用(呀，我们需要一个记忆管理器)。在取出 N 个句子并储存在记忆中之后，系统会暂停，并开始将每个句子标记成单词和短语。每个标记(单词或短语)被计数。

对于频繁使用的标记，它们总是保存在内存中。对于较少使用的令牌，它们根据 ID 进行排序(记住，我们将 String 转换为整数数组) ，然后序列化为磁盘文件。

(但是，对于您的问题，因为您只计算单词，那么您可以将所有的单词频率映射只存储在内存中。一个精心设计的数据结构对于400万个不同的单词只会消耗300MB 的内存。一些提示: 使用 ASCII 字符表示字符串) ，这是可以接受的。

同时，一旦发现系统生成的任何磁盘文件，就会激活另一个进程，然后开始合并它。由于磁盘文件已排序，合并将采用类似于合并排序的过程。一些设计也需要在这里小心，因为我们想避免太多的随机磁盘寻找。其思想是避免同时读(合并进程)/写(系统输出) ，并让合并进程读取一个磁盘，同时写入另一个磁盘。这类似于实现锁定。

世界末日

在一天结束时，系统将有许多频率存储在内存中的频繁令牌，以及许多其他不太频繁的令牌存储在几个磁盘文件中(每个文件都进行了排序)。

The system flush the in-memory map into a disk file (sort it). Now, the problem becomes merging a set of sorted disk file. Using similar process, we would get one sorted disk file at the end.

然后，最后的任务是将排序的磁盘文件合并到归档数据库中。 根据存档数据库的大小，如果数据库足够大，该算法的工作方式如下:

   for each record in sorted disk file
update archive database by increasing frequency
if rowcount == 0 then put the record into a list
end for


for each record in the list of having rowcount == 0
insert into archive database
end for

直觉告诉我们，过一段时间之后，插入的次数会变得越来越少。越来越多的操作将只在更新。而且这种更新不会受到索引的惩罚。

希望这整个解释能有所帮助。 :)

上个月十大搜索关键词

使用内存高效的索引/数据结构，例如 紧凑的尝试(来自 尝试上的 Wikipedia 条目)大致定义了内存需求和 n 个术语之间的关系。

在需要的内存可用的情况下(假设1) ，您可以保持准确的月度统计信息，并将每个月的统计信息汇总为所有时间的统计信息。

There is, also, an assumption here that interprets the 'last month' as fixed window. But even if the monthly window is sliding the above procedure shows the principle (sliding can be approximated with fixed windows of given size).

这让我想起了 循环数据库循环数据库循环数据库，除了一些统计数据是根据“所有时间”计算的(在某种意义上，并不是所有的数据都被保留; rrd 通过平均、求和或选择 max/min 值来合并时间段，忽略了细节，在给定的任务中，丢失的细节是关于低频项目的信息，这可能会导致错误)。

假设1

如果我们不能保持完美的统计整个月，那么我们应该能够找到一个特定的时期 P，我们应该能够保持完美的统计。 例如，假设我们对某个时间段 P 有完美的统计，它进入月 n 次。
完美的数据定义函数 f(search_term) -> search_term_occurance。

如果我们可以保持所有的 n完美统计表在内存中，那么每月的滑动统计可以这样计算:

• add stats for the newest period
• remove stats for the oldest period (so we have to keep n perfect stat tables)

然而，如果我们只保留聚合级别(每月)的前10名，那么我们将能够从固定时期的完整统计数据中丢弃大量数据。这给出了一个已经有固定内存需求的工作过程(假设周期 P 的完美统计表的上界)。

上述过程的问题在于，如果我们只在滑动窗口的前10个关键词上保留信息(类似于所有时间) ，那么对于在一段时间内达到峰值的搜索关键词，统计数据将是正确的，但是可能看不到随着时间的推移不断涌入的搜索关键词的统计数据。

这可以通过保留前10名词汇的信息来抵消，例如前100名词汇，希望前10名词汇是正确的。

我认为进一步的分析可以将条目成为统计数据的一部分所需的最小出现次数联系起来(这与最大错误有关)。

(在决定哪些条目应该成为统计数据的一部分时，人们还可以监控和跟踪趋势; 例如，如果对每个时期 P 的每个条目的发生情况进行线性外推，告诉你这个条目将在一两个月内变得重要，你可能已经开始跟踪它。类似的原则也适用于从跟踪池中删除搜索词。)

最糟糕的情况是，你有很多几乎同样频繁的术语，它们一直在变化(例如，如果只跟踪100个术语，那么如果前150个术语同样频繁出现，但前50个术语更多地出现在第一个月，以免经常出现一段时间后，统计数据就不会保持正确)。

此外，还有一种方法可能不是固定的内存大小(严格来说，也不是以上) ，这将定义最小的重要性的发生/期间(日，月，年，所有时间) ，以保持统计数据。这可以保证在聚合过程中每个统计数据的最大错误(再次参见循环)。

如果是对 “高速缓存文件置换机制”(也称为“第二次机会”)的改编呢？我可以想象，如果搜索请求是均匀分布的(这意味着大多数搜索条目会定期出现，而不是连续出现500万次，然后再也不会出现) ，那么它将非常有效。

下面是算法的可视化表示:

如何使用具有10个节点的 Splay Tree？每次尝试访问树中不包含的值(搜索词)时，抛出任何叶子，插入该值并访问它。

这背后的想法是相同的，在我的其他 回答。在均匀/定期地访问搜索条件的假设下，这个解决方案应该表现得非常好。

编辑

还可以在树中存储更多的搜索条件(我在另一个答案中建议的解决方案也是如此) ，以避免删除可能很快再次访问的节点。一个人在其中储存的价值越多，结果就越好。

不知道我理解得对不对。 我的解决方案是使用堆。 因为前10个搜索项，所以我构建了一个10大小的堆。 然后用新的搜索更新这个堆。如果新搜索的频率大于堆(Max Heap) top，请更新它。放弃频率最小的那个。

但是，如何计算具体搜索的频率将取决于其他东西。 也许正如大家所说，数据流算法..。

使用 cm- 草图存储从开始的所有搜索的计数，保持一个10大小的最小堆为前10。 对于每月的结果，保持30厘米的草图/散列表和最小堆，每一个开始计数和更新从最近的30,29。.，1天。作为一天过去，清除最后一个，并使用它作为第一天。 对于每小时的结果也是一样，保持60个哈希表和最小堆，并开始计数最后60、59、 ... ... 1分钟。作为一分钟通过，清除最后和使用它作为分钟1。

每月结果在1天的范围内准确，每小时结果在1分钟的范围内准确

当您有一个固定数量的内存和一个“无限”(认为非常非常大)的令牌流时，这个问题并不是普遍可以解决的。

一个粗略的解释..。

To see why, consider a token stream that has a particular token (i.e., word) T every N tokens in the input stream.

另外，假设内存可以保存对最多 M 个标记的引用(单词 id 和计数)。

有了这些条件，就可以构造一个输入流，在这个流中，如果 N 足够大，使得流在 T 之间包含不同的 M 个令牌，那么就永远不会检测到令牌 T。

这是独立于顶部 N 算法的细节。它只取决于极限 M。

要了解为什么会这样，请考虑由两个相同令牌组成的传入流:

T a1 a2 a3 ... a-M T b1 b2 b3 ... b-M ...

其中 a 和 b 都是不等于 T 的有效标记。

Notice that in this stream, the T appears twice for each a-i and b-i. Yet it appears rarely enough to be flushed from the system.

从一个空内存开始，第一个令牌(T)将占用内存中的一个槽(以 M 为界)。然后 a1将消耗一个槽，当 M 耗尽时，一直到 a-(M-1)。

当 a-M 到达时，算法必须删除一个符号，因此让它成为 T。 下一个符号将是 b-1，这将导致 a-1被刷新，等等。

因此，T 不会在内存驻留足够长的时间来建立一个真正的计数。简而言之，任何算法都会丢失一个本地频率足够低但全局频率较高(超过流长度)的令牌。