ngramsgraph.cc

// n-grams graph G = (V,E)
//   V: set of n-grams (i.e., n-tuple of words for n = 1 .. N )
//   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 )
//
#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

typedef string NGram; // separated by _ (underscore)
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 addEdge(string s, string t) {
  addWord(s);
  addWord(t);
  adj[ wordToId[s] ].push_back( wordToId[t] );
}

void addSentense(vector<string> sentense) {
  int nmax = 4;
  int l = sentense.size();
//  REP(i, l) cout << sentense[i] << " "; cout << endl;
  for (int p = 0; p+1 < l; ++p) { // word1 word2 
    vector<string> prev;
    prev.push_back(sentense[p]);
    for (int i = 1; i < nmax && p-i >= 0; ++i) 
      prev.push_back( sentense[p-i] + " " + prev.back() );

    string next = sentense[p+1];
    FOR(s, prev) addEdge(*s, next);
    for (int i = 1; i < nmax && p+1+i < l; ++i) {
      next = next + " " + sentense[p+1+i];
      FOR(s, prev) addEdge(*s, next);
      //FOR(s, prev) REP(k, i+1) addEdge(*s, next);
    }
  } 
}

void readFile(FILE *fp, int n) {
  vector<string> sentense;
  string s;
  for (char c; (c = getchar()) != EOF; ) {
    if (isalpha(c)) {
      s += tolower(c);
    } else if (s != "") {
      sentense.push_back(s);
      s = "";
      if (c == '.' || c == ',' || c == '?' || c == '!' || c == ':') {
        addSentense(sentense);
        sentense.clear();
      }
    }
  }
}

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(), 200u)) {
    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["cat"] ] = 1;
  pagerank(b);
  //pagerank();
}