lttoolbox/lttoolbox/Transducer.C

   1 /*
   2  * Copyright (C) 2005 Universitat d'Alacant / Universidad de Alicante
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License as
   6  * published by the Free Software Foundation; either version 2 of the
   7  * License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful, but
  10  * WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  17  * 02111-1307, USA.
  18  */
  19 #include <lttoolbox/Transducer.H>
  20 #include <lttoolbox/Compression.H>
  21 #include <lttoolbox/MyStdio.H>
  22 #include <lttoolbox/Utility.H>
  23
  24 #include <cstdlib>
  25 #include <iostream>
  26 #include <vector>
  27
  28
  29 int
  30 Transducer::newState()
  31 {
  32   int nstate = transitions.size();
  33
  34   while(transitions.find(nstate) != transitions.end())
  35   {
  36     nstate++;
  37   }
  38   transitions[nstate].clear();  // force creating
  39
  40   return nstate;
  41 }
  42
  43 Transducer::Transducer()
  44 {
  45   initial = newState();
  46 }
  47
  48 Transducer::~Transducer()
  49 {
  50   destroy();
  51 }
  52
  53 Transducer::Transducer(Transducer const &t)
  54 {
  55   copy(t);
  56 }
  57
  58 Transducer &
  59 Transducer::operator =(Transducer const &t)
  60 {
  61   if(this != &t)
  62   {
  63     destroy();
  64     copy(t);
  65   }
  66   return *this;
  67 }
  68
  69 int
  70 Transducer::insertSingleTransduction(int const tag, int const source)
  71 {
  72   if(transitions.find(source) != transitions.end())
  73   {
  74     if(transitions[source].count(tag) == 1)
  75     {
  76       pair<multimap<int,int>::iterator, multimap<int,int>::iterator > range;
  77       range = transitions[source].equal_range(tag);
  78       return range.first->second;
  79     }
  80     else if(transitions[source].count(tag) == 0)
  81     {
  82       // new state
  83       int state = newState();
  84       transitions[source].insert(pair<int, int>(tag, state));
  85       return state;
  86     }
  87     else if(transitions[source].count(tag) == 2)
  88     {
  89       // there's a local cycle, must be ignored and treated like in '1'
  90       pair<multimap<int,int>::iterator, multimap<int,int>::iterator> range;
  91       range = transitions[source].equal_range(tag);
  92       for(; range.first != range.second; range.first++)
  93       {
  94         if(range.first->second != source)
  95         {
  96           return range.first->second;
  97         }
  98       }
  99       return -1;
 100     }
 101     else
 102     {
 103       return -1;
 104     }
 105   }
 106   else
 107   {
 108     return -1;
 109   }
 110 }
 111
 112 int
 113 Transducer::insertNewSingleTransduction(int const tag, int const source)
 114 {
 115   int state = newState();
 116   transitions[source].insert(pair<int, int>(tag, state));
 117   return state;
 118 }
 119
 120 int
 121 Transducer::insertTransducer(int const source, Transducer &t,
 122                                  int const epsilon_tag)
 123 {
 124   map<int, int> relacion;
 125
 126   t.joinFinals(epsilon_tag);
 127
 128   for(map<int, multimap<int, int> >::const_iterator it = t.transitions.begin(),
 129                                                     limit = t.transitions.end();
 130       it != limit; it++)
 131   {
 132     relacion[it->first] = newState();
 133   }
 134
 135   for(map<int, multimap<int, int> >::const_iterator it = t.transitions.begin();
 136       it != t.transitions.end(); it++)
 137   {
 138     for(multimap<int, int>::const_iterator it2 = it->second.begin(),
 139                                            limit2 = (it->second).end();
 140         it2 != limit2; it2++)
 141     {
 142       transitions[relacion[it->first]].insert(pair<int, int>(it2->first, relacion[it2->second]));
 143     }
 144   }
 145
 146   transitions[source].insert(pair<int, int>(epsilon_tag,
 147                                              relacion[t.initial]));
 148
 149   return relacion[*(t.finals.begin())];
 150 }
 151
 152 void
 153 Transducer::linkStates(int const source, int const destino,
 154                             int const etiqueta)
 155 {
 156
 157   if(transitions.find(source) != transitions.end() &&
 158      transitions.find(destino) != transitions.end())
 159   {
 160     // new code
 161     pair<multimap<int, int>::iterator, multimap<int, int>::iterator> range;
 162     range = transitions[source].equal_range(etiqueta);
 163     for(;range.first != range.second; range.first++)
 164     {
 165       if(range.first->first == etiqueta && range.first->second == destino)
 166       {
 167         return;
 168       }
 169     }
 170     // end of new code
 171     transitions[source].insert(pair<int, int>(etiqueta, destino));
 172   }
 173   else
 174   {
 175     cerr << "Error: Trying to link nonexistent states (" << source;
 176     cerr << ", " << destino << ", " << etiqueta << ")" << endl;
 177     exit(EXIT_FAILURE);
 178   }
 179 }
 180
 181 bool
 182 Transducer::isFinal(int const state) const
 183 {
 184   return finals.find(state) != finals.end();
 185 }
 186
 187 void
 188 Transducer::setFinal(int const state, bool valor)
 189 {
 190   if(valor)
 191   {
 192     finals.insert(state);
 193   }
 194   else
 195   {
 196     finals.erase(state);
 197   }
 198 }
 199
 200 int
 201 Transducer::getInitial() const
 202 {
 203   return initial;
 204 }
 205
 206 set<int>
 207 Transducer::closure(int const state, int const epsilon_tag)
 208 {
 209   set<int> nonvisited, result;
 210
 211   nonvisited.insert(state);
 212   result.insert(state);
 213
 214   while(nonvisited.size() > 0)
 215   {
 216     int auxest = *nonvisited.begin();
 217     pair<multimap<int, int>::iterator, multimap<int, int>::iterator> rango;
 218     rango = transitions[auxest].equal_range(epsilon_tag);
 219     while(rango.first != rango.second)
 220     {
 221       if(result.find(rango.first->second) == result.end())
 222       {
 223         result.insert(rango.first->second);
 224         nonvisited.insert(rango.first->second);
 225       }
 226       rango.first++;
 227     }
 228     nonvisited.erase(auxest);
 229   }
 230
 231   return result;
 232 }
 233
 234 void
 235 Transducer::joinFinals(int const epsilon_tag)
 236 {
 237   if(finals.size() > 1)
 238   {
 239     int state = newState();
 240
 241     for(set<int>::iterator it = finals.begin(), limit = finals.end();
 242         it != limit; it++)
 243     {
 244       linkStates(*it, state, epsilon_tag);
 245     }
 246
 247     finals.clear();
 248     finals.insert(state);
 249   }
 250   else if(finals.size() == 0)
 251   {
 252     cerr << "Error: empty set of final states" <<endl;
 253     exit(EXIT_FAILURE);
 254   }
 255 }
 256
 257 bool
 258 Transducer::isEmptyIntersection(set<int> const &s1, set<int> const &s2)
 259 {
 260
 261   if(s1.size() < s2.size())
 262   {
 263     for(set<int>::iterator it = s1.begin(), limit = s1.end(); it != limit; it++)
 264     {
 265       if(s2.find(*it) != s2.end())
 266       {
 267         return false;
 268       }
 269     }
 270   }
 271   else
 272   {
 273     for(set<int>::iterator it = s2.begin(), limit = s2.end(); it != limit; it++)
 274     {
 275       if(s1.find(*it) != s1.end())
 276       {
 277         return false;
 278       }
 279     }
 280   }
 281
 282   return true;
 283 }
 284
 285 void
 286 Transducer::determinize(int const epsilon_tag)
 287 {
 288   vector<set<int> > R(2);
 289   map<int, set<int> > Q_prima;
 290   map<set<int>, int> Q_prima_inv;
 291
 292   map<int, multimap<int, int> > transitions_prima;
 293
 294   unsigned int talla_Q_prima = 0;
 295   Q_prima[0] = closure(initial, epsilon_tag);
 296
 297   Q_prima_inv[Q_prima[0]] = 0;
 298   R[0].insert(0);
 299
 300   int initial_prima = 0;
 301   set<int> finals_prima;
 302
 303   if(finals.find(initial) != finals.end())
 304   {
 305     finals_prima.insert(0);
 306   }
 307
 308   int t = 0;
 309
 310   while(talla_Q_prima != Q_prima.size())
 311   {
 312     talla_Q_prima = Q_prima.size();
 313     R[(t+1)%2].clear();
 314
 315     for(set<int>::iterator it = R[t].begin(), limit = R[t].end();
 316         it != limit; it++)
 317     {
 318       if(!isEmptyIntersection(Q_prima[*it], finals))
 319       {
 320         finals_prima.insert(*it);
 321       }
 322
 323       map<int, set<int> > mymap;
 324
 325       for(set<int>::iterator it2 = Q_prima[*it].begin(),
 326                              limit2 = Q_prima[*it].end();
 327           it2 != limit2; it2++)
 328       {
 329         for(multimap<int, int>::iterator it3 = transitions[*it2].begin(),
 330                                          limit3 = transitions[*it2].end();
 331             it3 != limit3; it3++)
 332         {
 333           if(it3->first != epsilon_tag)
 334           {
 335             set<int> c = closure(it3->second, epsilon_tag);
 336
 337             for(set<int>::iterator it4 = c.begin(), limit4 = c.end();
 338                 it4 != limit4; it4++)
 339             {
 340               mymap[it3->first].insert(*it4);
 341             }
 342           }
 343         }
 344       }
 345
 346       // adding new states
 347       for(map<int, set<int> >::iterator it2 = mymap.begin(), limit2 = mymap.end();
 348           it2 != limit2; it2++)
 349       {
 350         if(Q_prima_inv.find(it2->second) == Q_prima_inv.end())
 351         {
 352           int etiq = Q_prima.size();
 353           Q_prima[etiq] = it2->second;
 354           Q_prima_inv[it2->second] = etiq;
 355           R[(t+1)%2].insert(Q_prima_inv[it2->second]);
 356           transitions_prima[etiq].clear();
 357         }
 358         transitions_prima[*it].insert(pair<int, int>(it2->first, Q_prima_inv[it2->second]));
 359       }
 360     }
 361
 362     t = (t+1)%2;
 363   }
 364
 365   transitions = transitions_prima;
 366   finals = finals_prima;
 367   initial = initial_prima;
 368 }
 369
 370
 371 void
 372 Transducer::minimize(int const epsilon_tag)
 373 {
 374   reverse(epsilon_tag);
 375   determinize(epsilon_tag);
 376   reverse(epsilon_tag);
 377   determinize(epsilon_tag);
 378 }
 379
 380 void
 381 Transducer::optional(int const epsilon_tag)
 382 {
 383   joinFinals(epsilon_tag);
 384   int state = newState();
 385   linkStates(state, initial, epsilon_tag);
 386   initial = state;
 387
 388   state = newState();
 389   linkStates(*finals.begin(), state, epsilon_tag);
 390   finals.clear();
 391   finals.insert(state);
 392   linkStates(initial, state, epsilon_tag);
 393 }
 394
 395 void
 396 Transducer::oneOrMore(int const epsilon_tag)
 397 {
 398   joinFinals(epsilon_tag);
 399   int state = newState();
 400   linkStates(state, initial, epsilon_tag);
 401   initial = state;
 402
 403   state = newState();
 404   linkStates(*finals.begin(), state, epsilon_tag);
 405   finals.clear();
 406   finals.insert(state);
 407   linkStates(state, initial, epsilon_tag);
 408 }
 409
 410 void
 411 Transducer::zeroOrMore(int const epsilon_tag)
 412 {
 413   oneOrMore(epsilon_tag);
 414   optional(epsilon_tag);
 415 }
 416
 417 void
 418 Transducer::clear()
 419 {
 420   finals.clear();
 421   transitions.clear();
 422   initial = newState();
 423 }
 424
 425 bool
 426 Transducer::isEmpty() const
 427 {
 428   return finals.size() == 0 && transitions.size() == 1;
 429 }
 430
 431 int
 432 Transducer::size() const
 433 {
 434   return transitions.size();
 435 }
 436
 437 int
 438 Transducer::numberOfTransitions() const
 439 {
 440   int counter = 0;
 441
 442   for(map<int, multimap<int, int> >::const_iterator it = transitions.begin(),
 443                                                     limit = transitions.end();
 444       it != limit; it++)
 445   {
 446     counter += (it->second).size();
 447   }
 448
 449   return counter;
 450 }
 451
 452 bool
 453 Transducer::isEmpty(int const state) const
 454 {
 455   map<int, multimap<int, int> >::const_iterator it;
 456
 457   it = transitions.find(state);
 458   if(it != transitions.end())
 459   {
 460     if((it->second).size() > 0)
 461     {
 462       return false;
 463     }
 464   }
 465
 466   return true;
 467 }
 468
 469 void
 470 Transducer::write(FILE *output)
 471 {
 472   Compression::multibyte_write(initial, output);
 473   Compression::multibyte_write(finals.size(), output);
 474   int base = 0;
 475   for(set<int>::iterator it = finals.begin(), limit = finals.end();
 476       it != limit; it++)
 477   {
 478     Compression::multibyte_write(*it - base, output);
 479     base = *it;
 480   }
 481
 482   base = transitions.size();
 483   Compression::multibyte_write(base, output);
 484   for(map<int, multimap<int, int> >::iterator it = transitions.begin(),
 485                                               limit = transitions.end();
 486       it != limit; it++)
 487   {
 488     Compression::multibyte_write(it->second.size(), output);
 489     int tagbase = 0;
 490     for(multimap<int, int>::iterator it2 = it->second.begin(),
 491                                      limit2 = it->second.end();
 492         it2 != limit2; it2++)
 493     {
 494       Compression::multibyte_write(it2->first-tagbase, output);
 495       tagbase = it2->first;
 496
 497       if(it2->second >= it->first)
 498       {
 499         Compression::multibyte_write(it2->second-it->first, output);
 500       }
 501       else
 502       {
 503         Compression::multibyte_write(it2->second+base-it->first, output);
 504       }
 505     }
 506   }
 507 }
 508
 509 void
 510 Transducer::read(FILE *input)
 511 {
 512   Transducer new_t;
 513
 514   new_t.initial = Compression::multibyte_read(input);
 515   int finals_size = Compression::multibyte_read(input);
 516
 517   int base = 0;
 518   while(finals_size > 0)
 519   {
 520     finals_size--;
 521
 522     base += Compression::multibyte_read(input);
 523     new_t.finals.insert(base);
 524   }
 525
 526   base = Compression::multibyte_read(input);
 527   int number_of_states = base;
 528   int current_state = 0;
 529   while(number_of_states > 0)
 530   {
 531     int number_of_local_transitions = Compression::multibyte_read(input);
 532     int tagbase = 0;
 533     while(number_of_local_transitions > 0)
 534     {
 535       number_of_local_transitions--;
 536       int tag = Compression::multibyte_read(input);
 537       int state = (current_state + Compression::multibyte_read(input)) % base;
 538       if(new_t.transitions.find(state) == new_t.transitions.end())
 539       {
 540         new_t.transitions[state].clear(); // force create
 541       }
 542       new_t.transitions[current_state].insert(pair<int, int>(tag+tagbase, state));
 543       tagbase += tag;
 544     }
 545     number_of_states--;
 546     current_state++;
 547   }
 548
 549   *this = new_t;
 550 }
 551
 552 void
 553 Transducer::copy(Transducer const &t)
 554 {
 555   initial = t.initial;
 556   finals = t.finals;
 557   transitions = t.transitions;
 558 }
 559
 560 void
 561 Transducer::destroy()
 562 {
 563 }
 564
 565 void
 566 Transducer::reverse(int const epsilon_tag)
 567 {
 568   joinFinals(epsilon_tag);
 569
 570   map<int, multimap<int, int> > temporal;
 571
 572   for(map<int, multimap<int, int> >::reverse_iterator it = transitions.rbegin(); it != transitions.rend(); it++)
 573   {
 574     multimap<int, int> aux = it->second;
 575     it->second.clear();
 576     for(multimap<int, int>::iterator it2 = aux.begin(), limit2 = aux.end();
 577         it2 != limit2; it2++)
 578     {
 579       if(it2->second >= it->first)
 580       {
 581         transitions[it2->second].insert(pair<int, int>(it2->first, it->first));
 582       }
 583       else
 584       {
 585         temporal[it2->second].insert(pair<int, int>(it2->first, it->first));
 586       }
 587     }
 588     if(temporal.find(it->first) != temporal.end())
 589     {
 590       (it->second).insert(temporal[it->first].begin(), temporal[it->first].end());
 591       temporal.erase(it->first);
 592     }
 593   }
 594
 595   for(map<int, multimap<int, int> >::reverse_iterator it = temporal.rbegin(),
 596                                                       limit = temporal.rend();
 597       it != limit; it++)
 598   {
 599     for(multimap<int, int>::iterator it2 = it->second.begin(),
 600                                      limit2 = it->second.end();
 601         it2 != limit2; it2++)
 602     {
 603       transitions[it->first].insert(pair<int, int>(it2->first, it2->second));
 604     }
 605   }
 606
 607   int tmp = initial;
 608   initial = *(finals.begin());
 609   finals.clear();
 610   finals.insert(tmp);
 611 }