3

我知道我想使用什么算法，但想知道我必须改变什么，因为文件太大了。

我想使用散列来存储单词的频率，并使用最小堆来存储最常见的单词，并在我遍历单词时相应地调整最小堆。我认为这应该需要 O(nlogk)。如果我有太多数据要存储在内存中，我的算法需要如何更改。这是一个我一般难以理解的问题，不仅针对这个特定问题，而且我只是提供上下文，以便它可能有助于解释。

4

3 回答 3

4

我认为如果没有将整个文件放在内存中（或进行某种昂贵的合并排序），就没有确定的方法可以做到这一点。

但是有一些很好的概率算法。看看Count-Min Sketch。

在这个库中有一个很好的实现这个和其他算法。

解释合并排序的事情：如果您的文件已经排序，您可以使用最小堆轻松找到最频繁的 k。是的，当您发现一个更具竞争力的术语时，能够丢弃不太频繁的术语的最小堆。您可以这样做，因为您无需阅读整个文件即可知道当前单词的频率。如果您的文件未排序，则必须保留整个列表，因为最常用的术语可能会出现在文件中的任何位置，并且过早地被视为“非竞争性”而被丢弃。

您可以很容易地在有限内存的情况下进行合并排序，但这是一个 I/O 密集型操作，可能需要一段时间。实际上，您可以使用任何类型的External Sort。

于 2013-02-26T21:02:40.440 回答
4

在您需要计算频率的评论之后添加。

你没有说你期望在数据中有多少个单词，或者什么构成一个单词。如果是英文文本，我会惊讶地看到 50 万字。在 5 GB 的文本中肯定不会有 10 亿个单词。但是无论有多少单词，技术并没有真正改变。

您首先构建一个包含键值对的字典或哈希映射：单词、计数。当你阅读每个单词时，在字典中查找它。如果它在那里，增加它的数量。如果不存在，则将其添加为 1。

如果你有很多记忆或相对较少的单词，它都会适合记忆。如果是这样，您可以执行我在下面描述的堆操作。

如果您的内存已满，那么您只需将键值对写入文本文件，每行一个单词，如下所示：

word1, count
word2, count

然后清理你的字典并继续，添加单词或增加它们的计数。根据需要对每个单词块重复，直到您到达输入的末尾。

现在您有一个包含单词/计数对的巨大文本文件。按单词排序。有许多外部排序工具可以做到这一点。想到的两个是 Windows SORT 实用程序和 GNU 排序。两者都可以轻松地对非常大的短行文件进行排序。

文件按单词排序后，您将拥有：

word1, count
word1, count
word2, count
word3, count
word3, count
word3, count

现在只需按顺序浏览文件，累积单词计数就很简单了。在每个单词中断处，按如下所述检查其对堆的计数。

整个过程需要一些时间，但效果很好。您可以通过对单词块进行排序并将它们写入单个文件来加快速度。然后，当您到达输入的末尾时，您对几个块进行 N 路合并。这更快，但迫使你编写一个合并程序，除非你能找到一个。如果我这样做一次，我会选择简单的解决方案。如果我经常这样做，我会花时间编写自定义合并程序。

在你计算出频率之后......

假设您的文件包含单词及其频率，并且您要做的就是获取k频率最高的单词，那么是的，它是 O(n log k)，并且您不必将所有项目存储在内存中。您的堆只需要 k 个项目。

想法：

heap = new minheap();
for each item
    // if you don't already have k items on the heap, add this one
    if (heap.count < k)
        heap.Add(item)
    else if (item.frequency > heap.Peek().frequency)
    {
        // The new item's frequency is greater than the lowest frequency
        // already on the heap. Remove the item from the heap
        // and add the new item.
        heap.RemoveRoot();
        heap.Add(item);
    }

处理完每个项目后，堆中将包含k频率最高的项目。

于 2013-02-26T21:36:56.033 回答
0

您可以使用选择算法 ( http://en.wikipedia.org/wiki/Selection_algorithm ) 来计算第 k 个最大数。然后进行线性扫描，只选择 k 个大数。

在实践中，您可能希望从 kth min false 的估计范围开始，然后从那里继续。例如。读取前 M 个数字并计算 M 个数字中的估计 kth max = (k*M/N)th max。如果您认为数据有偏差（即部分排序），那么随机选择那些 M 个数字。

于 2013-02-26T21:37:39.873 回答