在一本大书中找出10个最常用的单词

Question

我知道这个问题在论坛上已经被问过几次了，我没有找到任何可以被认为是最合适的解决方案的"TAGGED"答案，所以再次问：

我们收到了一本很大的书中的文本，所有这些都无法进入记忆。我们被要求找出文本中出现频率最高的10个单词。做这件事的最佳（时间和空间）方式是什么？

我的想法：

将文件划分为k个相当大的块（这样每个块都可以存储在内存中）。现在，对每个块执行外部排序。一旦我们在磁盘上有了（N/k）排序的文件（假设N是书中文本的总大小），我不确定该如何继续，以便从k排序的数组中获得前10个元素。

此外，如果有不同的思路，请提出建议。

Answer 1

这是流算法领域的一个经典问题。显然，在某些退化的情况下，没有办法做到这一点；您需要满足于一堆元素，这些元素大约（在定义良好的意义上）是流中的前k个单词。我不知道有什么经典的参考文献，但一个快速的谷歌让我了解了这一点。它似乎对流媒体top K的各种技术进行了很好的调查。你可以查阅其中的参考资料以了解其他想法。

另一个想法（也是流媒体模型中没有的想法）就是随机抽取尽可能多的单词放入内存，对它们进行排序和uniq，然后对文件进行另一次遍历，计算样本中单词的命中率。然后你可以很容易地找到顶部的k。

Answer 2

编辑：此算法存在问题，特别是递归合并列表使其成为多项式运行时算法。但我将把它作为一个有缺陷的算法的例子留在这里。

---

你不能从你的区块中丢弃任何单词，因为可能有一个单词只在一个区块中存在100次，而另一个单词在100个不同的区块中每一个都存在一次。

但您仍然可以使用块，其方式类似于MapReduce算法。您将每个区块映射到单词列表（包括计数），然后通过递归地将单词列表合并为一个单词列表来减少。

在映射步骤中，将每个单词映射到每个块的计数。按字母顺序排序，而不是按计数排序，并将列表存储到磁盘中。现在，您可以成对线性合并列表，而无需在内存中保留两个以上的单词：

1. 设A和B是要合并的列表文件，R是结果文件
2. 从A中读取一行单词+count，调用单词a
3. 从B中读取一行单词+count，调用单词b
4. 按字母顺序比较单词：
   • 如果a=b：
     • 求和他们的计数
     • 将单词和新计数写为R
     • 转到2
   • 如果a>b：
     • 将包含计数的b写入R
     • 从B读取新行b
     • 转到4
   • 如果a<b：
     • 将包含计数的a写入R
     • 从a读取新行a
     • 转到4

继续进行此成对合并，直到所有文件都合并到一个列表中。然后你可以扫描一次结果列表，并保留十个最频繁的单词。