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

Question

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

我想使用散列来存储单词的频率，并使用最小堆来存储最频繁的单词，并相应地调整最小堆，因为我通过单词循环。我认为这应该是O（nlogk）。如果我有太多数据要存储在内存中，我的算法如何更改？这是一个我一般无法理解的问题，不仅仅是针对这个特定的问题，而是我给出的上下文，以便它可以帮助解释。

Answer 1

我认为没有确定性的方式来做到这一点，没有在内存中的整个文件（或进行一些昂贵的合并排序）。

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

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

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

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

Answer 2

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

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

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

如果您有很多内存或相对较少的字词，它们都会适合内存。如果是这样，你可以做下面描述的堆事情。

如果你的内存已满，那么你只需写入键值对出到一个文本文件，每行一个字，就像这样：

word1, count 
word2, count 

然后清除你的字典里，继续向前，将单词或增加他们的数量。根据需要对每个字块重复操作，直到达到输入的结尾。

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

一旦文件被字排序，你必须：

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

现在它是通过文件顺序去，积累计数的话一件简单的事情。在每个单词中断处，按照下面的描述检查堆数。

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

你计算出的频率后...

假设你的文件中包含的单词和他们的频率，以及所有你想要做的就是让k话最高频率，然后是它的为O（n日志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项目具有最高频率。

Answer 3

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

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