アルゴリズム問題を解く 12 - 最頻単語のリスト

問題

You are reading a sequence of strings separated by white
space from a very large stream. You are allowed to read the stream twice.
Devise an algorithm that uses only O(k) memory to identify all the words
that occur more than [n/k] times in the stream, where n is the length of the stream.
( Algorithms for interviewsより引用)

ヒント

今度は最頻出する複数の単語を調べる必要がある．しかも決められた O(k) メモリ しか利用できない．固定長のディクショナリがいいだろう．

解答

ヒントで述べたとおり，固定長のディクショナリを使う．固定長ゆえ，閾値 k 以上のエントリが入ってきた場合は最も少ない出現数のエントリをスイープする．
以下の解答は出現回数も表示するが，必ずしも正しい数字ではない．なぜなら，最終的に最頻となったエントリが計算中にスイープされている可能性があるからである．
もしO(k)メモリの縛りがなければ，スイープ無しにディクショナリを構築後，頻度の多い順にソート，上からm番目までを表示するといいだろう．ちなみに計算量はO(N)の定数時間である．

入力ファイル，入力ファイル読み込みのロジックは前回と同じ．
追加したコードは以下の通り．

void Sweep(map<string,int>* dict) {

 set<string> toRemove;

 map<string,int>::iterator iter;
 for( iter = dict->begin(); iter != dict->end();iter++ ) {
  iter->second--;
  if( !iter->second ) 
   toRemove.insert(iter->first);
 }
 set<string>::iterator sIter;
 for( sIter = toRemove.begin(); sIter != toRemove.end(); sIter++ ) {
  if( dict->find(*sIter) != dict->end() )
   dict->erase(*sIter);
 }

}

void GetPopularWords(const vector<string> v, map<string,int>* dict, int k) {

 cout << "GetPopularWords()" << endl;
 
 vector<string>::const_iterator iter;
 for( iter = v.begin(); iter != v.end();iter++ ) {
  
  if( dict->find(*iter) != dict->end() ) {
   if( dict->size() > k )
    Sweep( dict );
   else
    (*dict)[*iter] = (*dict)[*iter] + 1;
  }
  else
   (*dict)[*iter] = 1;
 }

}