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>
25 using std::unordered_map;
26 using std::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, GALLIC_RIGHT_RESTRICT> > gfst;
55   if (type == EPS_NORM_INPUT)
56     ArcMap(ifst, &gfst, ToGallicMapper<Arc, GALLIC_RIGHT_RESTRICT>());
57   else // type == EPS_NORM_OUTPUT
58     ArcMap(InvertFst<Arc>(ifst), &gfst,
59            ToGallicMapper<Arc, GALLIC_RIGHT_RESTRICT>());
60   RmEpsilon(&gfst);
61   FactorWeightFst< GallicArc<Arc, GALLIC_RIGHT_RESTRICT>,
62     GallicFactor<typename Arc::Label,
63       typename Arc::Weight, GALLIC_RIGHT_RESTRICT> >
64     fwfst(gfst);
65   ArcMap(fwfst, ofst, FromGallicMapper<Arc, GALLIC_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