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