utils/softcount.cpp

   1 #include "softcount.h"          // -*- tab-width: 2 -*-
   2 #include <deque>
   3 #include <boost/format.hpp>
   4
   5 /**
   6    Soft counter.
   7    Based on the article "Discovering Chinese Words from Unsegmented Text".
   8    The idea is that we count all possible words in a sentence with a fraction count
   9    instead of just count the words of the best segmentation in the sentence (count=1)
  10  */
  11
  12 using namespace std;
  13
  14 /**
  15          No short description.
  16  */
  17 ostream& SoftCounter::count_lattice(const Lattice &w, ostream &os, bool first_count)
  18 {
  19         vector<long double> Sleft,Sright;
  20         vector<vector<uint> > prev;
  21         //boost::shared_ptr<WordEntries> p_we = w.we;
  22         //const WordEntries &we = *p_we;
  23         int i,n = w.get_word_count(),v,vv;
  24         long double sum = 0;
  25         VocabIndex vi[3];
  26         vector<uint> ends;
  27         long double fc;
  28
  29         Sleft.resize(w.we->size());
  30         Sright.resize(w.we->size());
  31         prev.resize(w.we->size());
  32
  33         vi[1] = 0;
  34
  35         // first pass: Sleft
  36         for (i = 0;i < n;i ++) {
  37                 const WordEntryRefs &wers = w.get_we(i);
  38                 int ii,nn = wers.size();
  39                 long double add;
  40                 for (ii = 0;ii < nn;ii ++) {
  41                         // wers[ii] is the first node (W).
  42                         v = wers[ii]->id;
  43
  44                         if (i == 0) {
  45                                 vi[0] = get_id(START_ID);
  46                                 Sleft[v] = first_count ? 1 : -(long double)get_ngram().wordProb((*w.we)[v].node.node->get_id(),vi);
  47                                 //cerr << "Sleft("  << vi[0] << "," << v << ") = " << Sleft[v] << endl;
  48                         }
  49
  50                         int next = wers[ii]->pos+wers[ii]->len;
  51                         if (next < n) {
  52                                 const WordEntryRefs &wers2 = w.get_we(next);
  53                                 int iii,nnn = wers2.size();
  54                                 for (iii = 0;iii < nnn;iii ++) {
  55                                         // wers2[iii] is the second node (W').
  56                                         vv = wers2[iii]->id;
  57                                         vi[0] = (*w.we)[v].node.node->get_id();
  58                                         add = first_count ? 1 : Sleft[v]*(-(long double)get_ngram().wordProb((*w.we)[vv].node.node->get_id(),vi));
  59                                         Sleft[vv] += add;
  60
  61                                         //cerr << "Sleft("  << vi[0] << "," << vv << ") = " << Sleft[vv] << endl;
  62
  63                                         // init prev references for Sright phase
  64                                         prev[vv].push_back(v);
  65                                 }
  66                         } else {
  67                                 vi[0] = (*w.we)[v].node.node->get_id();
  68                                 Sright[v] = first_count ? 1 : -(long double)get_ngram().wordProb(get_id(STOP_ID),vi);
  69                                 //cerr << "Sright("  << vi[0] << "," << v << ") = " << Sright[v] << endl;
  70                                 sum += Sleft[v];
  71                                 //cerr << "Sum " << sum << endl;
  72                                 ends.push_back(v);
  73                         }
  74                 }
  75         }
  76
  77         // second pass: Sright
  78         Sright[w.we->size()-1] = 1;
  79         for (i = n-1;i >= 0;i --) {
  80                 const WordEntryRefs &wers = w.get_we(i);
  81                 int ii,nn = wers.size();
  82                 long double add;
  83                 for (ii = 0;ii < nn;ii ++) {
  84                         // wers[ii] is the first node (W).
  85                         v = wers[ii]->id;
  86
  87                         int iii,nnn = prev[v].size();
  88                         for (iii = 0;iii < nnn;iii ++) {
  89                                 // vv is the second node (W').
  90                                 vv = prev[v][iii];
  91                                 vi[0] = (*w.we)[vv].node.node->get_id();
  92                                 add = first_count ? 1 : Sright[v]*(-(long double)get_ngram().wordProb((*w.we)[v].node.node->get_id(),vi));
  93                                 Sright[vv] += add;
  94
  95                                 //cerr << "Sright("  << vi[0] << "," << vv << ") = " << Sright[vv] << endl;
  96
  97                                 // collect fractional counts
  98                                 fc = Sleft[vv]*add/sum; // P(v/vv)
  99                                 vi[0] = (*w.we)[vv].node.node->get_id();
 100                                 vi[1] = (*w.we)[v].node.node->get_id();
 101                                 vi[2] = 0;
 102                                 //*stats.insertCount(vi) += fc;
 103                                 os << boost::format("%s %s %f\n") % get_ngram()[vi[0]] % get_ngram()[vi[1]] << fc;
 104                                 //cerr << "Gram "  << vi[0] << "," << vi[1] << "+=" << fc << endl;
 105                                 vi[1] = 0;
 106                         }
 107                 }
 108         }
 109
 110         // collect fc of ends
 111         // we can use Sright with no problems becase there is only one edge
 112         // from ends[i] to the end.
 113         n = ends.size();
 114         vi[2] = 0;
 115         vi[1] = get_id(STOP_ID);
 116         for (i = 0;i < n;i ++) {
 117                 fc = Sleft[ends[i]]*Sright[ends[i]]/sum;
 118                 vi[0] = (*w.we)[ends[i]].node.node->get_id();
 119                 //cerr << "Gram "  << vi[0] << "," << vi[1] << "+=" << fc << endl;
 120                 //*stats.insertCount(vi) += fc;
 121                 os << boost::format("%s %s %f\n") % get_ngram()[vi[0]] % get_ngram()[vi[1]] << fc;
 122         }
 123
 124         vi[0] = get_id(START_ID);
 125         const WordEntryRefs &wers = w.get_we(0);
 126         n = wers.size();
 127         for (i = 0;i < n;i ++) {
 128                 fc = Sleft[wers[i]->id]*Sright[wers[i]->id]/sum;
 129                 vi[1] = (*w.we)[wers[i]->id].node.node->get_id();
 130                 //cerr << "Gram "  << vi[0] << "," << vi[1] << "+=" << fc << endl;
 131                 //*stats.insertCount(vi) += fc;
 132                 os << boost::format("%s %s %f\n") % get_ngram()[vi[0]] % get_ngram()[vi[1]] << fc;
 133         }
 134         return os;
 135 }
 136
 137
 138 ostream& SoftCounter::count_dag(const DAG &dag,ostream &os,int id, bool first_count)
 139 {
 140         int n = dag.node_count();
 141         vector<long double> Sleft(n),Sright(n);
 142         vector<set<uint> > prev(n);
 143         int i,v,vv;
 144         long double add;
 145
 146         //cerr << "Nodes: " << n << endl;
 147
 148         vector<bool> mark(n);
 149         deque<uint> traces;
 150         Sleft[dag.node_begin()] = 1;
 151         traces.push_back(dag.node_begin());
 152         // first pass: Sleft
 153         while (!traces.empty()) {
 154                 v = traces.front();
 155                 traces.pop_front();
 156                 if (mark[v])
 157                         continue;
 158                 else
 159                         mark[v] = true;
 160                 std::vector<uint> nexts;
 161                 dag.get_next(v,nexts);
 162                 n = nexts.size();
 163
 164                 for (i = 0;i < n;i ++) {
 165                         vv = nexts[i];
 166                         add = Sleft[v]*(first_count ? 1 : LogPtoProb(-dag.edge_value(v,vv)));
 167                         if (add == 0.0 || add == -0.0)
 168                                 cerr << boost::format("WARNING: %d: Sleft addition for %d is zero (Sleft[%d] = %Lg, prob=%g)") % id % vv % v % Sleft[v] % LogPtoProb(-dag.edge_value(v,vv)) << endl;
 169                         Sleft[vv] += add;
 170
 171                         traces.push_back(vv);
 172
 173                         // init prev references for Sright phase
 174                         prev[vv].insert(v);
 175                 }
 176         }
 177
 178         //cerr << "Sleft done" << endl;
 179
 180         long double fc;
 181         // second pass: Sright
 182         long double sum = Sleft[dag.node_end()];
 183         if (sum == 0.0 || sum == -0.0) {
 184                 cerr << boost::format("WARNING: %d: Sum is zero") % id << endl;
 185                 // Can do nothing more because sum is zero
 186                 return os;
 187         }
 188         Sright[dag.node_end()] = 1;
 189         traces.clear();
 190         traces.push_back(dag.node_end()); // the last v above
 191         while (!traces.empty()) {
 192                 vv = traces.front();
 193                 traces.pop_front();
 194                 if (!mark[vv])
 195                         continue;
 196                 else
 197                         mark[vv] = false;
 198                 //cerr << vv << " ";
 199                 set<uint>::iterator iter;
 200                 for (iter = prev[vv].begin();iter != prev[vv].end(); ++iter) {
 201                         v = *iter;
 202                         traces.push_back(v);
 203
 204                         add = Sright[vv]*(first_count ? 1 : LogPtoProb(-dag.edge_value(v,vv)));
 205                         if (add == 0.0 || add == -0.0)
 206                                 cerr << boost::format("WARNING: %d: Sright addition for %d is zero") % id % v << endl;
 207                         Sright[v] += add;
 208
 209                         // collect fractional counts
 210                         fc = Sleft[v]*add/sum; // P(vv/v)
 211                         VocabIndex vi[10];
 212                         VocabIndex vvv;
 213                         if (dag.fill_vi(v,vv,vvv,vi,9)) {
 214                                 uint t,jn,j;
 215                                 for (jn = 0;vi[jn] != 0 && jn < 9; jn ++);
 216                                 if (jn < 9 && vi[jn] == 0) {
 217                                         for (j = 0;j < jn/2;j ++) {
 218                                                 t = vi[j];
 219                                                 vi[j] = vi[jn-j-1];
 220                                                 vi[jn-j-1] = t;
 221                                         }
 222                                         vi[jn] = vvv;
 223                                         vi[jn+1] = 0;
 224                                         //stats.countSentence(vi,/*LogPtoProb(--fc)*/fc);
 225                                         //*stats.insertCount(vi) += fc;
 226                                         // FIXME
 227                                         for (int i_vi = 0; vi[i_vi] != 0; i_vi ++)
 228                                                 cout << get_ngram()[vi[i_vi]] << " ";
 229                                         cout << fc;
 230                                         cout << endl;
 231                                 }
 232                         }
 233                 }
 234         }
 235         //cerr << "Sright done" << endl;
 236         return os;
 237 }
 238
 239 void SoftCounter::record2(const DAG &dag,FILE *fp,int id)
 240 {
 241         int n = dag.node_count();
 242         vector<set<uint> > prev(n);
 243         int i,v,vv;
 244
 245         vector<bool> mark(n);
 246         deque<uint> traces;
 247         traces.push_back(dag.node_begin());
 248
 249         fprintf(fp,"%d %d %d\n",n,dag.node_begin(),dag.node_end());
 250
 251         while (!traces.empty()) {
 252                 v = traces.front();
 253                 traces.pop_front();
 254                 if (mark[v])
 255                         continue;
 256                 else
 257                         mark[v] = true;
 258                 std::vector<uint> nexts;
 259                 dag.get_next(v,nexts);
 260                 n = nexts.size();
 261
 262                 for (i = 0;i < n;i ++) {
 263                         vv = nexts[i];
 264
 265             VocabIndex edge_vi[2],edge_v;
 266                         dag.fill_vi(v,vv,edge_v,edge_vi,2);
 267                         fprintf(fp,"L %d %d %s %s\n",v,vv,get_ngram()[edge_vi[0]],get_ngram()[edge_v]);
 268
 269                         traces.push_back(vv);
 270
 271                         // init prev references for Sright phase
 272                         prev[vv].insert(v);
 273                 }
 274         }
 275
 276         traces.clear();
 277         traces.push_back(dag.node_end()); // the last v above
 278         while (!traces.empty()) {
 279                 vv = traces.front();
 280                 traces.pop_front();
 281                 if (!mark[vv])
 282                         continue;
 283                 else
 284                         mark[vv] = false;
 285
 286                 set<uint>::iterator iter;
 287                 for (iter = prev[vv].begin();iter != prev[vv].end(); ++iter) {
 288                         v = *iter;
 289                         traces.push_back(v);
 290
 291             VocabIndex edge_vi[2],edge_v;
 292                         dag.fill_vi(v,vv,edge_v,edge_vi,2);
 293                         fprintf(fp,"R %d %d %s %s\n",v,vv,get_ngram()[edge_vi[0]],get_ngram()[edge_v]);
 294                 }
 295         }
 296         fprintf(fp,"E 0 0 none none\n");
 297 }
 298
 299 int SoftCounter::replay2(FILE *fp_in,FILE *fp_out, int id,bool first_count)
 300 {
 301         int n, node_begin, node_end;
 302
 303         if (fscanf(fp_in,"%d %d %d\n",&n,&node_begin,&node_end) != 3) {
 304                 fprintf(stderr,"Error: %d: Could not read dag count\n",id);
 305                 return -2;
 306         }
 307
 308         vector<long double> Sleft(n),Sright(n);
 309         int i,v,vv;
 310         long double add;
 311         char type[2]; // should not be longer than one
 312         char str1[100],str2[100];
 313         int right_mode = 0;
 314         long double sum;
 315
 316         //cerr << "Nodes: " << n << endl;
 317
 318         Sleft[node_begin] = 1;
 319
 320         while (fscanf(fp_in,"%s %d %d %s %s\n",type,&v,&vv,str1,str2) == 5) {
 321                 if (type[0] == 'E')
 322                         return 0;
 323                 //fprintf(stderr,"Got %s %d %d %s %s\n",type,v,vv,str1,str2);
 324                 VocabIndex edge_vi[2],edge_v;
 325                 edge_v = get_ngram()[str2];
 326                 edge_vi[0] = get_ngram()[str1];
 327                 edge_vi[1] = 0;
 328                 if (type[0] == 'L') {
 329                         add = Sleft[v]*(first_count ? 1 : (long double)LogPtoProb(get_ngram().wordProb(edge_v,edge_vi)));
 330                         if (add == 0.0 || add == -0.0) {
 331                                 fprintf(stderr,"WARNING: %d: Sleft addition for %d is zero (Sleft[%d] = %Lg, prob=%g %s %s)\n",id,vv,v,Sleft[v],LogPtoProb(get_ngram().wordProb(edge_v,edge_vi)),str1,str2);
 332                                 add = Sleft[v];
 333                         }
 334                         Sleft[vv] += add;
 335                 }
 336                 else {
 337                         if (!right_mode) {
 338                                 right_mode = 1;
 339                                 sum = Sleft[node_end];
 340                                 if (sum == 0.0 || sum == -0.0) {
 341                                         fprintf(stderr,"WARNING: %d: Sum is zero\n",id);
 342                                 }
 343                                 Sright[node_end] = 1;
 344                         }
 345                         if (sum == 0.0 || sum == -0.0)
 346                                 continue;
 347                         add = Sright[vv]*(first_count ? 1 : (long double)LogPtoProb(get_ngram().wordProb(edge_v,edge_vi)));
 348                         if (add == 0.0 || add == -0.0) {
 349                                 fprintf(stderr,"WARNING: %d: Sright addition for %d is zero (%s %s)\n",id,v,str1,str2);
 350                                 add = Sright[vv];
 351                         }
 352                         Sright[v] += add;
 353
 354                         // collect fractional counts
 355                         long double fc = Sleft[v]*add/sum; // P(vv/v)
 356                         fprintf(fp_out,"%s %s %Lg\n",str1,str2,fc);
 357                 }
 358         }
 359         return 0;
 360 }
 361
 362 /*
 363          A work-around because NgramFractionalStats is still buggy.
 364 */
 365
 366
 367 ostream& SoftCounter::count_dag_fixed(const DAG &dag,ostream &os,bool first_count)
 368 {
 369         vector<long double> Sleft,Sright;
 370         vector<set<uint> > prev;
 371         int i,n,v,vv;
 372         long double add;
 373
 374         n = dag.node_count();
 375         Sleft.resize(n);
 376         Sright.resize(n);
 377         prev.resize(n);
 378         //cerr << "Nodes: " << n << endl;
 379
 380         // topo sort
 381         vector<uint> traces;
 382         traces.push_back(dag.node_begin());
 383         int itrace = 0;
 384         while (itrace < traces.size()) {
 385                 v = traces[itrace++];
 386                 std::vector<uint> nexts;
 387                 dag.get_next(v,nexts);
 388                 n = nexts.size();
 389
 390                 for (i = 0;i < n;i ++) {
 391                         vector<uint>::iterator iter = find(traces.begin(),traces.end(),nexts[i]);
 392                         if (iter != traces.end()) {
 393                                 traces.erase(iter);
 394                                 if (iter - traces.begin() <= itrace-1)
 395                                         itrace --;
 396                         }
 397                         traces.push_back(nexts[i]);
 398                 }
 399         }
 400
 401         // first pass: Sleft
 402         uint ntrace = traces.size();
 403         Sleft[dag.node_begin()] = 1; // log(1) = 0
 404         for (itrace = 0;itrace < ntrace;itrace ++) {
 405                 v = traces[itrace];
 406                 //cout << " " << v << ":" << Sleft[v];
 407                 std::vector<uint> nexts;
 408                 dag.get_next(v,nexts);
 409                 n = nexts.size();
 410
 411                 for (i = 0;i < n;i ++) {
 412                         vv = nexts[i];
 413                         add = Sleft[v]*dag.edge_value(v,vv);
 414                         //cout << "-" << dag.edge_value(v,vv) << "-" << Sleft[vv] << ">" << vv;
 415                         Sleft[vv] += add;
 416
 417                         // init prev references for Sright phase
 418                         prev[vv].insert(v);
 419                 }
 420         }
 421
 422         //cerr << "Sleft done" << endl;
 423
 424         unsigned int fc;
 425         // second pass: Sright
 426         long double sum = Sleft[dag.node_end()];
 427         if (sum == 0)
 428                 return os;
 429         //cout << "Sum " << sum << endl;
 430
 431         traces.clear();
 432         traces.push_back(dag.node_end());
 433         itrace = 0;
 434         while (itrace < traces.size()) {
 435                 vv = traces[itrace++];
 436
 437                 set<uint>::iterator iter;
 438                 for (iter = prev[vv].begin();iter != prev[vv].end(); ++iter) {
 439                         vector<uint>::iterator iiter = find(traces.begin(),traces.end(),*iter);
 440                         if (iiter != traces.end()) {
 441                                 traces.erase(iiter);
 442                                 if (iiter - traces.begin() <= itrace-1)
 443                                         itrace --;
 444                         }
 445                         traces.push_back(*iter);
 446                 }
 447         }
 448
 449         ntrace = traces.size();
 450         Sright[dag.node_end()] = 1; // log(1) = 0
 451         for (itrace = 0;itrace < ntrace;itrace ++) {
 452                 vv = traces[itrace];
 453                 //cout << " " << vv << ":" << Sright[vv];
 454                 set<uint>::iterator iter;
 455                 for (iter = prev[vv].begin();iter != prev[vv].end(); ++iter) {
 456                         v = *iter;
 457                         add = Sright[vv]*dag.edge_value(v,vv);
 458                         //cout << "-" << dag.edge_value(v,vv)<< "-" << Sright[v] << ">" << v;
 459                         Sright[v] += add;
 460
 461                         // collect fractional counts
 462                         fc = 100-(unsigned int)((Sleft[v]*add)*100.0/sum); // P(vv/v)
 463                         //cout << Sleft[v] << "+" << dag.edge_value(v,vv) << Sright[vv]<<  "=("<< (Sleft[v]+add)<< ")"<<((Sleft[v]+add)/sum) <<"_" << fc << endl;
 464                         cerr << v << " " << vv << " " << fc << endl;
 465                         if (fc != 0) {
 466                                 VocabIndex vi[10];
 467                                 VocabIndex vvv;
 468                                 if (dag.fill_vi(v,vv,vvv,vi,9)) {
 469                                         uint t,jn,j;
 470                                         for (jn = 0;vi[jn] != 0 && jn < 9; jn ++);
 471                                         if (jn < 9 && vi[jn] == 0) {
 472                                                 for (j = 0;j < jn/2;j ++) {
 473                                                         t = vi[j];
 474                                                         vi[j] = vi[jn-j-1];
 475                                                         vi[jn-j-1] = t;
 476                                                 }
 477                                                 vi[jn] = vvv;
 478                                                 vi[jn+1] = 0;
 479                                                 //stats.countSentence(vi,(unsigned int)(fc*10.0));
 480                                                 //*stats.insertCount(vi) += fc;
 481                                                 // FIXME
 482                                         }
 483                                 }
 484                         }
 485                 }
 486         }
 487         cerr << endl;
 488         //long double sum2 = Sright[dag.node_begin()];
 489         //cout << sum2 << " " << (traces[ntrace-1] == dag.node_begin()) << " " << (sum2 == sum ? "Ok" : "Failed") << endl;
 490         //cerr << "Sright done" << endl;
 491         return os;
 492 }