lttoolbox-unicode/lttoolbox/transducer.cc

   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/my_stdio.h>
  22
  23 #include <cstdlib>
  24 #include <iostream>
  25 #include <vector>
  26
  27
  28 int
  29 Transducer::newState()
  30 {
  31   int nstate = transitions.size();
  32
  33   while(transitions.find(nstate) != transitions.end())
  34   {
  35     nstate++;
  36   }
  37   transitions[nstate].clear();  // force creating
  38
  39   return nstate;
  40 }
  41
  42 Transducer::Transducer()
  43 {
  44   initial = newState();
  45 }
  46
  47 Transducer::~Transducer()
  48 {
  49   destroy();
  50 }
  51
  52 Transducer::Transducer(Transducer const &t)
  53 {
  54   copy(t);
  55 }
  56
  57 Transducer &
  58 Transducer::operator =(Transducer const &t)
  59 {
  60   if(this != &t)
  61   {
  62     destroy();
  63     copy(t);
  64   }
  65   return *this;
  66 }
  67
  68 int
  69 Transducer::insertSingleTransduction(int const tag, int const source)
  70 {
  71   if(transitions.find(source) != transitions.end())
  72   {
  73     if(transitions[source].count(tag) == 1)
  74     {
  75       pair<multimap<int,int>::iterator, multimap<int,int>::iterator > range;
  76       range = transitions[source].equal_range(tag);
  77       return range.first->second;
  78     }
  79     else if(transitions[source].count(tag) == 0)
  80     {
  81       // new state
  82       int state = newState();
  83       transitions[source].insert(pair<int, int>(tag, state));
  84       return state;
  85     }
  86     else if(transitions[source].count(tag) == 2)
  87     {
  88       // there's a local cycle, must be ignored and treated like in '1'
  89       pair<multimap<int,int>::iterator, multimap<int,int>::iterator> range;
  90       range = transitions[source].equal_range(tag);
  91       for(; range.first != range.second; range.first++)
  92       {
  93         if(range.first->second != source)
  94         {
  95           return range.first->second;
  96         }
  97       }
  98       return -1;
  99     }
 100     else
 101     {
 102       return -1;
 103     }
 104   }
 105   else
 106   {
 107     return -1;
 108   }
 109 }
 110
 111 int
 112 Transducer::insertNewSingleTransduction(int const tag, int const source)
 113 {
 114   int state = newState();
 115   transitions[source].insert(pair<int, int>(tag, state));
 116   return state;
 117 }
 118
 119 int
 120 Transducer::insertTransducer(int const source, Transducer &t,
 121                                  int const epsilon_tag)
 122 {
 123   map<int, int> relacion;
 124
 125   t.joinFinals(epsilon_tag);
 126
 127   for(map<int, multimap<int, int> >::const_iterator it = t.transitions.begin(),
 128                                                     limit = t.transitions.end();
 129       it != limit; it++)
 130   {
 131     relacion[it->first] = newState();
 132   }
 133
 134   for(map<int, multimap<int, int> >::const_iterator it = t.transitions.begin();
 135       it != t.transitions.end(); it++)
 136   {
 137     for(multimap<int, int>::const_iterator it2 = it->second.begin(),
 138                                            limit2 = (it->second).end();
 139         it2 != limit2; it2++)
 140     {
 141       transitions[relacion[it->first]].insert(pair<int, int>(it2->first, relacion[it2->second]));
 142     }
 143   }
 144
 145   transitions[source].insert(pair<int, int>(epsilon_tag,
 146                                              relacion[t.initial]));
 147
 148   return relacion[*(t.finals.begin())];
 149 }
 150
 151 void
 152 Transducer::linkStates(int const source, int const destino,
 153                             int const etiqueta)
 154 {
 155
 156   if(transitions.find(source) != transitions.end() &&
 157      transitions.find(destino) != transitions.end())
 158   {
 159     // new code
 160     pair<multimap<int, int>::iterator, multimap<int, int>::iterator> range;
 161     range = transitions[source].equal_range(etiqueta);
 162     for(;range.first != range.second; range.first++)
 163     {
 164       if(range.first->first == etiqueta && range.first->second == destino)
 165       {
 166         return;
 167       }
 168     }
 169     // end of new code
 170     transitions[source].insert(pair<int, int>(etiqueta, destino));
 171   }
 172   else
 173   {
 174     cerr << "Error: Trying to link nonexistent states (" << source;
 175     cerr << ", " << destino << ", " << etiqueta << ")" << endl;
 176     exit(EXIT_FAILURE);
 177   }
 178 }
 179
 180 bool
 181 Transducer::isFinal(int const state) const
 182 {
 183   return finals.find(state) != finals.end();
 184 }
 185
 186 void
 187 Transducer::setFinal(int const state, bool valor)
 188 {
 189   if(valor)
 190   {
 191     finals.insert(state);
 192   }
 193   else
 194   {
 195     finals.erase(state);
 196   }
 197 }
 198
 199 int
 200 Transducer::getInitial() const
 201 {
 202   return initial;
 203 }
 204
 205 set<int>
 206 Transducer::closure(int const state, int const epsilon_tag)
 207 {
 208   set<int> nonvisited, result;
 209
 210   nonvisited.insert(state);
 211   result.insert(state);
 212
 213   while(nonvisited.size() > 0)
 214   {
 215     int auxest = *nonvisited.begin();
 216     pair<multimap<int, int>::iterator, multimap<int, int>::iterator> rango;
 217     rango = transitions[auxest].equal_range(epsilon_tag);
 218     while(rango.first != rango.second)
 219     {
 220       if(result.find(rango.first->second) == result.end())
 221       {
 222         result.insert(rango.first->second);
 223         nonvisited.insert(rango.first->second);
 224       }
 225       rango.first++;
 226     }
 227     nonvisited.erase(auxest);
 228   }
 229
 230   return result;
 231 }
 232
 233 void
 234 Transducer::joinFinals(int const epsilon_tag)
 235 {
 236   if(finals.size() > 1)
 237   {
 238     int state = newState();
 239
 240     for(set<int>::iterator it = finals.begin(), limit = finals.end();
 241         it != limit; it++)
 242     {
 243       linkStates(*it, state, epsilon_tag);
 244     }
 245
 246     finals.clear();
 247     finals.insert(state);
 248   }
 249   else if(finals.size() == 0)
 250   {
 251     cerr << "Error: empty set of final states" <<endl;
 252     exit(EXIT_FAILURE);
 253   }
 254 }
 255
 256 bool
 257 Transducer::isEmptyIntersection(set<int> const &s1, set<int> const &s2)
 258 {
 259
 260   if(s1.size() < s2.size())
 261   {
 262     for(set<int>::const_iterator it = s1.begin(), limit = s1.end(); it != limit; it++)
 263     {
 264       if(s2.find(*it) != s2.end())
 265       {
 266         return false;
 267       }
 268     }
 269   }
 270   else
 271   {
 272     for(set<int>::const_iterator it = s2.begin(), limit = s2.end(); it != limit; it++)
 273     {
 274       if(s1.find(*it) != s1.end())
 275       {
 276         return false;
 277       }
 278     }
 279   }
 280
 281   return true;
 282 }
 283
 284 void
 285 Transducer::determinize(int const epsilon_tag)
 286 {
 287   vector<set<int> > R(2);
 288   map<int, set<int> > Q_prima;
 289   map<set<int>, int> Q_prima_inv;
 290
 291   map<int, multimap<int, int> > transitions_prima;
 292
 293   unsigned int talla_Q_prima = 0;
 294   Q_prima[0] = closure(initial, epsilon_tag);
 295
 296   Q_prima_inv[Q_prima[0]] = 0;
 297   R[0].insert(0);
 298
 299   int initial_prima = 0;
 300   set<int> finals_prima;
 301
 302   if(finals.find(initial) != finals.end())
 303   {
 304     finals_prima.insert(0);
 305   }
 306
 307   int t = 0;
 308
 309   while(talla_Q_prima != Q_prima.size())
 310   {
 311     talla_Q_prima = Q_prima.size();
 312     R[(t+1)%2].clear();
 313
 314     for(set<int>::iterator it = R[t].begin(), limit = R[t].end();
 315         it != limit; it++)
 316     {
 317       if(!isEmptyIntersection(Q_prima[*it], finals))
 318       {
 319         finals_prima.insert(*it);
 320       }
 321
 322       map<int, set<int> > mymap;
 323
 324       for(set<int>::iterator it2 = Q_prima[*it].begin(),
 325                              limit2 = Q_prima[*it].end();
 326           it2 != limit2; it2++)
 327       {
 328         for(multimap<int, int>::iterator it3 = transitions[*it2].begin(),
 329                                          limit3 = transitions[*it2].end();
 330             it3 != limit3; it3++)
 331         {
 332           if(it3->first != epsilon_tag)
 333           {
 334             set<int> c = closure(it3->second, epsilon_tag);
 335
 336             for(set<int>::iterator it4 = c.begin(), limit4 = c.end();
 337                 it4 != limit4; it4++)
 338             {
 339               mymap[it3->first].insert(*it4);
 340             }
 341           }
 342         }
 343       }
 344
 345       // adding new states
 346       for(map<int, set<int> >::iterator it2 = mymap.begin(), limit2 = mymap.end();
 347           it2 != limit2; it2++)
 348       {
 349         if(Q_prima_inv.find(it2->second) == Q_prima_inv.end())
 350         {
 351           int etiq = Q_prima.size();
 352           Q_prima[etiq] = it2->second;
 353           Q_prima_inv[it2->second] = etiq;
 354           R[(t+1)%2].insert(Q_prima_inv[it2->second]);
 355           transitions_prima[etiq].clear();
 356         }
 357         transitions_prima[*it].insert(pair<int, int>(it2->first, Q_prima_inv[it2->second]));
 358       }
 359     }
 360
 361     t = (t+1)%2;
 362   }
 363
 364   transitions = transitions_prima;
 365   finals = finals_prima;
 366   initial = initial_prima;
 367 }
 368
 369
 370 void
 371 Transducer::minimize(int const epsilon_tag)
 372 {
 373   reverse(epsilon_tag);
 374   determinize(epsilon_tag);
 375   reverse(epsilon_tag);
 376   determinize(epsilon_tag);
 377 }
 378
 379 void
 380 Transducer::optional(int const epsilon_tag)
 381 {
 382   joinFinals(epsilon_tag);
 383   int state = newState();
 384   linkStates(state, initial, epsilon_tag);
 385   initial = state;
 386
 387   state = newState();
 388   linkStates(*finals.begin(), state, epsilon_tag);
 389   finals.clear();
 390   finals.insert(state);
 391   linkStates(initial, state, epsilon_tag);
 392 }
 393
 394 void
 395 Transducer::oneOrMore(int const epsilon_tag)
 396 {
 397   joinFinals(epsilon_tag);
 398   int state = newState();
 399   linkStates(state, initial, epsilon_tag);
 400   initial = state;
 401
 402   state = newState();
 403   linkStates(*finals.begin(), state, epsilon_tag);
 404   finals.clear();
 405   finals.insert(state);
 406   linkStates(state, initial, epsilon_tag);
 407 }
 408
 409 void
 410 Transducer::zeroOrMore(int const epsilon_tag)
 411 {
 412   oneOrMore(epsilon_tag);
 413   optional(epsilon_tag);
 414 }
 415
 416 void
 417 Transducer::clear()
 418 {
 419   finals.clear();
 420   transitions.clear();
 421   initial = newState();
 422 }
 423
 424 bool
 425 Transducer::isEmpty() const
 426 {
 427   return finals.size() == 0 && transitions.size() == 1;
 428 }
 429
 430 int
 431 Transducer::size() const
 432 {
 433   return transitions.size();
 434 }
 435
 436 int
 437 Transducer::numberOfTransitions() const
 438 {
 439   int counter = 0;
 440
 441   for(map<int, multimap<int, int> >::const_iterator it = transitions.begin(),
 442                                                     limit = transitions.end();
 443       it != limit; it++)
 444   {
 445     counter += (it->second).size();
 446   }
 447
 448   return counter;
 449 }
 450
 451 bool
 452 Transducer::isEmpty(int const state) const
 453 {
 454   map<int, multimap<int, int> >::const_iterator it;
 455
 456   it = transitions.find(state);
 457   if(it != transitions.end())
 458   {
 459     if((it->second).size() > 0)
 460     {
 461       return false;
 462     }
 463   }
 464
 465   return true;
 466 }
 467
 468 void
 469 Transducer::write(FILE *output, int const decalage)
 470 {
 471   Compression::multibyte_write(initial, output);
 472   Compression::multibyte_write(finals.size(), output);
 473
 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+decalage, 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, int const decalage)
 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       tagbase += Compression::multibyte_read(input) - decalage;
 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>(tagbase, state));
 543     }
 544     number_of_states--;
 545     current_state++;
 546   }
 547
 548   *this = new_t;
 549 }
 550
 551 void
 552 Transducer::copy(Transducer const &t)
 553 {
 554   initial = t.initial;
 555   finals = t.finals;
 556   transitions = t.transitions;
 557 }
 558
 559 void
 560 Transducer::destroy()
 561 {
 562 }
 563
 564 void
 565 Transducer::reverse(int const epsilon_tag)
 566 {
 567   joinFinals(epsilon_tag);
 568
 569   map<int, multimap<int, int> > temporal;
 570
 571   for(map<int, multimap<int, int> >::reverse_iterator it = transitions.rbegin(); it != transitions.rend(); it++)
 572   {
 573     multimap<int, int> aux = it->second;
 574     it->second.clear();
 575     for(multimap<int, int>::iterator it2 = aux.begin(), limit2 = aux.end();
 576         it2 != limit2; it2++)
 577     {
 578       if(it2->second >= it->first)
 579       {
 580         transitions[it2->second].insert(pair<int, int>(it2->first, it->first));
 581       }
 582       else
 583       {
 584         temporal[it2->second].insert(pair<int, int>(it2->first, it->first));
 585       }
 586     }
 587     if(temporal.find(it->first) != temporal.end())
 588     {
 589       (it->second).insert(temporal[it->first].begin(), temporal[it->first].end());
 590       temporal.erase(it->first);
 591     }
 592   }
 593
 594   for(map<int, multimap<int, int> >::reverse_iterator it = temporal.rbegin(),
 595                                                       limit = temporal.rend();
 596       it != limit; it++)
 597   {
 598     for(multimap<int, int>::iterator it2 = it->second.begin(),
 599                                      limit2 = it->second.end();
 600         it2 != limit2; it2++)
 601     {
 602       transitions[it->first].insert(pair<int, int>(it2->first, it2->second));
 603     }
 604   }
 605
 606   int tmp = initial;
 607   initial = *(finals.begin());
 608   finals.clear();
 609   finals.insert(tmp);
 610 }