:此算法存在问题,特别是递归合并列表使其成为多项式运行时算法。但我将其作为有缺陷的算法的示例留在这里。
您不能丢弃数据块中的任何单词,因为一个单词可能仅在一个数据块中存在100次,而另一个单词在100个不同的数据块中每个存在一次。
但是您仍然可以以类似于MapReduce算法的方式使用块。您将每个块映射到一个单词列表(包括计数),然后通过将单词列表递归合并为一个单词来减少。
在映射步骤中,将每个单词映射到每个块的计数。按 字母顺序排序 ,而不是按计数排序,然后将列表存储到磁盘。现在,您可以线性地成对合并列表,而不必在内存中保留两个以上的单词: