在5 5GB文件中查找k个最常用单词的部分堆排序

Question

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

我想使用hash来存储单词的频率，使用min-heap来存储最频繁的单词，并在遍历单词时相应地调整min-heap。我想这应该需要O(nlogk)。如果我有太多的数据要存储在内存中，我的算法需要如何改变。这是一个我很难理解的问题，不仅仅是这个特定的问题，我只是给出上下文，以便它可能有助于解释。

Answer 1

我认为，如果不将整个文件放在内存中(或者进行某种代价高昂的合并排序)，就没有确定性的方法可以做到这一点。

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

这个算法和其他算法在this library中都有很好的实现。

解释合并排序的事情:如果您的文件已经排序，您可以很容易地找到k最频繁的最小堆。是的，当你发现一个更有竞争力的词时，最小堆能够丢弃频率较低的词。您可以这样做，因为您可以知道当前单词的频率，而不必读取整个文件。如果你的文件是未排序的，你必须保留一个完整的列表，因为最频繁的术语可能会出现在文件中的任何地方，并且很快就会因为“非竞争性”而被丢弃。

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

Answer 2

在你的评论后面添加了你需要计算频率的内容。

你不会说你期望的数据中有多少个单词，或者一个单词的组成。如果它是英文文本，我会惊讶地看到50万个单词。当然，5 of的文本中肯定不会有10亿个单词。但是，无论有多少单词，这种技术都不会真正改变。

首先构建一个包含键值对的字典或散列映射: word、count。当你读每个单词的时候，查查字典。如果它在那里，就增加它的数量。如果不存在，则使用计数1将其相加。

如果你有大量的内存或相对较少的单词，它们都可以放入内存中。如果是这样的话，你可以做我下面描述的堆事情。

如果内存已满，则只需将键值对写出到一个文本文件中，每行一个单词，如下所示：

word1, count
word2, count

然后清空你的字典，继续下去，增加单词或增加它们的数量。根据需要对每个单词块重复操作，直到到达输入的末尾。

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

一旦文件按word排序，您将拥有：

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

现在只需按顺序遍历文件，累加单词计数。在每个分词时，根据堆检查其计数，如下所述。

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

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

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

Answer 3

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

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