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

输入:正整数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)的方法.
我希望一些信息检索专家可以更多地了解这个问题.

1> Chihung Yu..：

---

这可以在O(n)时间内完成

解决方案1:

脚步:

计算单词并对其进行哈希处理,这将最终出现在这样的结构中

var hash = {
  "I" : 13,
  "like" : 3,
  "meow" : 3,
  "geek" : 3,
  "burger" : 2,
  "cat" : 1,
  "foo" : 100,
  ...
  ...

遍历散列并找到最常用的单词(在本例中为"foo"100),然后创建该大小的数组

然后我们可以再次遍历哈希并使用单词出现次数作为数组索引,如果索引中没有任何内容,则创建一个数组,否则将其附加到数组中.然后我们最终得到一个数组:

  0   1      2            3                  100
[[ ],[cat],[burger],[like, meow, geek],[]...[foo]]

然后只是从末尾遍历数组,并收集k个单词.

解决方案2:

脚步:

与上述相同

使用min heap并将min heap的大小保持为k,对于hash中的每个单词,我们将单词的出现与min进行比较,1)如果它大于min值,则删除min(如果min的大小) heap等于k)并在最小堆中插入数字.2)休息简单的条件.

遍历数组后,我们只需将最小堆转换为数组并返回数组.

---

您的解决方案(1)是替换标准O(n lg n)比较排序的O(n)桶排序.您的方法需要额外的空间用于铲斗结构,但可以在适当的位置进行比较.您的解决方案(2)在时间O(n lg k)中运行 - 也就是说,O(n)迭代所有单词,O(lg k)将每个单词添加到堆中.

---

第一种解决方案确实需要更多空间,但重要的是要强调它实际上是O(n)的时间.1:以字为单位的哈希频率,O(n); 2:遍历频率哈希,创建频率键入的第二个哈希值.这是遍历散列的O(n)和O(1)以在该频率的单词列表中添加单词.3:从最大频率向下遍历哈希,直到你达到k.最多,O(n).总= 3*O(n)= O(n).

---

通常在对单词进行计数时,解决方案1中的存储桶数量被广泛高估(因为最常见的单词比第二个和第三个更频繁),因此您的数组稀疏且效率低下.

2> Nick Johnson..：

---

你不会比你描述的解决方案获得更好的运行时间.你必须至少做O(n)工作来评估所有的单词,然后O(k)额外的工作来找到前k个术语.

如果您的问题集非常大,则可以使用分布式解决方案,例如map/reduce.n个映射工作者在每个文本的1/n处计算频率,并且对于每个单词,将其发送给基于单词的散列计算的m个reducer工作者中的一个.然后减速器将计数相加.对减速器输出的合并排序将为您提供最流行的单词,以便受欢迎.

3> 小智..：

---

如果我们不关心排名前K,那么你的解决方案的一个小变化产生O(n)算法,如果我们这样做,则产生O(n + k*lg(k))解.我相信这两个边界在一个恒定因子内是最佳的.

在我们遍历列表并插入哈希表之后,这里再次进行优化.我们可以使用中位数算法算法来选择列表中的第K个最大元素.该算法可证明是O(n).

选择第K个最小元素后,我们就像在quicksort中一样对该元素进行分区.这显然也是O(n).枢轴"左"侧的任何东西都在我们的K元素组中,所以我们已经完成了(我们可以简单地扔掉其他所有东西).

所以这个策略是:

浏览每个单词并将其插入哈希表:O(n)

选择第K个最小元素:O(n)

围绕该元素的分区:O(n)

如果要对K个元素进行排名,只需在O(k*lg(k))时间内使用任何有效的比较排序对它们进行排序,得到总运行时间为O(n + k*lg(k)).

O(n)时间界限在常数因子内是最佳的,因为我们必须至少检查一次每个单词.

O(n + k*lg(k))时间界限也是最佳的,因为没有基于比较的方式来在小于k*lg(k)时间内对k个元素进行排序.

---

您将无法在哈希表上运行"中位数中位数",因为它会进行交换.您必须将哈希表中的数据复制到临时数组.因此,将需要O(n)存储.

4> Aaron Maenpa..：

---

如果您的"大单词列表"足够大,您可以简单地抽样并获得估算值.否则,我喜欢哈希聚合.

编辑:

通过样本我的意思是选择一些页面子集并计算这些页面中最常用的单词.如果您以合理的方式选择页面并选择具有统计意义的样本,则您对最常用单词的估计应该是合理的.

如果您拥有如此多的数据来处理这一切只是一种愚蠢的行为,那么这种方法实际上是合理的.如果你只有几个megs,你应该能够撕掉数据并计算一个确切的答案,而不必费力而不是费心去计算估计.