rmfinalepsilon.h revision 8fc5a7f51e62cb4ae44a27bdf4176d04adc80ede
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// rmfinalepsilon.h 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Licensed under the Apache License, Version 2.0 (the "License"); 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// you may not use this file except in compliance with the License. 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// You may obtain a copy of the License at 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// http://www.apache.org/licenses/LICENSE-2.0 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Unless required by applicable law or agreed to in writing, software 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// distributed under the License is distributed on an "AS IS" BASIS, 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1246d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles)// See the License for the specific language governing permissions and 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// limitations under the License. 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 16eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch// \file 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Function to remove of final states that have epsilon only input arcs. 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 19d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles)#ifndef FST_LIB_RMFINALEPSILON_H__ 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define FST_LIB_RMFINALEPSILON_H__ 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 22d0247b1b59f9c528cb6df88b4f2b9afaf80d181eTorne (Richard Coles)#include <ext/hash_set> 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)using __gnu_cxx::hash_set; 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "fst/lib/connect.h" 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "fst/lib/mutable-fst.h" 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace fst { 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template<class A> 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void RmFinalEpsilon(MutableFst<A>* fst) { 3246d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) typedef typename A::StateId StateId; 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef typename A::Weight Weight; 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Determine the coaccesibility of states. 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) vector<bool> access; 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) vector<bool> coaccess; 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64 props = 0; 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SccVisitor<A> scc_visitor(0, &access, &coaccess, &props); 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DfsVisit(*fst, &scc_visitor); 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Find potential list of removable final states. These are final states 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // that have no outgoing transitions or final states that have a 4446d4c2bc3267f3f028f39e7e311b0f89aba2e4fdTorne (Richard Coles) // non-coaccessible future. Complexity O(S) 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) hash_set<StateId> finals; 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (StateIterator<Fst<A> > siter(*fst); !siter.Done(); siter.Next()) { 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StateId s = siter.Value(); 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (fst->Final(s) != Weight::Zero()) { 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool future_coaccess = false; 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (ArcIterator<Fst<A> > aiter(*fst, s); !aiter.Done(); aiter.Next()) { 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const A& arc = aiter.Value(); 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (coaccess[arc.nextstate]) { 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) future_coaccess = true; 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!future_coaccess) { 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) finals.insert(s); 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Move the final weight. Complexity O(E) 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) vector<A> arcs; 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (StateIterator<Fst<A> > siter(*fst); !siter.Done(); siter.Next()) { 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StateId s = siter.Value(); 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Weight w(fst->Final(s)); 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) arcs.clear(); 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (ArcIterator<Fst<A> > aiter(*fst, s); !aiter.Done(); aiter.Next()) { 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const A& arc = aiter.Value(); 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // is next state in the list of finals 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (finals.find(arc.nextstate) != finals.end()) { 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // sum up all epsilon arcs 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (arc.ilabel == 0 && arc.olabel == 0) { 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) w = Plus(Times(fst->Final(arc.nextstate), arc.weight), w); 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) arcs.push_back(arc); 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) arcs.push_back(arc); 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If some arcs (epsilon arcs) were deleted, delete all 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // arcs and add back only the non epsilon arcs 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (arcs.size() < fst->NumArcs(s)) { 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fst->DeleteArcs(s); 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fst->SetFinal(s, w); 90a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) for (size_t i = 0; i < arcs.size(); ++i) { 91a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) fst->AddArc(s, arcs[i]); 92a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) } 93a3f6a49ab37290eeeb8db0f41ec0f1cb74a68be7Torne (Richard Coles) } 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Connect(fst); 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif // FST_LIB_RMFINALEPSILON_H__ 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)