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@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 // 43 // When 'require_superinitial == false', a superinitial state is 44 // *not* created in the reversed Fst iff the input Fst has exactly 45 // 1 final state (which becomes the initial state of the reversed Fst) 46 // that has a final weight of Weight::One() *or* does not belong to 47 // any cycle. 48 // When 'require_superinitial == true', a superinitial state is 49 // always created. 50 template<class Arc, class RevArc> 51 void Reverse(const Fst<Arc> &ifst, MutableFst<RevArc> *ofst, 52 bool require_superinitial = true) { 53 typedef typename Arc::StateId StateId; 54 typedef typename Arc::Weight Weight; 55 typedef typename RevArc::Weight RevWeight; 56 57 ofst->DeleteStates(); 58 ofst->SetInputSymbols(ifst.InputSymbols()); 59 ofst->SetOutputSymbols(ifst.OutputSymbols()); 60 if (ifst.Properties(kExpanded, false)) 61 ofst->ReserveStates(CountStates(ifst) + 1); 62 StateId istart = ifst.Start(); 63 StateId ostart = kNoStateId; 64 StateId offset = 0; 65 uint64 dfs_iprops = 0, dfs_oprops = 0; 66 67 if (!require_superinitial) { 68 for (StateIterator<Fst<Arc> > siter(ifst); 69 !siter.Done(); 70 siter.Next()) { 71 StateId is = siter.Value(); 72 if (ifst.Final(is) == Weight::Zero()) continue; 73 if (ostart != kNoStateId) { 74 ostart = kNoStateId; 75 break; 76 } else { 77 ostart = is; 78 } 79 } 80 81 if (ostart != kNoStateId && ifst.Final(ostart) != Weight::One()) { 82 vector<StateId> scc; 83 SccVisitor<Arc> scc_visitor(&scc, 0, 0, &dfs_iprops); 84 DfsVisit(ifst, &scc_visitor); 85 if (count(scc.begin(), scc.end(), scc[ostart]) > 1) { 86 ostart = kNoStateId; 87 } else { 88 for (ArcIterator<Fst<Arc> > aiter(ifst, ostart); 89 !aiter.Done(); aiter.Next()) { 90 if (aiter.Value().nextstate == ostart) { 91 ostart = kNoStateId; 92 break; 93 } 94 } 95 } 96 if (ostart != kNoStateId) 97 dfs_oprops = kInitialAcyclic; 98 } 99 } 100 101 if (ostart == kNoStateId) { // Super-initial requested or needed. 102 ostart = ofst->AddState(); 103 offset = 1; 104 } 105 106 for (StateIterator<Fst<Arc> > siter(ifst); 107 !siter.Done(); 108 siter.Next()) { 109 StateId is = siter.Value(); 110 StateId os = is + offset; 111 while (ofst->NumStates() <= os) 112 ofst->AddState(); 113 if (is == istart) 114 ofst->SetFinal(os, RevWeight::One()); 115 116 Weight final = ifst.Final(is); 117 if ((final != Weight::Zero()) && (offset == 1)) { 118 RevArc oarc(0, 0, final.Reverse(), os); 119 ofst->AddArc(0, oarc); 120 } 121 122 for (ArcIterator<Fst<Arc> > aiter(ifst, is); 123 !aiter.Done(); 124 aiter.Next()) { 125 const Arc &iarc = aiter.Value(); 126 StateId nos = iarc.nextstate + offset; 127 typename RevArc::Weight weight = iarc.weight.Reverse(); 128 if (!offset && (nos == ostart)) 129 weight = Times(ifst.Final(ostart).Reverse(), weight); 130 RevArc oarc(iarc.ilabel, iarc.olabel, weight, os); 131 while (ofst->NumStates() <= nos) 132 ofst->AddState(); 133 ofst->AddArc(nos, oarc); 134 } 135 } 136 ofst->SetStart(ostart); 137 if (offset == 0 && ostart == istart) 138 ofst->SetFinal(ostart, ifst.Final(ostart).Reverse()); 139 140 uint64 iprops = ifst.Properties(kCopyProperties, false) | dfs_iprops; 141 uint64 oprops = ofst->Properties(kFstProperties, false) | dfs_oprops; 142 ofst->SetProperties(ReverseProperties(iprops, offset == 1) | oprops, 143 kFstProperties); 144 } 145 146 } // namespace fst 147 148 #endif // FST_LIB_REVERSE_H__ 149