FST  openfst-1.7.1 OpenFst Library
reverse.h
Go to the documentation of this file.
1 // See www.openfst.org for extensive documentation on this weighted
2 // finite-state transducer library.
3 //
4 // Functions and classes to sort arcs in an FST.
5
6 #ifndef FST_REVERSE_H_
7 #define FST_REVERSE_H_
8
9 #include <algorithm>
10 #include <vector>
11
12 #include <fst/cache.h>
13
14
15 namespace fst {
16
17 // Reverses an FST. The reversed result is written to an output mutable FST.
18 // If A transduces string x to y with weight a, then the reverse of A
19 // transduces the reverse of x to the reverse of y with weight a.Reverse().
20 //
21 // Typically, a = a.Reverse() and an arc is its own reverse (e.g., for
22 // TropicalWeight or LogWeight). In general, e.g., when the weights only form a
23 // left or right semiring, the output arc type must match the input arc type
24 // except having the reversed Weight type.
25 //
26 // When require_superinitial is false, a superinitial state is not created in
27 // the reversed FST iff the input FST has exactly one final state (which becomes
28 // the initial state of the reversed FST) with a final weight of semiring One,
29 // or if it does not belong to any cycle. When require_superinitial is true, a
30 // superinitial state is always created.
31 template <class FromArc, class ToArc>
32 void Reverse(const Fst<FromArc> &ifst, MutableFst<ToArc> *ofst,
33  bool require_superinitial = true) {
34  using StateId = typename FromArc::StateId;
35  using FromWeight = typename FromArc::Weight;
36  using ToWeight = typename ToArc::Weight;
37  ofst->DeleteStates();
38  ofst->SetInputSymbols(ifst.InputSymbols());
39  ofst->SetOutputSymbols(ifst.OutputSymbols());
40  if (ifst.Properties(kExpanded, false)) {
41  ofst->ReserveStates(CountStates(ifst) + 1);
42  }
43  StateId istart = ifst.Start();
44  StateId ostart = kNoStateId;
45  StateId offset = 0;
46  uint64 dfs_iprops = 0;
47  uint64 dfs_oprops = 0;
48  if (!require_superinitial) {
49  for (StateIterator<Fst<FromArc>> siter(ifst); !siter.Done(); siter.Next()) {
50  const auto s = siter.Value();
51  if (ifst.Final(s) == FromWeight::Zero()) continue;
52  if (ostart != kNoStateId) {
53  ostart = kNoStateId;
54  break;
55  } else {
56  ostart = s;
57  }
58  }
59  if (ostart != kNoStateId && ifst.Final(ostart) != FromWeight::One()) {
60  std::vector<StateId> scc;
61  SccVisitor<FromArc> scc_visitor(&scc, nullptr, nullptr, &dfs_iprops);
62  DfsVisit(ifst, &scc_visitor);
63  if (count(scc.begin(), scc.end(), scc[ostart]) > 1) {
64  ostart = kNoStateId;
65  } else {
66  for (ArcIterator<Fst<FromArc>> aiter(ifst, ostart); !aiter.Done();
67  aiter.Next()) {
68  if (aiter.Value().nextstate == ostart) {
69  ostart = kNoStateId;
70  break;
71  }
72  }
73  }
74  if (ostart != kNoStateId) dfs_oprops = kInitialAcyclic;
75  }
76  }
77  if (ostart == kNoStateId) { // Super-initial requested or needed.
79  offset = 1;
80  }
81  for (StateIterator<Fst<FromArc>> siter(ifst); !siter.Done(); siter.Next()) {
82  const auto is = siter.Value();
83  const auto os = is + offset;
84  while (ofst->NumStates() <= os) ofst->AddState();
85  if (is == istart) ofst->SetFinal(os, ToWeight::One());
86  const auto weight = ifst.Final(is);
87  if ((weight != FromWeight::Zero()) && (offset == 1)) {
88  const ToArc oarc(0, 0, weight.Reverse(), os);
90  }
91  for (ArcIterator<Fst<FromArc>> aiter(ifst, is); !aiter.Done();
92  aiter.Next()) {
93  const auto &iarc = aiter.Value();
94  const auto nos = iarc.nextstate + offset;
95  auto weight = iarc.weight.Reverse();
96  if (!offset && (nos == ostart)) {
97  weight = Times(ifst.Final(ostart).Reverse(), weight);
98  }
99  const ToArc oarc(iarc.ilabel, iarc.olabel, weight, os);
100  while (ofst->NumStates() <= nos) ofst->AddState();
102  }
103  }
104  ofst->SetStart(ostart);
105  if (offset == 0 && ostart == istart) {
106  ofst->SetFinal(ostart, ifst.Final(ostart).Reverse());
107  }
108  const auto iprops = ifst.Properties(kCopyProperties, false) | dfs_iprops;
109  const auto oprops = ofst->Properties(kFstProperties, false) | dfs_oprops;
110  ofst->SetProperties(ReverseProperties(iprops, offset == 1) | oprops,
112 }
113
114 } // namespace fst
115
116 #endif // FST_REVERSE_H_
constexpr uint64 kInitialAcyclic
Definition: properties.h:97
uint64_t uint64
Definition: types.h:32
virtual void AddArc(StateId, const Arc &arc)=0
void DfsVisit(const FST &fst, Visitor *visitor, ArcFilter filter, bool access_only=false)
Definition: dfs-visit.h:94
virtual void SetInputSymbols(const SymbolTable *isyms)=0
virtual Weight Final(StateId) const =0
ExpectationWeight< X1, X2 > Times(const ExpectationWeight< X1, X2 > &w1, const ExpectationWeight< X1, X2 > &w2)
virtual void SetStart(StateId)=0
constexpr uint64 kFstProperties
Definition: properties.h:301
constexpr uint64 kCopyProperties
Definition: properties.h:138
constexpr int kNoStateId
Definition: fst.h:180
constexpr uint64 kExpanded
Definition: properties.h:27
void Reverse(const Fst< Arc > &ifst, const std::vector< std::pair< typename Arc::Label, typename Arc::Label >> &parens, std::vector< typename Arc::Label > *assignments, MutableFst< RevArc > *ofst)
Definition: reverse.h:20
virtual uint64 Properties(uint64 mask, bool test) const =0
virtual void SetFinal(StateId, Weight)=0
virtual StateId Start() const =0
uint64 ReverseProperties(uint64 inprops, bool has_superinitial)
Definition: properties.cc:318
virtual void ReserveStates(StateId n)
Definition: mutable-fst.h:76
virtual const SymbolTable * InputSymbols() const =0
Arc::StateId CountStates(const Fst< Arc > &fst)
Definition: expanded-fst.h:154