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