我知道这个问题已经在论坛上被问过几次了，我没有找到任何可以被认为是最合适的解决方案的“标记”答案 - 所以再次询问：
我们从书中得到了一篇非常大的文本，所有这些文本都无法放入内存中。我们需要找到文本中出现频率最高的 10 个单词。做到这一点的最佳（时间和空间）方式是什么？
我的想法：
将文件划分为 k 个大小的块（使得每个块都可以存储在内存中）。现在，对每个块执行外部排序。一旦我们在磁盘上有了 (N/k) 个排序的文件（假设 N 是书中文本的总大小） - 我不知道应该如何继续，以便我可以从文件中获取前 10 个元素k 排序数组。
另外，如果有不同的思路，欢迎提出。
这是流算法领域的一个经典问题。显然，在某些退化情况下，没有办法做到这一点。您需要选择一堆大约（在明确定义的意义上）流中前 k 个单词的元素。我不知道任何经典参考文献，但快速谷歌让我找到了this。它似乎对流媒体 top-K 的各种技术进行了很好的调查。您可以查看其中的参考资料以获取其他想法。
另一种想法（在流模型中行不通）就是随机采样内存中尽可能多的单词，对它们进行排序和唯一化，然后对文件进行另一次传递，计算单词的命中数你的样品。然后你就可以轻松找到前k个了。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
