FST  openfst-1.7.1
OpenFst Library
invert.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 invert an FST.
5 
6 #ifndef FST_INVERT_H_
7 #define FST_INVERT_H_
8 
9 #include <fst/arc-map.h>
10 #include <fst/mutable-fst.h>
11 
12 
13 namespace fst {
14 
15 // Mapper to implement inversion of an arc.
16 template <class A>
17 struct InvertMapper {
18  using FromArc = A;
19  using ToArc = A;
20 
22 
23  ToArc operator()(const FromArc &arc) const {
24  return ToArc(arc.olabel, arc.ilabel, arc.weight, arc.nextstate);
25  }
26 
27  constexpr MapFinalAction FinalAction() const {
28  return MAP_NO_SUPERFINAL;
29  }
30 
32  return MAP_CLEAR_SYMBOLS;
33  }
34 
36  return MAP_CLEAR_SYMBOLS;
37  }
38 
39  uint64 Properties(uint64 props) const {
40  return InvertProperties(props);
41  }
42 };
43 
44 // Inverts the transduction corresponding to an FST by exchanging the
45 // FST's input and output labels.
46 //
47 // Complexity:
48 //
49 // Time: O(V + E)
50 // Space: O(1)
51 //
52 // where V is the number of states and E is the number of arcs.
53 template <class Arc>
54 inline void Invert(const Fst<Arc> &ifst, MutableFst<Arc> *ofst) {
55  std::unique_ptr<SymbolTable> input(
56  ifst.InputSymbols() ? ifst.InputSymbols()->Copy() : nullptr);
57  std::unique_ptr<SymbolTable> output(
58  ifst.OutputSymbols() ? ifst.OutputSymbols()->Copy() : nullptr);
59  ArcMap(ifst, ofst, InvertMapper<Arc>());
60  ofst->SetInputSymbols(output.get());
61  ofst->SetOutputSymbols(input.get());
62 }
63 
64 // Destructive variant of the above.
65 template <class Arc>
66 inline void Invert(MutableFst<Arc> *fst) {
67  std::unique_ptr<SymbolTable> input(
68  fst->InputSymbols() ? fst->InputSymbols()->Copy() : nullptr);
69  std::unique_ptr<SymbolTable> output(
70  fst->OutputSymbols() ? fst->OutputSymbols()->Copy() : nullptr);
71  ArcMap(fst, InvertMapper<Arc>());
72  fst->SetInputSymbols(output.get());
73  fst->SetOutputSymbols(input.get());
74 }
75 
76 // Inverts the transduction corresponding to an FST by exchanging the
77 // FST's input and output labels. This version is a delayed FST.
78 //
79 // Complexity:
80 //
81 // Time: O(v + e)
82 // Space: O(1)
83 //
84 // where v is the number of states visited and e is the number of arcs visited.
85 // Constant time and to visit an input state or arc is assumed and exclusive of
86 // caching.
87 template <class A>
88 class InvertFst : public ArcMapFst<A, A, InvertMapper<A>> {
89  public:
90  using Arc = A;
91 
94 
95  explicit InvertFst(const Fst<Arc> &fst)
96  : ArcMapFst<Arc, Arc, Mapper>(fst, Mapper()) {
97  GetMutableImpl()->SetOutputSymbols(fst.InputSymbols());
98  GetMutableImpl()->SetInputSymbols(fst.OutputSymbols());
99  }
100 
101  // See Fst<>::Copy() for doc.
102  InvertFst(const InvertFst<Arc> &fst, bool safe = false)
103  : ArcMapFst<Arc, Arc, Mapper>(fst, safe) {}
104 
105  // Get a copy of this InvertFst. See Fst<>::Copy() for further doc.
106  InvertFst<Arc> *Copy(bool safe = false) const override {
107  return new InvertFst(*this, safe);
108  }
109 
110  private:
112 };
113 
114 // Specialization for InvertFst.
115 template <class Arc>
117  : public StateIterator<ArcMapFst<Arc, Arc, InvertMapper<Arc>>> {
118  public:
121 };
122 
123 // Specialization for InvertFst.
124 template <class Arc>
126  : public ArcIterator<ArcMapFst<Arc, Arc, InvertMapper<Arc>>> {
127  public:
128  using StateId = typename Arc::StateId;
129 
131  : ArcIterator<ArcMapFst<Arc, Arc, InvertMapper<Arc>>>(fst, s) {}
132 };
133 
134 // Useful alias when using StdArc.
136 
137 } // namespace fst
138 
139 #endif // FST_INVERT_H_
typename Impl::Arc Arc
Definition: fst.h:871
MapSymbolsAction
Definition: arc-map.h:39
void ArcMap(MutableFst< A > *fst, C *mapper)
Definition: arc-map.h:94
ToArc operator()(const FromArc &arc) const
Definition: invert.h:23
void Invert(const Fst< Arc > &ifst, MutableFst< Arc > *ofst)
Definition: invert.h:54
typename ArcMapFst< Arc, Arc, InvertMapper< Arc > >::Arc Arc
Definition: fst.h:480
uint64_t uint64
Definition: types.h:32
StateIterator(const InvertFst< Arc > &fst)
Definition: invert.h:119
typename Arc::StateId StateId
Definition: invert.h:128
virtual SymbolTable * Copy() const
Definition: symbol-table.h:264
const SymbolTable * InputSymbols() const override=0
virtual void SetInputSymbols(const SymbolTable *isyms)=0
typename ArcMapFst< Arc, Arc, InvertMapper< Arc > >::Arc Arc
Definition: fst.h:374
constexpr MapSymbolsAction InputSymbolsAction() const
Definition: invert.h:31
InvertFst(const Fst< Arc > &fst)
Definition: invert.h:95
constexpr MapSymbolsAction OutputSymbolsAction() const
Definition: invert.h:35
const SymbolTable * OutputSymbols() const override=0
MapFinalAction
Definition: arc-map.h:24
uint64 Properties(uint64 props) const
Definition: invert.h:39
InvertFst< Arc > * Copy(bool safe=false) const override
Definition: invert.h:106
constexpr MapFinalAction FinalAction() const
Definition: invert.h:27
virtual const SymbolTable * InputSymbols() const =0
virtual void SetOutputSymbols(const SymbolTable *osyms)=0
InvertFst(const InvertFst< Arc > &fst, bool safe=false)
Definition: invert.h:102
ArcIterator(const InvertFst< Arc > &fst, StateId s)
Definition: invert.h:130
uint64 InvertProperties(uint64 inprops)
Definition: properties.cc:151
virtual const SymbolTable * OutputSymbols() const =0