Home | History | Annotate | Download | only in lib
      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 (at) 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 
     31 namespace fst {
     32 
     33 enum 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.
     47 template <class Arc>
     48 void 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