ngramgraph.cc

// n-gram graph G = (V,E)
//   V: set of n-grams (i.e., n-tuple of words)
//   E: u->v iff v is a next n-gram of v in the document
//
// Usage: ./a.out < pg11.txt
// ( http://www.gutenberg.org/cache/epub/11/pg11.txt )
//
// the_march_hare 0.224377
// march_hare_said 0.04768
// march_hare_interrupted 0.02384
// march_hare_went 0.02384
// march_hare_and 0.02384
// hare_interrupted_in 0.020264
// hare_said_to 0.020264
// interrupted_in_a 0.0172244
// march_hare_had 0.01192
// march_hare_moved 0.01192
// march_hare_took 0.01192
// march_hare_meekly 0.01192
// march_hare_will 0.01192
// march_hare_was 0.01192
// hare_and_his 0.010132
// hare_said_i 0.010132
// hare_had_just 0.010132
// hare_moved_into 0.010132
// hare_went_sh 0.010132
// hare_took_the 0.010132
//
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <cmath>
#include <cstring>
#include <numeric>
#include <functional>
#include <algorithm>
#include <tr1/unordered_map>

using namespace std;
using namespace tr1;

#define ALL(c) c.begin(), c.end()
#define FOR(i,c) for(typeof(c.begin())i=c.begin();i!=c.end();++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define fst first
#define snd second

unordered_map<string, int> wordToId;
vector<string> idToWord;
vector< vector<int> > adj;

void addWord(string s) {
  if (wordToId.count(s)) return;
  int n = idToWord.size();
  wordToId[s] = n;
  idToWord.push_back(s);
  adj.push_back( vector<int>() );
}

void readFile(FILE *fp, int n) {
  string s, ngram, init;
  REP(i, n-1) init += '_';
  ngram = init;
  for (char c; (c = getchar()) != EOF; ) {
    if (isalpha(c)) {
      s += tolower(c);
    } else if (s != "") {
      string prev = ngram;
      ngram = ngram.substr(ngram.find('_')+1) + '_' + s;
      addWord(ngram);
      adj[ wordToId[prev] ].push_back( wordToId[ngram] );
      s = "";
      if (c == '.' || c == ',' || c == '?' || c == '!' || c == ':') ngram = init;
    }
  }
}

void pagerank(vector<double> b = vector<double>(adj.size(), 1), double a = 0.85) {
  vector<double> x = b;
  REP(epoch, 100) {
    vector<double> y(x.size());
    REP(u, adj.size()) {
      int d = adj[u].size();
      REP(k, d) {
        int v = adj[u][k];
        y[v] += x[u] / d;
      }
    }
    double err = 0;
    REP(u, x.size()) {
      double rhs = a*y[u] + (1-a)*b[u];
      err += pow(x[u]-rhs, 2);
      x[u] = rhs;
    }
    err = sqrt(err);
    if (err < 1e-6) break;
  }
  double total = 0;
  REP(u, x.size()) total += x[u];
  REP(u, x.size()) x[u] /= total;

  vector< pair<double, int> > rank;
  REP(u, x.size()) rank.push_back( make_pair(x[u], u) );
  sort(ALL(rank), greater< pair<double,int> >());
  REP(k, min(rank.size(), 20u)) {
    string word = idToWord[rank[k].snd];
    double score = rank[k].fst;
    cout << word << " " << score << endl;
  }
}
int main() { 
  readFile(stdin, 3);
  vector<double> b(adj.size());
  b[ wordToId["the_march_hare"] ] = 1;
  pagerank(b);
}