search前10个search词的algorithm
我现在正在准备面试，这让我想起了曾经在以前的一次采访中被问到的一个问题：
“您被要求devise一些软件来持续显示Google上的前10个search字词，您可以访问一个供稿源，该search字词可以在Google上search目前正在search的实时search词条，描述什么algorithm和数据结构你会用它来实现这个，你要devise两个变体：
（i）显示所有时间的前10个search条件（即自您开始阅读提要以来）。
（ii）仅显示过去一个月的前10个search字词，每小时更新一次。
你可以使用近似值来获得前10名，但是你必须certificate你的select是合理的。“
我在这次采访中轰炸了，至今还不知道如何实施。
第一部分要求在一个不断增长的无限列表子序列中最频繁的10个项目。 我研究了selectalgorithm，但是找不到任何在线版本来解决这个问题。
第二部分使用了一个有限的列表，但是由于大量的数据正在被处理，所以你不能真正的将整个月的search词存储在内存中，并且每小时计算一次直方图。
问题变得更加困难的事实，前10名单不断更新，所以不知何故，你需要通过滑动窗口计算前10名。
有任何想法吗？
那么，看起来像一个可怕的很多数据，可能是昂贵的成本存储所有频率。 当数据量太大 ，我们不能希望将其全部存储，我们进入数据streamalgorithm的领域。
这方面的有用的书籍： Muthukrishnan – “数据stream：algorithm和应用”
密切相关的我从上面挑选的问题： Manku，Motwani – “数据stream的近似频率计数”[pdf]
顺便说一句，斯坦福大学的Motwani（编辑）是非常重要的“随机algorithm”一书的作者。 本书第十一章涉及这个问题 。 编辑：对不起，引用不好，那个特定的章节是在不同的问题。 经过检查，我推荐Muthukrishnan的书的第5.1.2节 ，可在网上。
嘿，很好的面试问题。
频率估计概述
有一些众所周知的algorithm可以使用固定的存储量为这样的stream提供频率估计。 一个是Frequent，由Misra和Gries（1982）。 从n个项目列表中，使用k-1个计数器find所有发生超过n / k次的项目。 这是Boyer和Moore的多数algorithm（Fischer-Salzberg，1982）的推广，其中k是2. Manku和Motwani的LossyCounting （2002）和Metwally的SpaceSaving （2005）algorithm具有类似的空间要求，但是可以在某些条件。
重要的是要记住这些algorithm只能提供频率估计。 具体而言，米斯拉格里斯估计可以低于（n / k）项目的实际频率。
假设你有一个algorithm， 只有当它发生超过50％的时间，才能肯定地识别一个项目。 给这个algorithm提供一个N个不同项目的stream，然后再添加一个N – 1个副本，一个项目x ，总共2N-1个项目。 如果algorithm告诉你x超过了总数的50％，它必须在第一个stream中; 如果没有， x不在最初stream中。 为了让algorithm做出这个决定，它必须存储初始stream（或一些与其长度成比例的概要）！ 所以，我们可以向自己certificate这样一个“精确”algorithm所需要的空间是Ω（ N ）。
相反，这里描述的这些频率algorithm提供了一个估计，确定任何超过阈值的项目，以及一些项目下降一定的余量。 例如，使用单个计数器的多数（Majority）algorithm将总是给出结果; 如果有任何项目超过stream的50％，它会被发现。 但它也可能会给你一个只发生一次的项目。 如果不对数据进行第二遍处理（再次使用单个计数器，但仅查找该项目），则不知道。
频繁algorithm
下面是Misra-Gries的Frequentalgorithm的简单描述。 Demaine（2002）等人已经对algorithm进行了优化，但是这给了你的要点。
指定阈值分数， 1 / k ; 任何发生超过n / k倍的项目都会被find。 创build一个空的地图（如红黑树）; 键将是search词，并且这些值将是该词的计数器。
- 查看stream中的每个项目。
- 如果该术语存在于地图中，请增加关联的计数器。
- 否则，如果地图小于k-1个条目，则将该项添加到具有一个计数器的地图中。
- 但是，如果地图已经有k-1个条目，则在每个条目中递减计数器。 如果任何计数器在此过程中达到零，请将其从地图上移除。
请注意，您可以使用固定数量的存储处理无限数量的数据（只是固定大小的地图）。 所需的存储量仅取决于感兴趣的阈值，并且stream的大小无关紧要。
计数search
在这种情况下，也许你缓冲了一个小时的search，并在那个小时的数据上执行这个过程。 如果您可以在本小时的searchlogging中进行第二次传递，则可以精确计算第一阶段中确定的最高“候选人”的出现次数。 或者，也许可以做一个单一的通行证，并报告所有的候选人，知道任何应该在那里的项目是包括在内，任何额外的只是噪音，将在下一个小时内消失。
任何真正超过感兴趣阈值的候选人将被存储为摘要。 保留一个月的这些总结，扔掉每个小时的最古老的，你将有一个很好的近似最常见的search条件。
这是我目前正在经历的一个研究项目。 这个要求和你的要求几乎一样，我们已经开发出了很好的algorithm来解决这个问题。
input
input是层出不穷的英文单词或短语（我们称之为tokens ）。
输出
- 输出迄今为止我们所见过的最多N个令牌（从我们所看到的所有令牌中）
- 在历史窗口中输出前N个令牌，比如说上一天或上周。
本研究的一个应用是在Twitter或Facebook上find热门话题或话题的趋势。 我们有一个在网站上爬行的爬行器，它会产生一串文字，将会进入系统。 然后系统将在整体或历史上输出最高频率的单词或短语。 想象一下，在过去的几周里，“世界杯”这个词语在Twitter上将会出现很多次。 “保罗章鱼”也是如此。 🙂
string整数
系统为每个单词都有一个整数ID。 尽pipe互联网上可能存在的词语几乎是无限的，但是在积累了大量词汇后，发现新词的可能性越来越低。 我们已经find了400万个不同的单词，并为每个单词分配了一个唯一的ID。 这整套数据可以作为哈希表加载到内存中，消耗大约300MB的内存。 （我们已经实现了我们自己的哈希表，Java的实现需要巨大的内存开销）
然后每个短语可以被识别为一个整数数组。
这很重要，因为对整数的sorting和比较比string要快得多 。
存档数据
系统保存每个令牌的归档数据。 基本上它是(Token, Frequency) 。 但是，存储数据的表格非常庞大，我们必须物理分区。 一旦分区scheme基于令牌的ngrams。 如果令牌是单个单词，则为1克。 如果令牌是双字短语，则为2克。 这就继续下去。 大概在4克，我们有10亿条logging，桌子大小在60GB左右。
处理传入stream
系统将吸收传入的句子，直到内存被充分利用（Ya，我们需要一个MemoryManager）。 在loggingN个句子并存储之后，系统暂停，并开始将每个句子标记为单词和短语。 每个标记（单词或短语）都被计数。
对于频繁的令牌，它们总是被留在记忆中。 对于不太常见的令牌，它们是基于ID进行sorting的（请记住，我们将string转换为整数数组），然后序列化为磁盘文件。
（但是，对于你的问题，因为你只计算单词，所以你可以把所有的单词频率映射到内存中，一个精心devise的数据结构在400万个不同的单词中只消耗300MB的内存，有些提示：代表string），这是可以接受的。
同时，一旦find系统生成的磁盘文件，就会启动另一个进程，然后开始合并。 由于磁盘文件是sorting的，合并将采取类似的过程，如合并sorting。 这里也需要注意一些devise，因为我们要避免太多的随机磁盘查找。 这个想法是为了避免同时读取（合并过程）/写入（系统输出），并让合并过程从一个磁盘读取到另一个磁盘中。 这与实现locking类似。
一天的结束
在一天结束时，系统将有许多频繁的令牌存储在内存中，而许多不太频繁的令牌存储在多个磁盘文件中（并且每个文件都被sorting）。
系统将内存映射清理成一个磁盘文件（对其进行sorting）。 现在，问题就变成了一组sorting的磁盘文件。 使用类似的过程，我们会得到一个sorting的磁盘文件在最后。
然后，最后的任务是将sorting的磁盘文件合并到归档数据库中。 取决于档案数据库的大小，如果足够大，则algorithm如下所示：
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
直觉是在一段时间之后，插入的数量会越来越小。 越来越多的操作将只在更新。 而这个更新不会受到索引的惩罚。
希望这整个解释会有所帮助。 🙂
你可以使用一个哈希表结合二叉search树 。 实现一个<search term, count>字典，告诉你每个search项search了多less次。
显然每小时迭代整个哈希表以获得前10名是非常糟糕的。 但是，这是我们正在谈论的谷歌，所以你可以假设，前十名都将得到，说超过10 000点击（虽然它可能是一个更大的数字）。 因此，每当search字词数超过10 000时，将其插入BST。 那么每一个小时，你只需要从BST获得前10个，这个应该包含相对较less的条目。
这解决了前10名的问题。
真正棘手的部分是在月度报告中处理另外一个术语（例如，“堆栈溢出”可能在过去两个月中有5万次点击，但是过去一个月只有10 000次，而“亚马逊”可能有40个过去两个月为3万，过去一个月为3万，你想在月报中把“亚马逊”放在“堆栈溢出”之前）。 要做到这一点，我会为所有主要（超过10 000个所有时间的search）search条件存储一个30天的列表，告诉您每天search该词的次数。 该列表将像FIFO队列一样工作：您每天（或每个小时）删除第一天并插入新的一个，但可能需要存储更多的信息，这意味着更多的内存/空间，如果内存不是问题它，否则去为他们正在谈论的“近似”）。
这看起来是一个好的开始。 然后，你可以担心修剪的条件有一万个点击，但很久没有很多东西了。
情况我）
为所有searchterms维护一个散列表，以及一个与散列表分开的sorting前十名单。 每当search发生时，在散列表中增加适当的项目，并检查该项目是否现在应该用前十列表中的第10项来切换。
O（1）查找前十列表，并将最大O（log（n））插入散列表（假定由自平衡二叉树pipe理的冲突）。
情况ii）我们不是维护一个巨大的散列表和一个小列表，而是维护一个散列表和一个所有项目的sorting列表。 每当进行search时，该项在散列表中增加，并且在sorting列表中可以检查该项是否应该随着项之后的项来切换。 一个自我平衡的二叉树可以很好地工作，因为我们也需要能够快速查询（后面会详细介绍）。
此外，我们还以FIFO列表（队列）的forms保存“小时”列表。 每个“小时”元素将包含在该特定小时内完成的所有search的列表。 例如，我们的小时数列表可能如下所示：
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
然后，每隔一小时：如果列表的长度至less为720小时（即30天内的小时数），则查看列表中的第一个元素，对于每个search项，将散列表中的元素减less适当的数量。 之后，从列表中删除第一个小时元素。
所以假设我们在721小时，我们已经准备好看我们列表中的第一个小时（上面）。 我们会把散列表中的免费东西减less56个，有趣的图片减less321个，然后从列表中完全删除小时0，因为我们再也不需要再去查看了。
我们维护所有允许快速查询的条款的sorting列表的原因是因为在我们从720小时前经过search条件后的每一小时，我们需要确保排在前十位的列表。 所以当我们在hashtable中减less56个“free stuff”时，我们会检查它现在属于哪个列表。 因为它是一个自平衡二叉树，所有这些都可以在O（log（n））时间内很好地完成。
编辑：牺牲空间的准确性…
像第二个那样，在第一个实施一个大列表也许是有用的。 然后，我们可以在两种情况下应用以下空间优化：运行cron作业以除去列表中的前x个项目。 这将保持空间需求下降（并因此更快地对列表进行查询）。 当然，这会导致一个近似的结果，但这是允许的。 可以在基于可用内存部署应用程序之前计算x ，并且如果有更多存储器可用，则dynamic调整x 。
粗思
所有时间的前10
- 使用哈希集合，其中存储了每个术语的计数（清理术语等）
- 一个包含正在进行的前10位的sorting数组，每当一个项的计数等于或大于数组中的最小计数时，将添加到该数组中的项/计数
对于按月更新的每小时10个月：
- 使用一个以从744开始所经过的小时数（一个月内的小时数）为索引的数组，该数组项包含散列集合，其中存储了在此小时隙中遇到的每个项的计数。 每当小时隙计数器改变时，条目将被重置
- 每当当前小时隙计数器改变（最多一小时一次）时，通过拷贝和展平在小时隙上索引的该数组的内容，需要收集在小时隙上索引的数组中的统计数据
错误…有道理？ 我没有像现实生活中那样思考
啊，是的，忘了提及，每月统计所需的每小时“复制/压扁”实际上可以重复使用与前十名相同的代码，这是一个很好的副作用。
确切的解决scheme
首先，一个解决scheme，保证正确的结果，但需要大量的内存（大地图）。
“全时”变体
使用查询作为键维护一个哈希映射，并将其作为值计数。 此外，保持迄今为止最频繁的10个查询的列表以及第10个最频繁的计数（阈值）的计数。
读取查询stream后，不断更新地图。 每次计数超过当前阈值时，请执行以下操作：从“前10名”列表中删除第10个查询，将其replace为刚刚更新的查询，然后更新阈值。
“上个月”变体
保持相同的“前十名单”，并按照上述相同的方式进行更新。 此外，保留一个类似的地图，但这次存储vector30 * 24 = 720计数（每个小时一个）作为值。 每个小时都为每个关键点执行以下操作：从向量中删除最早的计数器，并在最后添加一个新的（初始化为0）。 如果vector是全零，从地图上删除键。 而且，每个小时你都必须从头开始计算“前10名”。
注意：是的，这次我们存储了720个整数，而不是一个，但是键的数量要less得多（这个所有的variables都有一个很长的尾部）。
约稿
这些近似值不能保证正确的解决scheme，但是消耗更less的内存。
- 处理每个第N个查询，跳过其余部分。
- （仅适用于所有时间variables）在地图中最多保留M个键值对（M应该尽可能大）。 这是一种LRUcaching：每次读取不在映射中的查询时，删除最近使用次数最less的查询，并将其replace为当前处理的查询。
前10个search条件
使用内存高效的索引/数据结构，例如紧密压缩的尝试 （来自trypedia上的维基百科条目）近似地定义了内存需求和n个术语之间的一些关系。
如果需要的记忆是可用的（ 假设1 ），您可以保持精确的每月统计，并将其每月汇总到所有时间统计中。
这里还有一个假设，把“上个月”解释为固定窗口。 但是，即使月度窗口滑动，上面的程序也显示了原理（滑动可以用给定大小的固定窗口近似）。
这让我想起了循环法数据库 ，除了一些统计数据是按照“所有时间”来计算的（从某种意义上说，并非所有的数据都是保留的; rrd通过求平均值，总结或select最大值/最小值来合并时间段，在给定的任务中，丢失的细节是关于低频项目的信息，这可能引入错误）。
假设1
如果我们不能在整个月里保持完美的统计数据，那么我们应该能够find一个能够保持完美数据的特定时期。 例如，假设我们对某个时间段P进行了完美的统计，这个时间段进入了n个月。
完美的统计定义函数f(search_term) -> search_term_occurance 。
如果我们可以在记忆中保存所有n完美的统计表，那么滑动每月统计可以这样计算：
- 添加最新时期的统计信息
- 删除最古老的统计数据（所以我们必须保留
n完美的统计表）
但是，如果我们只保持总量水平前10名（每月），那么我们将能够从固定期间的完整统计数据中丢弃大量数据。 这给已经固定的工作stream程（假设P期完美统计表的上限）存储器需求。
上述过程的问题在于，如果我们只保留一个滑动窗口的前10项（类似于所有时间）的信息，那么统计信息对于在一段时间内达到峰值的search项将是正确的，但可能不会看到search条件的统计数据随着时间的推移不断的stream逝。
这可以通过保持信息超过前10名来抵消，例如前100名，希望前10名是正确的。
我认为进一步的分析可能会涉及一个条目成为统计数据的一部分（与最大误差有关）所需的最小事件数量。
（在决定哪些条目应该成为统计数据的一部分时，还可以监视和跟踪趋势;例如，如果在每个期间P的每个事件的事件的线性外推告诉你该术语将在一两个月内变得重要，可能已经开始跟踪它了，类似的原则适用于从跟踪池中删除search词。）
最糟糕的情况是，当你有很多几乎同样频繁的条件，他们总是改变（例如，如果只跟踪100条款，那么如果前150名词同样频繁地发生，但前50名更常在第一个月以免经常过一段时间，统计数据不会正确保存）。
另外还有另一种方法，在内存大小上并不固定（严格来说，上面也不是这样），它会根据事件/周期（日，月，年，全时）统计。 这可以保证聚合过程中每个统计数据中的最大误差（再次参见循环赛）。
那么“时钟页面replacealgorithm” （也称为“二次机会”）的适应呢？ 如果search请求是均匀分布的（这意味着大多数search的术语经常出现，而不是连续5百万次，然后再也不会），我可以想象它能够很好地工作。
以下是该algorithm的可视化表示： 
将search项的数量存储在巨大的哈希表中，其中每个新的search都会使特定的元素递增1。 跟踪前20名左右的search字词; 当第11位的元素增加时，检查是否需要用＃10 *replace位置（不需要保留前10位;所有你关心的是划分第10位和第11位）。
* 需要进行类似的检查，看看新的search词是否在第11位，所以这个algorithm也会起泡到其他search词 – 所以我简化了一下。
有时候最好的答案是“我不知道”。
我会采取更深入的刺。 我的第一个直觉就是把结果input到一个Q中。一个进程将不断地处理进入Q的项目。这个进程将保持一个
长期 – >计数
每次处理Q项目时，只需查找search项并递增计数即可。
同时，我会保留一张对地图前十位条目的引用列表。
对于当前实现的条目，请查看它的计数是否大于前10位中最小条目的计数的计数（如果不在列表中）。 如果是，用条目replace最小的。
我认为这将工作。 没有操作是时间密集的。 你将不得不find一种方法来pipe理计数地图的大小。 但是面试的答案应该足够好。
他们并不期待一个解决scheme，想看看你能不能想。 你不必在那里写解决scheme….
一种方法是，对于每个search，您存储该search词和它的时间戳。 这样，在任何时间段内find前十名都只是比较给定时间段内的所有search条件。
该algorithm很简单，但缺点是内存和时间消耗较大。
如何使用10个节点的Splay树 ？ 每次尝试访问树中未包含的值（search词）时，抛出任何叶，插入值并访问它。
这背后的想法是在我的其他答案相同。 在假设search条件被均匀/定期访问的情况下，该解决scheme应该performance得非常好。
编辑
也可以在树中存储一些更多的search条件（对于我在其他答案中build议的解决scheme也是如此），以便不删除可能很快被访问的节点。 其中存储的价值越高，结果就越好。
不知道，如果我理解正确与否。 我的解决scheme是使用堆。 由于前10个search项目，我build立一个大小为10的堆。然后用新的search来更新这个堆。 如果新search的频率大于堆（最大堆）顶部，则更新它。 放弃频率最小的那个。
但是，如何计算特定search的频率将被计入其他内容。 也许每个人都说，数据streamalgorithm….
使用cm-sketch存储自开始以来所有search的计数，保留最小10的大小为前10的最小堆。对于月度结果，保留30厘米草图/散列表和最小堆，每一个开始从上次的30日，29日，1日计数和更新。 作为一天通过，清除最后一个，并使用它作为第1天。同样的小时结果，保持60哈希表和最小堆，并开始计数最后60,59，… 1分钟。 As a minute pass, clear the last and use it as minute 1.
Montly result is accurate in range of 1 day, hourly result is accurate in range of 1 min
