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// Copyright 2005-2010 Google, Inc. 16// Author: johans@google.com (Johan Schalkwyk) 17// 18// \file 19// Function to remove of final states that have epsilon only input arcs. 20 21#ifndef FST_LIB_RMFINALEPSILON_H__ 22#define FST_LIB_RMFINALEPSILON_H__ 23 24#include <tr1/unordered_set> 25using std::tr1::unordered_set; 26using std::tr1::unordered_multiset; 27#include <vector> 28using std::vector; 29 30#include <fst/connect.h> 31#include <fst/mutable-fst.h> 32 33 34namespace fst { 35 36template<class A> 37void RmFinalEpsilon(MutableFst<A>* fst) { 38 typedef typename A::StateId StateId; 39 typedef typename A::Weight Weight; 40 41 // Determine the coaccesibility of states. 42 vector<bool> access; 43 vector<bool> coaccess; 44 uint64 props = 0; 45 SccVisitor<A> scc_visitor(0, &access, &coaccess, &props); 46 DfsVisit(*fst, &scc_visitor); 47 48 // Find potential list of removable final states. These are final states 49 // that have no outgoing transitions or final states that have a 50 // non-coaccessible future. Complexity O(S) 51 unordered_set<StateId> finals; 52 for (StateIterator<Fst<A> > siter(*fst); !siter.Done(); siter.Next()) { 53 StateId s = siter.Value(); 54 if (fst->Final(s) != Weight::Zero()) { 55 bool future_coaccess = false; 56 for (ArcIterator<Fst<A> > aiter(*fst, s); !aiter.Done(); aiter.Next()) { 57 const A& arc = aiter.Value(); 58 if (coaccess[arc.nextstate]) { 59 future_coaccess = true; 60 break; 61 } 62 } 63 if (!future_coaccess) { 64 finals.insert(s); 65 } 66 } 67 } 68 69 // Move the final weight. Complexity O(E) 70 vector<A> arcs; 71 for (StateIterator<Fst<A> > siter(*fst); !siter.Done(); siter.Next()) { 72 StateId s = siter.Value(); 73 Weight w(fst->Final(s)); 74 75 arcs.clear(); 76 for (ArcIterator<Fst<A> > aiter(*fst, s); !aiter.Done(); aiter.Next()) { 77 const A& arc = aiter.Value(); 78 // is next state in the list of finals 79 if (finals.find(arc.nextstate) != finals.end()) { 80 // sum up all epsilon arcs 81 if (arc.ilabel == 0 && arc.olabel == 0) { 82 w = Plus(Times(fst->Final(arc.nextstate), arc.weight), w); 83 } else { 84 arcs.push_back(arc); 85 } 86 } else { 87 arcs.push_back(arc); 88 } 89 } 90 91 // If some arcs (epsilon arcs) were deleted, delete all 92 // arcs and add back only the non epsilon arcs 93 if (arcs.size() < fst->NumArcs(s)) { 94 fst->DeleteArcs(s); 95 fst->SetFinal(s, w); 96 for (size_t i = 0; i < arcs.size(); ++i) { 97 fst->AddArc(s, arcs[i]); 98 } 99 } 100 } 101 102 Connect(fst); 103} 104 105} // namespace fst 106 107#endif // FST_LIB_RMFINALEPSILON_H__ 108