我目前正在准备一次面试，这让我想起了之前一次面试中被问到的一个问题，大致如下：
“你被要求设计一些软件，以持续显示 Google 上前 10 个搜索词。你可以使用提供无限实时流的数据源，该数据源提供当前正在 Google 上进行搜索的搜索词。请描述您将使用哪些算法和数据结构来实现此功能。您需要设计两个变体：
(i) 显示自开始阅读流以来的所有时间内排名前 10 的搜索词。
(ii) 显示过去一个月内每小时更新的前 10 个搜索词。
您可以使用近似值来获得前 10 名列表，但必须证明您的选择。”
我在这个面试中失败了，至今仍不知道如何实现。
第一部分要求在一个无限增长的子序列中找出前 10 个最频繁的元素。我研究了一些选择算法，但找不到任何在线版本来解决这个问题。
第二部分使用有限的列表，但由于处理的数据量很大，您无法真正将整个月的搜索词存储在内存中并每小时计算一次直方图。
由于前十列表一直在不断更新，所以问题变得更加困难，您需要通过滑动窗口计算出前十名的结果。
有什么想法吗？
有一些著名算法可以使用固定数量的存储空间为此类流提供频率估计。其中之一是 Misra 和 Gries（1982）的 Frequent 算法。从一个包含 n 个项目的列表中，它使用 k-1 个计数器查找所有出现超过 n / k 次的项目。这是 Boyer 和 Moore 的 Majority 算法（Fischer-Salzberg，1982）的推广，其中 k 为 2。Manku 和 Motwani（2002）的 LossyCounting 和 Metwally 的 SpaceSaving（2005）算法具有类似的空间要求，但在某些条件下可以提供更准确的估计。
需要记住的重要事情是这些算法只能提供频率估计。具体而言，Misra-Gries 估计可能会将实际频率少计算 (n / k) 个项目。
假设您有一个仅当某个项目出现超过50％的时间时才能确定其身份的算法。将此算法馈送一个包含 N 个不同项目的流，然后添加另外 N-1 个项目，x，使得总共有 2N-1 个项目。如果算法告诉您 x 超过了总数的50％，那么它必须在第一个流中；否则，x 不在初始流中。为了让算法做出这个决定，它必须存储初始流（或者与其长度成比例的某些摘要）！因此，我们可以证明这样一个 "精确 "算法所需的空间为 Ω(N)。
相反，这里描述的频率算法提供了一个估计值，识别超过阈值的任何条目以及一些略低于阈值的条目。例如，多数 算法使用单个计数器，将始终给出结果；如果任何项目超过流的50％，它将被找到。但它也可能给你一个仅出现一次的项目。没有进行第二遍数据扫描（再次使用单个计数器，但仅查找该项），你无法确定。
这里是Misra-Gries 频繁 算法的简单描述。Demaine（2002）和其他人对算法进行了优化，但这给出了算法的要点。
指定阈值分数，1 / k ；出现次数超过 n / k 的任何项都将被找到。创建一个空映射（如红黑树）；键将是搜索术语，值将是该术语的计数器。
请注意，您可以使用固定大小的映射处理无限量的数据。所需的存储量仅取决于感兴趣的阈值，而流的大小并不重要。
1 /（1 + X），其背后的理论是什么？ - q0987看起来这是大量的数据，存储所有频率可能成本过高。当数据量非常大以至于我们无法全部存储时，我们就进入了数据流算法领域。
在这个领域中，有一本有用的书： Muthukrishnan - "Data Streams: Algorithms and Applications"
从上述内容中我选择的与问题密切相关的参考文献： Manku, Motwani - "Approximate Frequency Counts over Data Streams" [pdf]
顺便说一下，斯坦福的Motwani博士是著名书籍"Randomized Algorithms"的作者之一。 该书的第11章涉及到了这个问题。 编辑:对不起，参考文献错误，那个特定的章节是关于另一个问题的。经过核实，我建议你阅读在线可用的Muthukrishnan书中的5.1.2节。
嘿，不错的面试问题。
（Token，Frequency）对。但是，存储数据的表会非常巨大，以至于我们必须在物理上分区表。一个分区方案基于令牌的ngrams。如果令牌是单个单词，则为1gram。如果令牌是两个单词短语，则为2gram。这样就可以了。大约在4gram处，我们有10亿条记录，表大小约为60GB。
处理传入流
系统将吸收传入的句子，直到内存完全利用为止（是的，我们需要MemoryManager）。将N个句子存储在内存中后，系统将暂停，并开始将每个句子标记为单词和短语。计算每个标记（单词或短语）的数量。
对于高频令牌，始终保留在内存中。对于较少频繁的令牌，它们基于ID进行排序（记住我们将字符串转换为整数数组），并序列化为磁盘文件。
（但是，对于您的问题，由于您仅计数单词，则可以仅将所有单词频率映射放入内存中。经过认真设计的数据结构将仅占用300MB内存，适用于400万个不同的单词。一些提示：使用ASCII字符表示字符串），这是可以接受的。
同时，将有另一个进程被激活，一旦发现系统生成的任何磁盘文件，就会开始合并它们。由于磁盘文件已排序，因此合并过程类似于归并排序。在这里也需要注意一些设计，因为我们 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
直觉告诉我们，随着时间的推移，插入操作的数量将变得越来越少。更多的操作将仅涉及更新，并且这些更新不会受到索引的惩罚。
希望这整个解释对你有所帮助。 :)
<搜索词，计数>的字典，告诉你每个搜索词已经被搜索了多少次。
显然，每小时遍历整个哈希表以获取前10名是非常糟糕的。但这是在谈论Google，所以你可以假设前十名都会获得超过10,000次点击（尽管这可能是一个更大的数字）。因此，每当一个搜索词的计数超过10,000时，将其插入BST中。然后，每小时，您只需要从BST中获取前10个，其中应该包含相对较少的条目。
这解决了所有时间的前十名问题。
这看起来像是一个很好的开始。然后，您可以担心修剪那些具有大于10,000次点击但长时间没有太多点击的术语等等。
情况一)
为所有搜索词维护一个哈希表，以及与哈希表分开的排序前十列表。每当发生搜索时，增加哈希表中相应的项，并检查该项是否应该现在与前十列表中的第十项交换。
对于前十列表，O(1) 的查找，对于哈希表，最大 O(log(n)) 的插入（假设碰撞由自平衡二叉树管理）。
情况二)
不再维护一个巨大的哈希表和一个小列表，而是维护一个哈希表和一个包含所有项的排序列表。每当进行搜索时，增加哈希表中相应的项，并在排序列表中检查该项是否应该与其后面的项交换。自平衡二叉树可能很适合此任务，因为我们还需要能够快速查询它（稍后会详细介绍）。
此外，我们还维护了一个“小时”列表，形式为 FIFO 列表（队列）。每个“小时”元素都包含在该特定小时内完成的所有搜索的列表。例如，我们的小时列表可能如下所示：
Time: 0 hours
-Search Terms:
-free stuff: 56
-funny pics: 321
-stackoverflow: 1234
Time: 1 hour
-Search Terms:
-ebay: 12
-funny pics: 1
-stackoverflow: 522
-BP sucks: 92
初步想法...
对于历史前十：
对于每月更新一次的前十名：
这样说明白了吗？我没有像在现实生活中那样深入思考。
啊，是的，我忘了提到，对于每月统计所需的每小时“复制/展开”实际上可以重用用于历史前十的相同代码，这是一个好的副作用。
首先，有一个保证正确结果的解决方案，但需要大量内存（一个大地图）。
维护一个哈希映射表，将查询作为键，将它们的计数作为值。此外，保持一个包含10个最频繁查询和第10个最频繁计数（阈值）的列表f。
随着查询流的不断更新，不断更新映射表。每当计数超过当前阈值时，请执行以下操作：从“Top 10”列表中删除第10个查询，用刚刚更新的查询替换它，并更新阈值。
保持相同的“Top 10”列表，并以与上述方式相同的方式更新它。还要保留类似的映射表，但这次将30*24 = 720个计数向量（每小时一个）作为值存储。每小时对每个键执行以下操作：从向量中删除最旧的计数器，在末尾添加一个新的计数器（初始化为0）。如果向量全部为零，则从映射表中删除该键。此外，每小时必须从头开始计算“Top 10”列表。
注意：是的，这次我们存储了720个整数而不是一个，但键要少得多（全时段变体有一个非常长的尾巴）。
这些近似方法不能保证正确的解决方案，但内存消耗较少。
过去一个月的十大搜索词
使用内存高效的索引/数据结构，例如紧密压缩字典树（维基百科上关于字典树的条目）可以大致定义内存需求和词项数n之间的某种关系。
在有足够内存的情况下（假设1），您可以保留精确的每月统计数据，并将其汇总为所有时间的统计数据。
这里还有一个假设，即将“上个月”解释为固定窗口。 但即使月度窗口是滑动的，上述程序也展示了原则（可以用给定大小的固定窗口近似滑动）。
这让我想起了循环数据库，唯一的区别是某些统计数据是基于“所有时间”的计算（即不保留所有数据；rrd通过平均、求和或选择最大/最小值来合并时间段，在给定任务中丢失的细节是低频项目的信息，这可能会引入误差）。
假设1
如果我们无法保持整个月的完美统计数据，那么我们应该能够找到一定的时间段P，以便我们能够保持完美的统计数据。
例如，假设我们在某个时间段P上拥有完美的统计数据，该时间段分为n个月。
完美的统计数据定义函数f(search_term) -> search_term_occurance。
如果我们可以将所有n个完美统计表格都保存在内存中，则滑动的每月统计数据可按以下方式计算：
但是，如果仅在聚合级别（每月）上保留前十个搜索词，那么就能够从固定时间段的完整统计数据中丢弃许多数据。这已经提供了一个有工作效果的程序，其内存需求是固定的（假设最大的完美统计表格的上限）。
上述过程的问题在于，如果仅保留滑动窗口（类似于所有时间）中的前10个搜索词的信息，则对于不断涌入的搜索词可能无法看到统计数据，这会影响到正确性。
可以通过保留更多的信息来抵消这一点，例如保留前100个搜索词的信息，希望前10个是正确的。
我认为进一步分析可以将一个条目成为统计数据一部分所需的最小发生次数与最大误差相关联。
在确定哪些条目应成为统计数据的一部分时，还可以监视和跟踪趋势；例如，如果对于每个术语，在每个期间P中出现次数的线性外推告诉您该术语将在一个月或两个月内变得重要，那么您可能已经开始跟踪它。类似的原理也适用于从跟踪池中删除搜索术语。最坏的情况是当您有很多几乎同样频繁的术语并且它们一直在变化时（例如，如果仅跟踪100个术语，则如果前150个术语出现的频率相等，但前50个术语在第一个月更常见，而后来则不常见，则统计数据将不正确）。此外，还可以采用另一种方法，该方法在内存大小上不固定（严格来说，以上方法也是如此），该方法会以每个期间（日、月、年、全部时间）内的出现/周期定义最小显着性，以保证在聚合过程中每个统计数据的最大误差（再次参见轮询）。
T a1 a2 a3 ... a-M T b1 b2 b3 ... b-M ...
其中a和b都是有效的令牌，不等于T。
注意，在此流中，每个a-i和b-i都会出现两次T。但它出现得不够频繁，以至于可以从系统中清除。
从空内存开始，第一个令牌（T）将占用内存中的一个插槽（受M限制）。然后a1将消耗一个插槽，一直到a-(M-1)当M用尽时。
当a-M到达时，算法必须丢弃一个符号，让它成为T。下一个符号将是b-1，这将导致a-1被刷新，依此类推。
因此，T不会在内存中停留足够长的时间来建立真正的计数。简而言之，任何算法都会错过低局部频率但高全局频率（在流的长度上）的令牌。
你序列中子序列[2; 2; 3; 3; 3; 4; 4; 4; 4; 5; 5]中最频繁的项是什么？- IVlad