algorithm - 如何从超过 1TB 的数据中打印频率为 k 的词？

Question

这个问题是在我的面试中被问到的。我想知道解决方案。

给一个文本文件，每行一个单词，文件大小超过 1TB。任务是仅打印文件中频率为 k 的词。

我没有完全回答这个问题。但我想，我以正确的方式开始了它。您使用了散列技术并且代码至少需要 O(n) 时间(因为它必须读取整个文件)

任何人都可以回答我谁可以有效地完成这项工作。

Answer 1

一般来说，这类问题是“Top K”或“选择”算法的主题。这是一篇关于一般主题的维基百科文章:Wikipedia: Selection algorithm .它似乎在“大数据”系统中普遍流行，并且可能会通过上一代专注于排序算法的面试，而那时每个认真的候选人都已经记住了快速排序和堆排序代码。

作为一个实际问题，这只是关于构建“大数据”(Hadoop 和其他 Map/Reduce 系统)的教科书问题。如果数据分布在 N 个节点上，那么每个节点都可以计算单独的部分直方图(将它们的直方图函数映射到整个数据集)并合并它们的结果(将它们的小计减少为总计)。

对于面试场景，这是一个很受欢迎的问题，因为没有简单的技巧。您可以列举学术文献中已发表的几种方法，也可以从头解决问题。

如果“词汇量”相对较小(例如，典型的英语词典中只有几万个单词——所以 25 万个单词的词汇量相当广泛)。在那种情况下，我们希望计数可以适合典型现代硬件的 RAM。如果这个数据集中的“词”更广泛——超过数千万或数亿——那么这种方法就不再可行了。

可以想象，人们可以尝试一种自适应或统计方法。如果我们知道没有任何单个“单词”的主要集群......数据集的任何统计显着样本与任何其他样本大致相似......那么我们可以构建直方图并丢弃那些“单词”(和他们的数量)，这比其他的要少得多。如果数据仅以流的形式呈现，并且我们没有得到任何有关术语分布的硬性保证，那么这不是一种可行的方法。但是，如果我们在某个随机访问文件系统中拥有数据，那么我们可能会稀疏随机地对数据集进行采样，以构建一个很有可能的前 K * M 集合(其中 M 是我们所需的任意倍数K 个元素，使其全部适合 RAM)。

散列可以帮助我们找到每个单词的计数器，但如果我们试图只保留散列的计数而不将“单词”本身保留在数据结构中，我们必须考虑发生冲突的可能性。总的来说，我认为堆会更好(可能包括将内存堆底部的东西放到存储堆或 trie 中)。

我之前说“自适应”是因为可以使用缓存(最终是统计建模)将当前最频繁的“单词”保留在 RAM 中，并将最不频繁的“单词”混洗到存储中(以防止某些退化的数据集，这些数据集最初是频繁出现的“单词”让位于一些最初不常见的单词，随着人们对数据集的深入挖掘，这些单词变得更加频繁。

虽然对这些考虑因素的对话探索在某些采访中可能会很有效，但我建议您熟悉我引用的维基百科文章的各个部分，这样您就可以勾勒出伪代码至少一个或其中两个，并表明您确实具有该 Material 的一些学术背景。

绝对不要忽视在提出“Top K”类问题的采访中讨论分布式处理。即使只是为了澄清所提出问题的局限性，并承认此类问题一直是现代“大数据”分布式处理系统的驱动力，也要这样做。

还有一个关于同一主题的问题:StackOverflow: The Most Efficient Way To Find Top K Frequent Words In A Big Word Sequence .