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

  • Z时代
  • 2024-01-10
  • 分类：问答

我知道这个问题已经在论坛上被问过两次，我没有找到任何可以认为是最合适的解决方案的“ TAGGED”答案-因此请再次提出：

书中给我们提供了非常大的文字，所有这些文字都无法放入记忆中。我们需要找到文本中最常见的10个单词。这样做的最佳方式（时间和空间）是什么？

我的想法：

将文件分为k个可调整大小的块（这样每个块都可以存储在内存中）。现在，对每个块执行外部排序。一旦我们将（N /

k）-排序的文件放在磁盘上（假设N是书中文本的总大小）-我不确定该如何继续才能从中获得前10个元素k个排序的数组。

另外，如果有不同的想法，请提出建议。

回答：

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

您不能丢弃数据块中的任何单词，因为一个单词可能仅在一个数据块中存在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

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

以上是 在一本大书中找到10个最常用的词 的全部内容， 来源链接： utcz.com/qa/406800.html

回到顶部