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