アルゴリズム問題を解く 11 - 最頻単語の検索

問題

You are reading a sequence of words from a very long
stream. You know a priori that more than half the words are repetitions of
a single word W but the positions where W occurs are unknown. Design
an efficient algorithm that reads this stream only once and uses only a
constant amount of memory to identify W.
( algorithms for interview より引用)

ヒント

"A priori"を自分に有利なように解釈するのもテクニックのひとつ．

解答

ここではWの出現条件が以下を満たすものとする

• Wが最初から現れることもある
• Wがストリームスナップショットの半分以上を占める

以上の前提に基づくと，W最初からストリームスナップショットの最後まで50%以上の確率で現れることになるので，ストリームの最初からある任意の位置Mまでサンプリングを行えばほぼ確実にWを推定できる．以下のコードのAssumeMajority()はより正確性を求め，ストリームスナップショット全体をサンプリングする - O(N)．一方AssumeMajority2()は先頭から５番目の要素までサンプリングをする - O(5)．

#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

static const string FILE_PATH = "C:\\tmp\\data\\rec.txt";

void ReadFile(string& buf, string path) {

 ifstream fin(path.c_str());
 char ch;
 while( fin.good() ) {
  fin.get(ch);
  if( fin.good() )
   buf += ch;
 }
 cout << "Data loaded from " << FILE_PATH << endl;
 
}

void tokenize(vector<string>& v,const string str) {

 char *pch;
 pch = strtok(const_cast<char*>(str.c_str())," ");

 while( pch != NULL ) {
  
  v.push_back( pch );
  pch = strtok(NULL," ");

 }

}

string* AssumeMajority(const vector<string>& v) {

 cout << "@AssumeMajority()" << endl;
 int count = 0;
 vector<string>::const_iterator iter;
 string* cand = new string();
 for(iter = v.begin(); iter != v.end();iter++) {
  if( !count ) {
   *cand = *iter;
   cout << "current candidate is " << *cand << endl;
   count = 1;
  }
  else if( *iter == *cand )
   count++;
  else
   count--;
 }
 
 return cand;
 
}

string* AssumeMajority2(const vector<string> v) {

 cout << "@AssumeMajority2()" << endl;
 const int sampleMax = 5;
 int count = 0;
 string *cand = new string();
 for(int i = 0;i < sampleMax;i++ ) {
  if( !count ) {
   *cand = v[i];
   cout << "current candidate is " << *cand << endl;
   count = 1;
  }
  else if( v[i] == *cand )
   count++;
  else
   count--;
 }

 return cand;

}

void dump(const vector<string>& v) {

 vector<string>::const_iterator iter;
 for(iter = v.begin(); iter != v.end();iter++) {
  cout << *iter << " ";
 }
 cout << endl;

}

int main() { 

 string s;
 ReadFile(s,FILE_PATH);
 vector<string> v;
 tokenize(v,s);
 dump(v);
 string* pch = AssumeMajority(v);
 cout << "Majority would be .. " << *pch << endl;
 delete pch;
 pch = AssumeMajority2(v);
 cout << "Majority would be .. " << *pch << endl;
 delete pch;

 return 0;
}

入力ファイル 中身

202 200 200 200 404 200 200 200 200 200 404 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 404 200