在内存无法容纳的大文件中查找“n”个最重复的单词/字符串

我想验证我的伪代码，建议优化和更好的方法。

最重复的单词（按排名）：
（此处的排名定义了您要选择的排名，即前 X 个最重复的单词）

1. 外部按字母顺序对所有文件进行排序。下列的这里提到的算法 http://www.tcs.fudan.edu.cn/rudolf/Courses/Algorithms/Alg_cs_06w/Resources/cache_sort.pdf.
   复杂度：ø (n log n/m)

2. 创建一个新文件“wordCount”，其中包含类似的条目

   "word1" : 3- 即 word1 重复了 3 次
   "word2" : 1- 即 word2 是唯一的。

3.  

   for ( read each of the sorted file one by one ) { 
       for (read each "word" in the current file) { 
           int count =  checkIfDuplicateAndReturnCount(); 
           enter "word" and "count" in the "wordCount" file. 
   
           sanitizeFile(); 
   
           if  (wordCount file is > page size) { 
                   write wordCount file to disk. 
                   create a new wordCount file.
            } 
   
           move to next word ie currentword + count;
       } 
   }
   

   复杂度 O (n + p)，其中 n 是已排序页面的数量，p

4. checkIfDuplicateAndReturnCount()是一个简单的函数，它将将此元素与第一个和前一个等进行比较，并确定单词的频率。

5. sanitizeFile()当页面上充斥着相同的单词时使用。假设一个页面的大小为 4KB，并且假设在排序时包含单词“the”的页面数量大于（4KB / 单词大小）。那么我们可能需要创建一个新文件。但是清理文件将采取额外的步骤来合并文件中同一单词的两个条目。例子：

   • : 500
   • : 600

   将合并为：

   • : 1100

6.  

   for  (reading the all the wordcount files one by one ) {
     for (each word in the wordcount) {
       Use a minimum heap / priority queue of size "rank" to keep track of the frequency.
       if (wordcount > heap.peek()) {
           heap.addAtPositionZero(word);
       }   
     }
   }
   

   复杂度为 O(p)

7. 复杂度： ø ( n log n / m ) + O (n + p ) + O(p) 有效： ø ( n log n / m )

无需提前对文件进行排序。这样做只是一堆不必要的 I/O。

更直接的方法是：

Create an empty dictionary (hash map), keyed by word. The value is the count.
for each file
    while not end of file
        read word
        if word in dictionary
            update count
        else
            if dictionary full
                sort dictionary by word
                output dictionary to temporary file
                Clear dictionary
            Add word to dictionary, with count 1
    end
end
if dictionary not empty
    sort dictionary by word
    output dictionary to temporary file

您现在拥有一定数量的临时文件，每个文件均按单词排序，并且每行包含一个单词/计数对。喜欢：

aardvark,12
bozo,3
zebra,5

创建一个最小堆，用于保存 n 个最大的项目。叫它largest_items.

做一个标准n路合并 https://stackoverflow.com/questions/5055909/algorithm-for-n-way-merge这些临时文件。当您找到每个唯一的项目时（即合并多个文件中的所有“aardvark”条目），您可以执行以下操作：

if (largest_items.count < n)
    largest_items.add(word)
else if (word.count > largest_items.peek().count)
{
    // the count for this word is more than the smallest count
    // already on the heap. So remove the item with the
    // smallest count, and add this one.
    largest_items.remove_root()
    largest_items.add(word)
}

复杂：

• 构建字典的时间复杂度为 O(N)，其中N是文件中单个单词的总数。
• 对每个临时字典进行排序的时间复杂度为 O(k log k)，其中“k”是字典中的单词数。
• 编写每个临时字典的时间复杂度为 O(k)
• 合并的时间复杂度为 O(M log x)，其中M是所有临时文件的条目总数，并且x是临时文件的数量。
• 选择项目的时间复杂度为 O(m log n)，其中m是唯一单词的数量，并且n是您要选择的字数。

如果您考虑最坏情况的行为（即所有单词都是唯一的），则复杂性为（n是总字数）：

• 构建字典的时间复杂度为 O(n)
• 排序并写入临时文件是(n/m) * (m log m), where m是字典的大小。
• 合并是n log (n/m).
• 选择是 O(m + (k log k))，其中k是您要选择的单词数，m是唯一单词的数量。因为所有单词都是唯一的，所以它们具有相同的计数，所以你只会这样做k插入到堆中。这m当术语占主导地位时k远小于m（在这些情况下通常是这种情况）。所以选择的时间复杂度为 O(m)。

当您处理大于内存的数据集时，瓶颈通常是文件 I/O。我上面概述的算法尝试最小化 I/O。在最坏的情况下（所有单词都是唯一的），每个单词将被读取两次并写入一次。但在一般情况下，每个单词被读取一次，然后每个哈希页被写入一次并读取一次。另外，您的排序是在哈希页面而不是原始单词上进行的，并且临时文件的总大小将比原始文本小得多。