在大词序列中找到前K个频繁词的最有效方法

Question

输入：正整数K和大文本。实际上，文本可以被视为单词序列。因此，我们不必担心如何将其分解为单词序列。

输出：文本中最常见的K字。

我的想法是这样的。

使用哈希表来记录所有单词的频率，同时遍历整个单词序列。在此阶段，键是“字”，值是“字频”。这需要O（n）时间。

对（字，字 - 频率）对进行排序; 关键是“字频”。这需要使用正常排序算法的O（n * lg（n））时间。

排序后，我们只取第一个K字。这需要O（K）时间。

总而言之，总时间是O（n + n lg（n）+ K），因为K肯定小于N，所以它实际上是O（n lg（n））。

我们可以改善这一点。实际上，我们只想要前K个词。换句话说，频率对我们来说并不重要。因此，我们可以使用“部分堆排序”。对于步骤2）和3），我们不仅仅进行排序。相反，我们改变它

2'）构建一堆（word，word-frequency）对，以“word-frequency”为关键。构建堆需要花费O（n）时间;

3'）从堆中提取前K个单词。每次提取为O（lg（n））。所以，总时间是O（k * lg（n））。

总而言之，该解决方案花费时间O（n + k * lg（n））。

这只是我的想法。我还没有找到改进步骤1）的方法。

我希望一些信息检索专家可以对这个问题有所了解。

Answer 1

你不会比你描述的解决方案获得更好的运行时间。你必须至少做O（n）工作来评估所有的单词，然后O（k）额外的工作来找到前k个术语。如果您的问题集非常大，则可以使用分布式解决方案，例如map / reduce。n个映射工作者在每个文本的1 / n处计算频率，并且对于每个单词，将其发送给基于单词的散列计算的m个reducer工作者中的一个。然后减速器将计数相加。对减速器输出的合并排序将为您提供最流行的单词，以便受欢迎。