openfst-1.2.6/src/include/fst/reverse.h

Go to the documentation of this file.

///  reverse.h

///  Licensed under the Apache License, Version 2.0 (the "License");
///  you may not use this file except in compliance with the License.
///  You may obtain a copy of the License at
/// 
///      http://www.apache.org/licenses/LICENSE-2.0
/// 
///  Unless required by applicable law or agreed to in writing, software
///  distributed under the License is distributed on an "AS IS" BASIS,
///  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
///  See the License for the specific language governing permissions and
///  limitations under the License.
/// 
///  Copyright 2005-2010 Google, Inc.
///  Author: riley@google.com (Michael Riley)
/// 
///  \file
///  Functions and classes to sort arcs in an FST.

#ifndef FST_LIB_REVERSE_H__
#define FST_LIB_REVERSE_H__

#include <algorithm>
#include <vector>
using std::vector;

#include <fst/cache.h>

namespace fst {

///  Reverses an FST. The reversed result is written to an output
///  MutableFst.  If A transduces string x to y with weight a, then the
///  reverse of A transduces the reverse of x to the reverse of y with
///  weight a.Reverse().
/// 
///  Typically, a = a.Reverse() and Arc = RevArc (e.g. for
///  TropicalWeight or LogWeight).  In general, e.g. when the weights
///  only form a left or right semiring, the output arc type must match
///  the input arc type except having the reversed Weight type.
template<class Arc, class RevArc>
void Reverse(const Fst<Arc> &ifst, MutableFst<RevArc> *ofst) {
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Weight Weight;
  typedef typename RevArc::Weight RevWeight;

  ofst->DeleteStates();
  ofst->SetInputSymbols(ifst.InputSymbols());
  ofst->SetOutputSymbols(ifst.OutputSymbols());
  StateId istart = ifst.Start();
  StateId ostart = ofst->AddState();
  ofst->SetStart(ostart);

  for (StateIterator< Fst<Arc> > siter(ifst);
       !siter.Done();
       siter.Next()) {
    StateId is = siter.Value();
    StateId os = is + 1;
    while (ofst->NumStates() <= os)
      ofst->AddState();
    if (is == istart)
      ofst->SetFinal(os, RevWeight::One());

    Weight final = ifst.Final(is);
    if (final != Weight::Zero()) {
      RevArc oarc(0, 0, final.Reverse(), os);
      ofst->AddArc(0, oarc);
    }

    for (ArcIterator< Fst<Arc> > aiter(ifst, is);
         !aiter.Done();
         aiter.Next()) {
      const Arc &iarc = aiter.Value();
      RevArc oarc(iarc.ilabel, iarc.olabel, iarc.weight.Reverse(), os);
      StateId nos = iarc.nextstate + 1;
      while (ofst->NumStates() <= nos)
        ofst->AddState();
      ofst->AddArc(nos, oarc);
    }
  }
  uint64 iprops = ifst.Properties(kCopyProperties, false);
  uint64 oprops = ofst->Properties(kFstProperties, false);
  ofst->SetProperties(ReverseProperties(iprops) | oprops, kFstProperties);
}

}  ///  namespace fst

#endif  ///  FST_LIB_REVERSE_H__