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> 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