1 // epsnormalize.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: allauzen (at) google.com (Cyril Allauzen) 17 // 18 // \file 19 // Function that implements epsilon normalization. 20 21 #ifndef FST_LIB_EPSNORMALIZE_H__ 22 #define FST_LIB_EPSNORMALIZE_H__ 23 24 #include <tr1/unordered_map> 25 using std::tr1::unordered_map; 26 using std::tr1::unordered_multimap; 27 28 29 #include <fst/factor-weight.h> 30 #include <fst/invert.h> 31 #include <fst/arc-map.h> 32 #include <fst/rmepsilon.h> 33 34 35 namespace fst { 36 37 enum EpsNormalizeType {EPS_NORM_INPUT, EPS_NORM_OUTPUT}; 38 39 // Returns an equivalent FST that is epsilon-normalized. An acceptor is 40 // epsilon-normalized if it is epsilon-removed. A transducer is input 41 // epsilon-normalized if additionally if on each path any epsilon input 42 // label follows all non-epsilon input labels. Output epsilon-normalized 43 // is defined similarly. 44 // 45 // The input FST needs to be functional. 46 // 47 // References: 48 // - Mehryar Mohri. "Generic epsilon-removal and input epsilon-normalization 49 // algorithms for weighted transducers", International Journal of Computer 50 // Science, 13(1): 129-143, 2002. 51 template <class Arc> 52 void EpsNormalize(const Fst<Arc> &ifst, MutableFst<Arc> *ofst, 53 EpsNormalizeType type = EPS_NORM_INPUT) { 54 VectorFst< GallicArc<Arc, STRING_RIGHT_RESTRICT> > gfst; 55 if (type == EPS_NORM_INPUT) 56 ArcMap(ifst, &gfst, ToGallicMapper<Arc, STRING_RIGHT_RESTRICT>()); 57 else // type == EPS_NORM_OUTPUT 58 ArcMap(InvertFst<Arc>(ifst), &gfst, 59 ToGallicMapper<Arc, STRING_RIGHT_RESTRICT>()); 60 RmEpsilon(&gfst); 61 FactorWeightFst< GallicArc<Arc, STRING_RIGHT_RESTRICT>, 62 GallicFactor<typename Arc::Label, 63 typename Arc::Weight, STRING_RIGHT_RESTRICT> > 64 fwfst(gfst); 65 ArcMap(fwfst, ofst, FromGallicMapper<Arc, STRING_RIGHT_RESTRICT>()); 66 ofst->SetOutputSymbols(ifst.OutputSymbols()); 67 if(type == EPS_NORM_OUTPUT) 68 Invert(ofst); 69 } 70 71 } // namespace fst 72 73 #endif // FST_LIB_EPSNORMALIZE_H__ 74
