14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// rmfinalepsilon.h 24a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 34a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Licensed under the Apache License, Version 2.0 (the "License"); 44a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// you may not use this file except in compliance with the License. 54a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// You may obtain a copy of the License at 64a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 74a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// http://www.apache.org/licenses/LICENSE-2.0 84a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 94a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Unless required by applicable law or agreed to in writing, software 104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// distributed under the License is distributed on an "AS IS" BASIS, 114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// See the License for the specific language governing permissions and 134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// limitations under the License. 144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// \file 174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Function to remove of final states that have epsilon only input arcs. 184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef FST_LIB_RMFINALEPSILON_H__ 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define FST_LIB_RMFINALEPSILON_H__ 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <ext/hash_set> 234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectusing __gnu_cxx::hash_set; 244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/connect.h" 264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include "fst/lib/mutable-fst.h" 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectnamespace fst { 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate<class A> 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectvoid RmFinalEpsilon(MutableFst<A>* fst) { 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::StateId StateId; 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project typedef typename A::Weight Weight; 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Determine the coaccesibility of states. 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<bool> access; 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<bool> coaccess; 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project uint64 props = 0; 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project SccVisitor<A> scc_visitor(0, &access, &coaccess, &props); 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project DfsVisit(*fst, &scc_visitor); 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Find potential list of removable final states. These are final states 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // that have no outgoing transitions or final states that have a 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // non-coaccessible future. Complexity O(S) 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project hash_set<StateId> finals; 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateIterator<Fst<A> > siter(*fst); !siter.Done(); siter.Next()) { 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId s = siter.Value(); 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (fst->Final(s) != Weight::Zero()) { 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool future_coaccess = false; 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (ArcIterator<Fst<A> > aiter(*fst, s); !aiter.Done(); aiter.Next()) { 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const A& arc = aiter.Value(); 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (coaccess[arc.nextstate]) { 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project future_coaccess = true; 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project break; 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (!future_coaccess) { 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project finals.insert(s); 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Move the final weight. Complexity O(E) 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<A> arcs; 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (StateIterator<Fst<A> > siter(*fst); !siter.Done(); siter.Next()) { 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project StateId s = siter.Value(); 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Weight w(fst->Final(s)); 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arcs.clear(); 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (ArcIterator<Fst<A> > aiter(*fst, s); !aiter.Done(); aiter.Next()) { 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project const A& arc = aiter.Value(); 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // is next state in the list of finals 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (finals.find(arc.nextstate) != finals.end()) { 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // sum up all epsilon arcs 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (arc.ilabel == 0 && arc.olabel == 0) { 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project w = Plus(Times(fst->Final(arc.nextstate), arc.weight), w); 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arcs.push_back(arc); 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project arcs.push_back(arc); 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // If some arcs (epsilon arcs) were deleted, delete all 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // arcs and add back only the non epsilon arcs 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (arcs.size() < fst->NumArcs(s)) { 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->DeleteArcs(s); 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->SetFinal(s, w); 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project for (size_t i = 0; i < arcs.size(); ++i) { 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project fst->AddArc(s, arcs[i]); 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Connect(fst); 974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif // FST_LIB_RMFINALEPSILON_H__ 102