del*_*del 114 algorithm data-structures
我正在准备接受采访,这让我想起曾经在之前的一次采访中被问过的一个问题:
"您被要求设计一些软件,以便在Google上连续显示前10个搜索字词.您可以访问提供无限实时搜索字词流的Feed,目前正在Google上搜索.请说明算法和数据结构你会用来实现这个.你要设计两个变种:
(i)显示所有时间的前10个搜索词(即自您开始阅读提要以来).
(ii)仅显示过去一个月的前10个搜索字词,每小时更新一次.
您可以使用近似值来获得前十名,但您必须证明自己的选择是合理的."
我在这次采访中遭到轰炸,但仍然不知道如何实现这一点.
第一部分要求在无限列表的不断增长的子序列中的10个最频繁的项目.我查看了选择算法,但找不到任何在线版本来解决这个问题.
第二部分使用有限列表,但由于处理的数据量很大,您无法将整个月的搜索项存储在内存中并每小时计算一次直方图.
前十名列表不断更新,这个问题变得更加困难,所以不管怎样你需要在滑动窗口上计算前十名.
有任何想法吗？
eri*_*son 55
有一些众所周知的算法可以使用固定数量的存储来为这样的流提供频率估计.一个是Frerant,由Misra和Gries(1982).从n个项目的列表中,它使用k-1计数器查找出现超过n/k次的所有项目.这是Boyer和Moore的多数算法(Fischer-Salzberg,1982)的推广,其中k为2. Manku和Motwani的LossyCounting(2002)和Metwally的SpaceSaving(2005)算法具有相似的空间要求,但可以在某些情况下提供更准确的估计条件.
需要记住的重要一点是,这些算法只能提供频率估算.具体而言,Misra-Gries估计可以通过(n/k)项来计算实际频率.
假设您的算法只有在超过50%的时间内才能正确识别项目.将此算法提供给N个不同项目的流,然后添加一个项目x的另一个N-1个副本,总共2N-1个项目.如果算法告诉你x超过总数的50%,它必须在第一个流中; 如果没有,则x不在初始流中.为了使算法进行此确定,它必须存储初始流(或与其长度成比例的一些摘要)!因此,我们可以向自己证明这种"精确"算法所需的空间为Ω(N).
相反,这里描述的这些频率算法提供估计,识别超过阈值的任何项目,以及一些低于它的项目.例如,使用单个计数器的Majority算法将始终给出结果; 如果任何项目超过流的50%,将会找到它.但它也可能会给你一个只出现一次的项目.如果不对数据进行第二次传递,你就不会知道(再次使用一个计数器,但只查看该项目).
以下是Misra-Gries的Frequent算法的简单描述.Demaine(2002)和其他人已经对算法进行了优化,但这给了你一个要点.
指定阈值分数,1/k ; 任何超过n/k次的项目都将被找到.创建一个空地图(如红黑树); 键将是搜索项,值将是该术语的计数器.
请注意,您可以使用固定数量的存储(仅固定大小的映射)处理无限量的数据.所需的存储量仅取决于感兴趣的阈值,并且流的大小无关紧要.
在这种情况下,也许您可以缓冲一小时的搜索,并在该小时的数据上执行此过程.如果您可以在这个小时的搜索日志中进行第二次传递,您可以获得第一次传递中识别出的最高"候选人"的确切发生次数.或者,也许可以单次通过,并报告所有候选人,知道应该包含的任何项目,并且任何额外的只是噪音将在下一个小时消失.
任何真正超出感兴趣阈值的候选人都会被存储为摘要.保留这些摘要一个月的价值,每小时丢掉最旧的摘要,您将获得最常见搜索词的近似值.
Dim*_*eou 47
好吧,看起来像是一个非常多的数据,存储所有频率的成本可能过高.当数据量太大以至于我们无法将其全部存储起来时,我们就进入了数据流算法领域.
这个领域的有用书: Muthukrishnan - "数据流:算法和应用"
我从上面选择了与手头问题密切相关的参考: Manku,Motwani - "数据流的近似频率计数"[pdf]
顺便说一句,斯坦福大学的Motwani(编辑)是非常重要的"随机算法"一书的作者.本书的第11章讨论了这个问题.编辑:对不起,不好的参考,特定章节是一个不同的问题.检查后,我推荐Muthukrishnan的书第5.1.2节,在线提供.
嘿,很好的面试问题.
SiL*_*oNG 19
这是我目前正在进行的研究项目之一.要求几乎与您的要求完全一致,我们已经开发出很好的算法来解决问题.
输入
输入是无穷无尽的英语单词或短语(我们称之为tokens).
输出
这项研究的应用是在Twitter或Facebook上找到主题的热门话题或趋势.我们有一个爬网程序可以在网站上抓取,它会生成一个单词流,这些单词将输入到系统中.然后,系统将在整体或历史上输出最高频率的单词或短语.想象一下,在过去的几周里,"世界杯"这个词在Twitter上会多次出现."保罗章鱼"也是如此.:)
字符串成整数
系统具有每个单词的整数ID.虽然互联网上几乎有无限可能的单词,但在积累了大量单词之后,找到新单词的可能性变得越来越低.我们已经找到了400万个不同的单词,并为每个单词分配了一个唯一的ID.这整组数据可以作为哈希表加载到内存中,大约消耗300MB内存.(我们已经实现了自己的哈希表.Java的实现需要巨大的内存开销)
然后可以将每个短语标识为整数数组.
这很重要,因为整数的排序和比较比字符串要快得多.
存档数据
系统保留每个令牌的归档数据.基本上它是成对的(Token, Frequency).但是,存储数据的表会非常庞大,因此我们必须对表进行物理分区.一旦分区方案基于令牌的ngrams.如果令牌是单个单词,则为1gram.如果令牌是双字短语,则为2gram.这继续下去.大约4克,我们有10亿条记录,桌面大小约为60GB.
处理传入流
系统将吸收传入的句子,直到内存被充分利用(Ya,我们需要一个MemoryManager).在取N个句子并存储在存储器中之后,系统暂停,并开始将每个句子标记为单词和短语.每个标记(单词或短语)都被计算在内.
对于高频率的令牌,它们总是留在记忆中.对于频率较低的令牌,它们是根据ID排序的(记住我们将String转换为整数数组),并序列化为磁盘文件.
(但是,对于你的问题,因为你只计算单词,那么你可以把所有的词频映射只放在内存中.精心设计的数据结构只会消耗300MB内存,可以容纳400万个不同的单词.一些提示:使用ASCII char来代表字符串),这是可以接受的.
同时,一旦找到系统生成的任何磁盘文件,就会激活另一个进程,然后开始合并它.由于磁盘文件已排序,因此合并将采用类似合并排序的类似过程.这里也需要注意一些设计,因为我们希望避免过多的随机磁盘搜索.我们的想法是同时避免读取(合并进程)/写入(系统输出),并在写入不同磁盘时将合并进程从一个磁盘读取.这类似于实现锁定.
一天的结束
在一天结束时,系统将具有频率存储在存储器中的许多频繁令牌,以及存储在若干磁盘文件中的许多其他较不频繁的令牌(并且每个文件被分类).
系统将内存映射刷新为磁盘文件(对其进行排序).现在,该问题变为合并一组已排序的磁盘文件.使用类似的过程,我们将在最后获得一个已排序的磁盘文件.
然后,最后的任务是将已排序的磁盘文件合并到存档数据库中.取决于存档数据库的大小,如果足够大,算法的工作方式如下:
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
直觉是在一段时间之后,插入的数量将变得越来越小.越来越多的操作只会进行更新.此更新不会受到索引的惩罚.
希望这整个解释会有所帮助.:)