FST  openfst-1.7.1 OpenFst Library
union.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 compute the union of two FSTs.
5
6 #ifndef FST_UNION_H_
7 #define FST_UNION_H_
8
9 #include <algorithm>
10 #include <utility>
11 #include <vector>
12
13 #include <fst/mutable-fst.h>
14 #include <fst/rational.h>
15
16
17 namespace fst {
18
19 // Computes the union (sum) of two FSTs. This version writes the union to an
20 // output MutableFst. If A transduces string x to y with weight a and B
21 // transduces string w to v with weight b, then their union transduces x to y
22 // with weight a and w to v with weight b.
23 //
24 // Complexity:
25 //
26 // Time: (V_2 + E_2)
27 // Space: O(V_2 + E_2)
28 //
29 // where Vi is the number of states, and Ei is the number of arcs, in the ith
30 // FST.
31 template <class Arc>
32 void Union(MutableFst<Arc> *fst1, const Fst<Arc> &fst2) {
33  using Label = typename Arc::Label;
34  using StateId = typename Arc::StateId;
35  using Weight = typename Arc::Weight;
36  // Checks for symbol table compatibility.
37  if (!CompatSymbols(fst1->InputSymbols(), fst2.InputSymbols()) ||
38  !CompatSymbols(fst1->OutputSymbols(), fst2.OutputSymbols())) {
39  FSTERROR() << "Union: Input/output symbol tables of 1st argument "
40  << "do not match input/output symbol tables of 2nd argument";
41  fst1->SetProperties(kError, kError);
42  return;
43  }
44  const auto numstates1 = fst1->NumStates();
45  const bool initial_acyclic1 = fst1->Properties(kInitialAcyclic, true);
46  const auto props1 = fst1->Properties(kFstProperties, false);
47  const auto props2 = fst2.Properties(kFstProperties, false);
48  const auto start2 = fst2.Start();
49  if (start2 == kNoStateId) {
50  if (props2 & kError) fst1->SetProperties(kError, kError);
51  return;
52  }
53  if (fst2.Properties(kExpanded, false)) {
54  fst1->ReserveStates(numstates1 + CountStates(fst2) +
55  (initial_acyclic1 ? 0 : 1));
56  }
57  for (StateIterator<Fst<Arc>> siter(fst2); !siter.Done(); siter.Next()) {
58  const auto s1 = fst1->AddState();
59  const auto s2 = siter.Value();
60  fst1->SetFinal(s1, fst2.Final(s2));
61  fst1->ReserveArcs(s1, fst2.NumArcs(s2));
62  for (ArcIterator<Fst<Arc>> aiter(fst2, s2); !aiter.Done(); aiter.Next()) {
63  auto arc = aiter.Value(); // Copy intended.
64  arc.nextstate += numstates1;
65  fst1->AddArc(s1, std::move(arc));
66  }
67  }
68  const auto start1 = fst1->Start();
69  if (start1 == kNoStateId) {
70  fst1->SetStart(start2);
71  fst1->SetProperties(props2, kCopyProperties);
72  return;
73  }
74  if (initial_acyclic1) {
75  fst1->AddArc(start1, Arc(0, 0, Weight::One(), start2 + numstates1));
76  } else {
77  const auto nstart1 = fst1->AddState();
78  fst1->SetStart(nstart1);
79  fst1->AddArc(nstart1, Arc(0, 0, Weight::One(), start1));
80  fst1->AddArc(nstart1, Arc(0, 0, Weight::One(), start2 + numstates1));
81  }
82  fst1->SetProperties(UnionProperties(props1, props2), kFstProperties);
83 }
84
85 // Computes the union of two FSTs, modifying the RationalFst argument.
86 template <class Arc>
87 void Union(RationalFst<Arc> *fst1, const Fst<Arc> &fst2) {
88  fst1->GetMutableImpl()->AddUnion(fst2);
89 }
90
92
93 // Computes the union (sum) of two FSTs. This version is a delayed FST. If A
94 // transduces string x to y with weight a and B transduces string w to v with
95 // weight b, then their union transduces x to y with weight a and w to v with
96 // weight b.
97 //
98 // Complexity:
99 //
100 // Time: O(v_1 + e_1 + v_2 + e_2)
101 // Space: O(v_1 + v_2)
102 //
103 // where vi is the number of states visited, and ei is the number of arcs
104 // visited, in the ith FST. Constant time and space to visit an input state or
105 // arc is assumed and exclusive of caching.
106 template <class A>
107 class UnionFst : public RationalFst<A> {
108  public:
109  using Arc = A;
110  using StateId = typename Arc::StateId;
111  using Weight = typename Arc::Weight;
112
113  UnionFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2) {
114  GetMutableImpl()->InitUnion(fst1, fst2);
115  }
116
117  UnionFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2,
118  const UnionFstOptions &opts)
119  : RationalFst<Arc>(opts) {
120  GetMutableImpl()->InitUnion(fst1, fst2);
121  }
122
123  // See Fst<>::Copy() for doc.
124  UnionFst(const UnionFst<Arc> &fst, bool safe = false)
125  : RationalFst<Arc>(fst, safe) {}
126
127  // Gets a copy of this UnionFst. See Fst<>::Copy() for further doc.
128  UnionFst<Arc> *Copy(bool safe = false) const override {
129  return new UnionFst<Arc>(*this, safe);
130  }
131
132  private:
135 };
136
137 // Specialization for UnionFst.
138 template <class Arc>
139 class StateIterator<UnionFst<Arc>> : public StateIterator<RationalFst<Arc>> {
140  public:
141  explicit StateIterator(const UnionFst<Arc> &fst)
142  : StateIterator<RationalFst<Arc>>(fst) {}
143 };
144
145 // Specialization for UnionFst.
146 template <class Arc>
147 class ArcIterator<UnionFst<Arc>> : public ArcIterator<RationalFst<Arc>> {
148  public:
149  using StateId = typename Arc::StateId;
150
152  : ArcIterator<RationalFst<Arc>>(fst, s) {}
153 };
154
156
157 } // namespace fst
158
159 #endif // FST_UNION_H_
uint64 UnionProperties(uint64 inprops1, uint64 inprops2, bool delayed=false)
Definition: properties.cc:370
constexpr uint64 kInitialAcyclic
Definition: properties.h:97
StateIterator(const UnionFst< Arc > &fst)
Definition: union.h:141
virtual size_t NumArcs(StateId) const =0
virtual void AddArc(StateId, const Arc &arc)=0
const SymbolTable * InputSymbols() const override=0
virtual Weight Final(StateId) const =0
virtual void SetStart(StateId)=0
typename ReplaceFst< Arc >::Arc Arc
Definition: fst.h:374
UnionFst(const UnionFst< Arc > &fst, bool safe=false)
Definition: union.h:124
constexpr uint64 kFstProperties
Definition: properties.h:301
CacheOptions RationalFstOptions
Definition: rational.h:21
constexpr uint64 kCopyProperties
Definition: properties.h:138
constexpr int kNoStateId
Definition: fst.h:180
constexpr uint64 kExpanded
Definition: properties.h:27
virtual uint64 Properties(uint64 mask, bool test) const =0
#define FSTERROR()
Definition: util.h:35
UnionFst(const Fst< Arc > &fst1, const Fst< Arc > &fst2)
Definition: union.h:113
const SymbolTable * OutputSymbols() const override=0
virtual void ReserveArcs(StateId s, size_t n)
Definition: mutable-fst.h:79
virtual void SetFinal(StateId, Weight)=0
typename Arc::StateId StateId
Definition: rational.h:254
void Union(RationalFst< Arc > *fst1, const Fst< Arc > &fst2)
Definition: union.h:87
UnionFst< Arc > * Copy(bool safe=false) const override
Definition: union.h:128
typename Arc::StateId StateId
Definition: rational.h:299
virtual StateId Start() const =0
virtual void ReserveStates(StateId n)
Definition: mutable-fst.h:76
typename ReplaceFst< Arc >::Arc Arc
Definition: cache.h:1189
virtual const SymbolTable * InputSymbols() const =0
Arc::StateId CountStates(const Fst< Arc > &fst)
Definition: expanded-fst.h:154
constexpr uint64 kError
Definition: properties.h:33
virtual StateId AddState()=0
ArcIterator(const UnionFst< Arc > &fst, StateId s)
Definition: union.h:151
typename Arc::Weight Weight
Definition: union.h:111
UnionFst(const Fst< Arc > &fst1, const Fst< Arc > &fst2, const UnionFstOptions &opts)
Definition: union.h:117
bool CompatSymbols(const SymbolTable *syms1, const SymbolTable *syms2, bool warning=true)
internal::RationalFstImpl< A > * GetMutableImpl() const
Definition: fst.h:947
virtual StateId NumStates() const =0
const internal::RationalFstImpl< A > * GetImpl() const
Definition: fst.h:945
virtual void SetProperties(uint64 props, uint64 mask)=0
virtual const SymbolTable * OutputSymbols() const =0