在5GB的文件中使用部分堆排序来查找出现最频繁的k个单词

Question

我知道我想要使用的算法，但由于文件太大，想知道需要做哪些更改。我想使用哈希表来存储单词的频率，并使用小根堆来存储最常见的单词，并在遍历单词时相应地调整小根堆。我认为这应该需要 O(nlogk) 的时间复杂度。如果我的数据量过大无法存储在内存中，我的算法需要如何更改？我通常很难理解这个问题，不仅仅是针对这个具体问题，但我提供背景信息以帮助解释。

- user1136342

---

内存映射文件怎么样？这是一个选项吗？ - Justin

你是在问如何计算单词频率并选择出现频率最高的单词吗？还是只是想知道在计算了频率之后如何选择出现最频繁的单词？ - Jim Mischel

计算单词频率并选择具有最高频率的单词。 - user1136342

Answer 1

我认为在不将整个文件加载到内存中(或进行一些昂贵的归并排序)的情况下，没有确定性的方法可以做到这一点。

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

这里有一个很棒的实现，包括其他算法，这个库。

解释一下归并排序的事情：如果您的文件已经排序，您可以使用最小堆相对容易地找到k个最频繁的词。是的，使用最小堆可以丢弃较不常见的词汇，以便在发现更具竞争力的词汇时舍弃它。这样做是因为你可以知道当前单词的频率，而无需读取整个文件。如果文件未排序，则必须保留整个列表，因为最常用的术语可能出现在文件的任何位置，并且会被过早地丢弃为“非竞争性”。

您可以使用有限的内存轻松地进行合并排序，但这是一项I/O密集型操作，可能需要一段时间。实际上，您可以使用任何一种外部排序。

- Juan Lopes

---

我不经常处理大量数据，所以我很难理解与之相关的问题-对我来说，似乎我只需要一次读取文件的一小部分，但我知道我缺少了什么。你说没有确定性的方法可以做到这一点，但我不明白为什么，因为我很难看到每种情况下数据处理的确切差异。你能详细说明一下吗？ - user1136342

@user1136342 扩展了答案，使其更具体地涉及到了排序部分。 - Juan Lopes

Answer 2

根据您的评论，您需要计算频率。

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

首先要建立一个包含键值对（单词、计数）的字典或哈希表。读取每个单词时，在字典中查找它。如果存在，则增加其计数。如果不存在，则将其添加到字典中，并设置计数为1。

如果您拥有大量内存或相对较少的单词，则所有内容都可以放入内存中。如果是这样，您可以按照下面描述的方法进行堆排序。

如果您的内存填满了，则只需将键值对写入文本文件中，每行一个单词，像这样：

word1, count
word2, count

接下来，清空字典并继续添加单词或增加它们的计数。对于每个单词块，重复此操作直到输入结束。

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

一旦按单词排序，你将得到：

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项。

- Jim Mischel

Answer 3

你可以使用选择算法（http://en.wikipedia.org/wiki/Selection_algorithm）来计算第k大的数字。然后进行线性扫描并仅选择k个大数字。

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

- ElKamina