epsnormalize.h revision 5b6dc79427b8f7eeb6a7ff68034ab8548ce670ea 
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 <tr1/unordered_map>
25using std::tr1::unordered_map;
26using std::tr1::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
35namespace fst {
36
37enum 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.
51template <class Arc>
52void EpsNormalize(const Fst<Arc> &ifst, MutableFst<Arc> *ofst,
53                      EpsNormalizeType type = EPS_NORM_INPUT) {
54  VectorFst< GallicArc<Arc, STRING_RIGHT_RESTRICT> > gfst;
55  if (type == EPS_NORM_INPUT)
56    ArcMap(ifst, &gfst, ToGallicMapper<Arc, STRING_RIGHT_RESTRICT>());
57  else // type == EPS_NORM_OUTPUT
58    ArcMap(InvertFst<Arc>(ifst), &gfst,
59           ToGallicMapper<Arc, STRING_RIGHT_RESTRICT>());
60  RmEpsilon(&gfst);
61  FactorWeightFst< GallicArc<Arc, STRING_RIGHT_RESTRICT>,
62    GallicFactor<typename Arc::Label,
63      typename Arc::Weight, STRING_RIGHT_RESTRICT> >
64    fwfst(gfst);
65  ArcMap(fwfst, ofst, FromGallicMapper<Arc, STRING_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