Home | History | Annotate | Download | only in fst 
      1 // reverse.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: riley (at) google.com (Michael Riley)
     17 //
     18 // \file
     19 // Functions and classes to sort arcs in an FST.
     20 
     21 #ifndef FST_LIB_REVERSE_H__
     22 #define FST_LIB_REVERSE_H__
     23 
     24 #include <algorithm>
     25 #include <vector>
     26 using std::vector;
     27 
     28 #include <fst/cache.h>
     29 
     30 
     31 namespace fst {
     32 
     33 // Reverses an FST. The reversed result is written to an output
     34 // MutableFst.  If A transduces string x to y with weight a, then the
     35 // reverse of A transduces the reverse of x to the reverse of y with
     36 // weight a.Reverse().
     37 //
     38 // Typically, a = a.Reverse() and Arc = RevArc (e.g. for
     39 // TropicalWeight or LogWeight).  In general, e.g. when the weights
     40 // only form a left or right semiring, the output arc type must match
     41 // the input arc type except having the reversed Weight type.
     42 template<class Arc, class RevArc>
     43 void Reverse(const Fst<Arc> &ifst, MutableFst<RevArc> *ofst) {
     44   typedef typename Arc::StateId StateId;
     45   typedef typename Arc::Weight Weight;
     46   typedef typename RevArc::Weight RevWeight;
     47 
     48   ofst->DeleteStates();
     49   ofst->SetInputSymbols(ifst.InputSymbols());
     50   ofst->SetOutputSymbols(ifst.OutputSymbols());
     51   if (ifst.Properties(kExpanded, false))
     52     ofst->ReserveStates(CountStates(ifst) + 1);
     53   StateId istart = ifst.Start();
     54   StateId ostart = ofst->AddState();
     55   ofst->SetStart(ostart);
     56 
     57   for (StateIterator< Fst<Arc> > siter(ifst);
     58        !siter.Done();
     59        siter.Next()) {
     60     StateId is = siter.Value();
     61     StateId os = is + 1;
     62     while (ofst->NumStates() <= os)
     63       ofst->AddState();
     64     if (is == istart)
     65       ofst->SetFinal(os, RevWeight::One());
     66 
     67     Weight final = ifst.Final(is);
     68     if (final != Weight::Zero()) {
     69       RevArc oarc(0, 0, final.Reverse(), os);
     70       ofst->AddArc(0, oarc);
     71     }
     72 
     73     for (ArcIterator< Fst<Arc> > aiter(ifst, is);
     74          !aiter.Done();
     75          aiter.Next()) {
     76       const Arc &iarc = aiter.Value();
     77       RevArc oarc(iarc.ilabel, iarc.olabel, iarc.weight.Reverse(), os);
     78       StateId nos = iarc.nextstate + 1;
     79       while (ofst->NumStates() <= nos)
     80         ofst->AddState();
     81       ofst->AddArc(nos, oarc);
     82     }
     83   }
     84   uint64 iprops = ifst.Properties(kCopyProperties, false);
     85   uint64 oprops = ofst->Properties(kFstProperties, false);
     86   ofst->SetProperties(ReverseProperties(iprops) | oprops, kFstProperties);
     87 }
     88 
     89 }  // namespace fst
     90 
     91 #endif  // FST_LIB_REVERSE_H__
     92