tests/shortestpath.cpp

   1 #include "spell.h"
   2 #include <iostream>
   3 #include "sentence.h"
   4
   5 using namespace std;
   6
   7 class HeapValue : public vector<float> {
   8 public:
   9   bool operator() (int v1,int v2) {
  10     return (*this)[v1] > (*this)[v2];
  11   }
  12
  13 };
  14
  15 void find_path(const Lattice &w)
  16 {
  17   vector<int> back_traces;
  18   vector<bool> seen;
  19   vector<int> candidates;
  20   HeapValue val;
  21
  22   int i,n = w.get_word_count();
  23
  24   val.resize(n+1);
  25   back_traces.resize(n+1);
  26   seen.resize(n+1);
  27   candidates.reserve(n+1);
  28
  29   candidates.push_back(0);
  30   seen[0] = true;
  31   val[0] = 0;
  32
  33   int c = 1;
  34
  35   while (c < n) {
  36     pop_heap(candidates.begin(),candidates.end(),val);
  37     int v = candidates.back();
  38     candidates.pop_back();
  39     cerr << "got " << v << " " << val[v] << endl;
  40
  41     const WordEntryRefs &wers = w.get_we(v);
  42     int vv,ii,nn = wers.size();
  43     float value;
  44     for (ii = 0;ii < nn;ii ++) {
  45       vv = wers[ii]->pos+wers[ii]->len;
  46       value = val[v]+wers[ii]->node.node->get_prob();
  47       cerr << "examine " << vv << "(" << wers[ii]->node << ")";
  48       if (!seen[vv]) {
  49         candidates.push_back(vv);
  50         seen[vv] = true;
  51         val[vv] = value;
  52         push_heap(candidates.begin(),candidates.end(),val);
  53         back_traces[vv] = wers[ii]->id;
  54         cerr << " add " << val[vv] << "=" << v << "+"<<wers[ii]->node.node->get_prob();
  55         c++;
  56         cerr << " add";
  57       } else {
  58         if (val[vv] > value) {
  59           val[vv] = value;
  60           vector<int>::iterator iter = find(candidates.begin(),candidates.end(),vv);
  61           while (true) {
  62             push_heap(candidates.begin(),iter);
  63             if (iter != candidates.end())
  64               ++iter;
  65             else
  66               break;
  67           }
  68           back_traces[vv] = wers[ii]->id;
  69           cerr << " val " << val[vv] << "=" << v << "+"<<wers[ii]->node.node->get_prob();
  70         }
  71       }
  72       cerr << endl;
  73     }
  74   }
  75
  76   int p = n;
  77   vector<int> P;
  78   const WordEntries &we = *w.we;
  79   while (p) {
  80     int l = we[back_traces[p]].len;
  81     P.push_back(back_traces[p]);
  82     p -= l;
  83   }
  84   for (i = P.size()-1;i >= 0;i --) {
  85     cerr << we[P[i]] << endl;
  86   }
  87
  88   cerr << "done" << endl;
  89 }
  90
  91 int main(int argc,char **argv)
  92 {
  93   dic_init(argc > 1 ? new WordNode(get_sarch()["<root>"]) : new FuzzyWordNode(get_sarch()["<root>"]));
  94
  95   cerr << "Loading... ";
  96   get_root()->load("wordlist.wl");
  97   cerr << "done" << endl;
  98
  99   get_sarch().set_blocked(true);
 100
 101   string s;
 102   int count = 0;
 103   while (getline(cin,s)) {
 104     count ++;
 105     if (count % 200 == 0) cerr << count << endl;
 106     if (s.empty()) continue;
 107     vector<string> ss;
 108     sentences_split(s,ss);
 109     for (int i = 0;i < ss.size();i ++) {
 110       Sentence st(ss[i]);
 111       st.standardize();
 112       st.tokenize();
 113       Lattice words;
 114       words.construct(st);
 115       find_path(words);
 116     }
 117   }
 118 }