0

这个问题在我的采访中被问到。我想知道解决方案。

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

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

谁能回答我这可以有效地完成。

4

2 回答 2

5

一般来说，这类问题是“Top K”或“选择”算法的主题。这是关于一般主题的维基百科文章：维基百科：选择算法。它似乎已经在“大数据”系统中流行起来，也许是为了克服上一代面试的重点，这些面试专注于排序算法，早在每个认真的候选人都记住快速排序和堆排序代码的时候。

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

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

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

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

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

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

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

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

这里还有一个关于相同主题的问题：StackOverflow: The Most Efficient Way To Find Top Kfrequent Words In A Big Word Sequence。

于 2013-04-06T08:46:22.193 回答
0

这个问题的答案完全取决于唯一单词的大小，如果唯一单词计数很小，那么您可以使用任何字符串->数字映射数据结构（例如 Trie 树）来计算单词频率。复杂度将是n log(m)（m 是单个单词的长度），易于实现。但是描述问题的方式，很可能唯一的字数足够大，可以存储在内存中。在这种情况下，可以使用以下方法：

1 TB 数据意味着输入文件中有大约1.0*10^12字节的数据。1 个字节是一个字符，平均而言，一个单词有 4 个字符，然后我们有大约2.5*10^11单词。我们将把这个词表分成50k不同的词表。因此，每次我们5m从输入文件中读取未读单词时，对这个5m单词列表进行排序并将这个排序列表写入一个文件。我们将使用50k数字数组（让我们称之为Parray）来存储文件中所有排序列表的起始位置（最初Parray将有数字，如：0、5m+1、10m+1 等）。现在从所有列表中读取最上面的50k单词，将它们放在一个最小堆中，你会得到堆顶部的最小单词。得到当前最小的单词后（让我们称之为cur_small) 从所有排序列表中读出每个列表中的单词（在此操作之后，您Parray将指向每个列表中的下一个最小单词）。在这里，您将获得cur_small- 的计数，因此做出决定，K然后从堆中删除所有条目，cur_small最后将每个列表中的一个新单词添加到至少一个单词所在的堆中cur_small。继续此过程，直到您读出所有排序列表。在所有的复杂性是n log(n)

于 2013-04-06T10:15:55.263 回答