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