FST  openfst-1.8.3 OpenFst Library
union.h
Go to the documentation of this file.
2 //
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
8 //
9 // Unless required by applicable law or agreed to in writing, software
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 compute the union of two FSTs.
19
20 #ifndef FST_UNION_H_
21 #define FST_UNION_H_
22
23 #include <algorithm>
24 #include <utility>
25 #include <vector>
26
27 #include <fst/log.h>
28 #include <fst/arc.h>
29 #include <fst/cache.h>
30 #include <fst/expanded-fst.h>
31 #include <fst/float-weight.h>
32 #include <fst/fst.h>
33 #include <fst/impl-to-fst.h>
34 #include <fst/mutable-fst.h>
35 #include <fst/properties.h>
36 #include <fst/rational.h>
37 #include <fst/symbol-table.h>
38 #include <fst/util.h>
39
40 namespace fst {
41
42 // Computes the union (sum) of two FSTs. This version writes the union to an
43 // output MutableFst. If A transduces string x to y with weight a and B
44 // transduces string w to v with weight b, then their union transduces x to y
45 // with weight a and w to v with weight b.
46 //
47 // Complexity:
48 //
49 // Time: (V_2 + E_2)
50 // Space: O(V_2 + E_2)
51 //
52 // where Vi is the number of states, and Ei is the number of arcs, in the ith
53 // FST.
54 template <class Arc>
55 void Union(MutableFst<Arc> *fst1, const Fst<Arc> &fst2) {
56  // Checks for symbol table compatibility.
57  if (!CompatSymbols(fst1->InputSymbols(), fst2.InputSymbols()) ||
58  !CompatSymbols(fst1->OutputSymbols(), fst2.OutputSymbols())) {
59  FSTERROR() << "Union: Input/output symbol tables of 1st argument "
60  << "do not match input/output symbol tables of 2nd argument";
61  fst1->SetProperties(kError, kError);
62  return;
63  }
64  const auto numstates1 = fst1->NumStates();
65  const bool initial_acyclic1 =
67  const auto props1 = fst1->Properties(kFstProperties, false);
68  const auto props2 = fst2.Properties(kFstProperties, false);
69  const auto start2 = fst2.Start();
70  if (start2 == kNoStateId) {
71  if (props2 & kError) fst1->SetProperties(kError, kError);
72  return;
73  }
74  if (std::optional<typename Arc::StateId> numstates2 =
75  fst2.NumStatesIfKnown()) {
76  fst1->ReserveStates(numstates1 + *numstates2 + (initial_acyclic1 ? 0 : 1));
77  }
78  for (StateIterator<Fst<Arc>> siter(fst2); !siter.Done(); siter.Next()) {
79  const auto s1 = fst1->AddState();
80  const auto s2 = siter.Value();
81  fst1->SetFinal(s1, fst2.Final(s2));
82  fst1->ReserveArcs(s1, fst2.NumArcs(s2));
83  for (ArcIterator<Fst<Arc>> aiter(fst2, s2); !aiter.Done(); aiter.Next()) {
84  auto arc = aiter.Value(); // Copy intended.
85  arc.nextstate += numstates1;
87  }
88  }
89  const auto start1 = fst1->Start();
90  if (start1 == kNoStateId) {
91  fst1->SetStart(start2);
92  fst1->SetProperties(props2, kCopyProperties);
93  return;
94  }
95  if (initial_acyclic1) {
96  fst1->AddArc(start1, Arc(0, 0, start2 + numstates1));
97  } else {
98  const auto nstart1 = fst1->AddState();
99  fst1->SetStart(nstart1);
101  fst1->AddArc(nstart1, Arc(0, 0, start2 + numstates1));
102  }
103  fst1->SetProperties(UnionProperties(props1, props2), kFstProperties);
104 }
105
106 // Same as the above but can handle arbitrarily many right-hand-side FSTs,
107 // preallocating the states.
108 template <class Arc>
109 void Union(MutableFst<Arc> *fst1, const std::vector<const Fst<Arc> *> &fsts2) {
110  // We add 1 just in case fst1 has an initial cycle.
111  fst1->ReserveStates(1 + fst1->NumStates() + CountStates(fsts2));
112  for (const auto *fst2 : fsts2) Union(fst1, *fst2);
113 }
114
115 // Computes the union of two FSTs, modifying the RationalFst argument.
116 template <class Arc>
117 void Union(RationalFst<Arc> *fst1, const Fst<Arc> &fst2) {
119 }
120
122
123 // Computes the union (sum) of two FSTs. This version is a delayed FST. If A
124 // transduces string x to y with weight a and B transduces string w to v with
125 // weight b, then their union transduces x to y with weight a and w to v with
126 // weight b.
127 //
128 // Complexity:
129 //
130 // Time: O(v_1 + e_1 + v_2 + e_2)
131 // Space: O(v_1 + v_2)
132 //
133 // where vi is the number of states visited, and ei is the number of arcs
134 // visited, in the ith FST. Constant time and space to visit an input state or
135 // arc is assumed and exclusive of caching.
136 template <class A>
137 class UnionFst : public RationalFst<A> {
138  public:
139  using Arc = A;
140  using StateId = typename Arc::StateId;
141  using Weight = typename Arc::Weight;
142
143  UnionFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2) {
144  GetMutableImpl()->InitUnion(fst1, fst2);
145  }
146
147  UnionFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2,
148  const UnionFstOptions &opts)
149  : RationalFst<Arc>(opts) {
150  GetMutableImpl()->InitUnion(fst1, fst2);
151  }
152
153  // See Fst<>::Copy() for doc.
154  UnionFst(const UnionFst &fst, bool safe = false)
155  : RationalFst<Arc>(fst, safe) {}
156
157  // Gets a copy of this UnionFst. See Fst<>::Copy() for further doc.
158  UnionFst *Copy(bool safe = false) const override {
159  return new UnionFst(*this, safe);
160  }
161
162  private:
165 };
166
167 // Specialization for UnionFst.
168 template <class Arc>
169 class StateIterator<UnionFst<Arc>> : public StateIterator<RationalFst<Arc>> {
170  public:
171  explicit StateIterator(const UnionFst<Arc> &fst)
172  : StateIterator<RationalFst<Arc>>(fst) {}
173 };
174
175 // Specialization for UnionFst.
176 template <class Arc>
177 class ArcIterator<UnionFst<Arc>> : public ArcIterator<RationalFst<Arc>> {
178  public:
179  using StateId = typename Arc::StateId;
180
182  : ArcIterator<RationalFst<Arc>>(fst, s) {}
183 };
184
186
187 } // namespace fst
188
189 #endif // FST_UNION_H_
virtual uint64_t Properties(uint64_t mask, bool test) const =0
StateIterator(const UnionFst< Arc > &fst)
Definition: union.h:171
virtual size_t NumArcs(StateId) const =0
const SymbolTable * InputSymbols() const override=0
constexpr uint64_t kError
Definition: properties.h:52
constexpr uint64_t kInitialAcyclic
Definition: properties.h:116
virtual Weight Final(StateId) const =0
virtual void SetStart(StateId)=0
typename ReplaceFst< Arc >::Arc Arc
Definition: fst.h:408
CacheOptions RationalFstOptions
Definition: rational.h:42
constexpr int kNoStateId
Definition: fst.h:196
virtual void ReserveArcs(StateId, size_t)
Definition: mutable-fst.h:104
#define FSTERROR()
Definition: util.h:56
UnionFst(const Fst< Arc > &fst1, const Fst< Arc > &fst2)
Definition: union.h:143
const SymbolTable * OutputSymbols() const override=0
typename Arc::StateId StateId
Definition: rational.h:276
uint64_t UnionProperties(uint64_t inprops1, uint64_t inprops2, bool delayed=false)
Definition: properties.cc:393
void Union(RationalFst< Arc > *fst1, const Fst< Arc > &fst2)
Definition: union.h:117
constexpr uint64_t kCopyProperties
Definition: properties.h:163
virtual void SetProperties(uint64_t props, uint64_t mask)=0
typename Arc::StateId StateId
Definition: rational.h:321
virtual StateId Start() const =0
virtual std::optional< StateId > NumStatesIfKnown() const
Definition: fst.h:228
constexpr uint64_t kFstProperties
Definition: properties.h:326
virtual void AddArc(StateId, const Arc &)=0
typename ReplaceFst< Arc >::Arc Arc
Definition: cache.h:1202
virtual const SymbolTable * InputSymbols() const =0
Arc::StateId CountStates(const Fst< Arc > &fst)
Definition: expanded-fst.h:179
virtual void ReserveStates(size_t)
Definition: mutable-fst.h:101
virtual void SetFinal(StateId s, Weight weight=Weight::One())=0
ArcIterator(const UnionFst< Arc > &fst, StateId s)
Definition: union.h:181
typename Arc::Weight Weight
Definition: union.h:141
UnionFst(const Fst< Arc > &fst1, const Fst< Arc > &fst2, const UnionFstOptions &opts)
Definition: union.h:147
bool CompatSymbols(const SymbolTable *syms1, const SymbolTable *syms2, bool warning=true)
UnionFst(const UnionFst &fst, bool safe=false)
Definition: union.h:154
internal::RationalFstImpl< A > * GetMutableImpl() const
Definition: impl-to-fst.h:125
virtual StateId NumStates() const =0
UnionFst * Copy(bool safe=false) const override
Definition: union.h:158
const internal::RationalFstImpl< A > * GetImpl() const
Definition: impl-to-fst.h:123
virtual const SymbolTable * OutputSymbols() const =0