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> 26using std::vector; 27 28#include <fst/cache.h> 29 30 31namespace 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. 42template<class Arc, class RevArc> 43void 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