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

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

您不能丢弃数据块中的任何单词，因为一个单词可能仅在一个数据块中存在100次，而另一个单词在100个不同的数据块中每个存在一次。

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

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

1. 假设A和B为要合并的列表文件，R为结果文件
2. 从A读取一行带有单词+计数的单词，然后调用该单词

   a

3. 从B中读一行带有单词+计数的单词

   b

4. 按字母顺序比较单词：
   • 如果

     a

     =

     b

     ：
   • 求和
   • 将单词和新计数写到R
   • 转到2
   • 如果

     a

     >

     b

     ：
   • 将

     b

     其计数写入R

   • b

     从B 读换行
   • 转到4
   • 如果

     a

     <

     b

     ：
   • 将

     a

     其计数写入R

   • a

     从A 读换行
   • 转到4

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