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 <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
31namespace fst {
32
33enum 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.
47template <class Arc>
48void 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