Home | History | Annotate | Download | only in lib 
      1 // rmfinalepsilon.h
      2 //
      3 // Licensed under the Apache License, Version 2.0 (the "License");
      4 // you may not use this file except in compliance with the License.
      5 // You may obtain a copy of the License at
      6 //
      7 //      http://www.apache.org/licenses/LICENSE-2.0
      8 //
      9 // Unless required by applicable law or agreed to in writing, software
     10 // distributed under the License is distributed on an "AS IS" BASIS,
     11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     12 // See the License for the specific language governing permissions and
     13 // limitations under the License.
     14 //
     15 //
     16 // \file
     17 // Function to remove of final states that have epsilon only input arcs.
     18 
     19 #ifndef FST_LIB_RMFINALEPSILON_H__
     20 #define FST_LIB_RMFINALEPSILON_H__
     21 
     22 #include <ext/hash_set>
     23 using __gnu_cxx::hash_set;
     24 
     25 #include "fst/lib/connect.h"
     26 #include "fst/lib/mutable-fst.h"
     27 
     28 namespace fst {
     29 
     30 template<class A>
     31 void RmFinalEpsilon(MutableFst<A>* fst) {
     32   typedef typename A::StateId StateId;
     33   typedef typename A::Weight Weight;
     34 
     35   // Determine the coaccesibility of states.
     36   vector<bool> access;
     37   vector<bool> coaccess;
     38   uint64 props = 0;
     39   SccVisitor<A> scc_visitor(0, &access, &coaccess, &props);
     40   DfsVisit(*fst, &scc_visitor);
     41 
     42   // Find potential list of removable final states. These are final states
     43   // that have no outgoing transitions or final states that have a
     44   // non-coaccessible future. Complexity O(S)
     45   hash_set<StateId> finals;
     46   for (StateIterator<Fst<A> > siter(*fst); !siter.Done(); siter.Next()) {
     47     StateId s = siter.Value();
     48     if (fst->Final(s) != Weight::Zero()) {
     49       bool future_coaccess = false;
     50       for (ArcIterator<Fst<A> > aiter(*fst, s); !aiter.Done(); aiter.Next()) {
     51         const A& arc = aiter.Value();
     52         if (coaccess[arc.nextstate]) {
     53           future_coaccess = true;
     54           break;
     55         }
     56       }
     57       if (!future_coaccess) {
     58         finals.insert(s);
     59       }
     60     }
     61   }
     62 
     63   // Move the final weight. Complexity O(E)
     64   vector<A> arcs;
     65   for (StateIterator<Fst<A> > siter(*fst); !siter.Done(); siter.Next()) {
     66     StateId s = siter.Value();
     67     Weight w(fst->Final(s));
     68 
     69     arcs.clear();
     70     for (ArcIterator<Fst<A> > aiter(*fst, s); !aiter.Done(); aiter.Next()) {
     71       const A& arc = aiter.Value();
     72       // is next state in the list of finals
     73       if (finals.find(arc.nextstate) != finals.end()) {
     74         // sum up all epsilon arcs
     75         if (arc.ilabel == 0 && arc.olabel == 0) {
     76           w = Plus(Times(fst->Final(arc.nextstate), arc.weight), w);
     77         } else {
     78           arcs.push_back(arc);
     79         }
     80       } else {
     81         arcs.push_back(arc);
     82       }
     83     }
     84 
     85     // If some arcs (epsilon arcs) were deleted, delete all
     86     // arcs and add back only the non epsilon arcs
     87     if (arcs.size() < fst->NumArcs(s)) {
     88       fst->DeleteArcs(s);
     89       fst->SetFinal(s, w);
     90       for (size_t i = 0; i < arcs.size(); ++i) {
     91         fst->AddArc(s, arcs[i]);
     92       }
     93     }
     94   }
     95 
     96   Connect(fst);
     97 }
     98 
     99 }
    100 
    101 #endif  // FST_LIB_RMFINALEPSILON_H__
    102