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