title: Find the 'n' most repeating words/strings in a huge file that does not fit in memory
body: <p>I would like to verify my psuedocode, suggest optimizations and better approaches.</p>
  
  <p>mostRepeatingWords(int rank):<br>
  (rank here defines how many ranks you want to choose, i.e. top X most repeating words)</p>
  
  <ol>
  <li><p>External sort all files alphabetically. Following <a href="http://www.tcs.fudan.edu.cn/rudolf/Courses/Algorithms/Alg_cs_06w/Resources/cache_sort.pdf" rel="nofollow">the algorithm mentioned here</a>.<br>
  Complexity:ø (n log n/m)</p></li>
  <li><p>Create a new file "wordCount" which would contain entries like</p>
  
  <p><code>"word1" : 3</code> - i.e. word1 was repeated three times<br>
  <code>"word2" : 1</code> - i.e. word2 was unique.</p></li>
  <li><p>&nbsp;</p>
  
  <pre><code>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 &gt; page size) { 
                  write wordCount file to disk. 
                  create a new wordCount file.
           } 
  
          move to next word ie currentword + count;
      } 
  }
  </code></pre>
  
  <p>Complexity O (n + p) where n is the number of sorted pages and p &lt;= n, is number of "wordcount" pages</p></li>
  <li><p><code>checkIfDuplicateAndReturnCount()</code> is a simple function which will compare this element with first and previous etc. and determine the frequency of the word.</p></li>
  <li><p><code>sanitizeFile()</code> is used when pages are all flooded with same word. Lets say size of a page is 4KB, and let's say but number of pages, on sorting, containing the word common word "the" is greater than (4KB / size of word). Then we may need to create a new file. But sanitize file will take an extra step to combine two entries in the file for same word. Example: </p>
  
  <ul>
  <li>the : 500</li>
  <li>the : 600</li>
  </ul>
  
  <p>Would be combined to:</p>
  
  <ul>
  <li>the : 1100</li>
  </ul></li>
  <li><p>&nbsp;</p>
  
  <pre><code>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 &gt; heap.peek()) {
          heap.addAtPositionZero(word);
      }   
    }
  }
  </code></pre>
  
  <p>Complexity is O(p) </p></li>
  <li><p>Complexity: ø ( n log n / m ) + O (n + p ) + O(p) effectively :  ø ( n log n / m )</p></li>
  </ol>