<分区>
我知道这个问题已经在论坛上被问过几次了，我没有找到任何可以被认为是最合适的解决方案的“已标记”答案 - 所以再次询问:
我们从书中得到了非常大的文本，所有这些文本都无法容纳在内存中。我们需要找到文本中出现频率最高的前 10 个词。执行此操作的最佳(时间和空间)方式是什么？
我的想法:
将文件分成k大小的 block (这样每个 block 都可以存储在内存中)。现在，对每个 block 执行外部排序。一旦我们在磁盘上有了 (N/k)- 排序的文件(假设 N 是书中文本的总大小)——我不确定我应该如何继续才能从中获得前 10 个元素k 排序数组。
另外，如果有不同的思路，欢迎提出。
最佳答案
这是流式算法领域的经典问题。在某些退化的情况下，显然没有办法做到这一点；您需要满足一堆元素，这些元素大约(在明确定义的意义上)流中的前 k 个词。我不知道任何经典引用资料，但快速谷歌将我带到 this .它似乎对流式传输 top-K 的各种技术进行了很好的调查。您可以查看其中的引用资料以了解其他想法。
另一个想法(并且在流模型中不适用)只是随机抽取尽可能多的单词以适合内存，对它们进行排序和唯一化，然后再通过文件计算命中率示例中的单词。然后你可以很容易地找到前k。
关于algorithm - 在一本大书中找到 10 个最常用的单词，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17541983/