FST  openfst-1.7.2
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 Weight = typename Arc::Weight;
34  // Checks for symbol table compatibility.
35  if (!CompatSymbols(fst1->InputSymbols(), fst2.InputSymbols()) ||
36  !CompatSymbols(fst1->OutputSymbols(), fst2.OutputSymbols())) {
37  FSTERROR() << "Union: Input/output symbol tables of 1st argument "
38  << "do not match input/output symbol tables of 2nd argument";
39  fst1->SetProperties(kError, kError);
40  return;
41  }
42  const auto numstates1 = fst1->NumStates();
43  const bool initial_acyclic1 = fst1->Properties(kInitialAcyclic, true);
44  const auto props1 = fst1->Properties(kFstProperties, false);
45  const auto props2 = fst2.Properties(kFstProperties, false);
46  const auto start2 = fst2.Start();
47  if (start2 == kNoStateId) {
48  if (props2 & kError) fst1->SetProperties(kError, kError);
49  return;
50  }
51  if (fst2.Properties(kExpanded, false)) {
52  fst1->ReserveStates(numstates1 + CountStates(fst2) +
53  (initial_acyclic1 ? 0 : 1));
54  }
55  for (StateIterator<Fst<Arc>> siter(fst2); !siter.Done(); siter.Next()) {
56  const auto s1 = fst1->AddState();
57  const auto s2 = siter.Value();
58  fst1->SetFinal(s1, fst2.Final(s2));
59  fst1->ReserveArcs(s1, fst2.NumArcs(s2));
60  for (ArcIterator<Fst<Arc>> aiter(fst2, s2); !aiter.Done(); aiter.Next()) {
61  auto arc = aiter.Value(); // Copy intended.
62  arc.nextstate += numstates1;
63  fst1->AddArc(s1, std::move(arc));
64  }
65  }
66  const auto start1 = fst1->Start();
67  if (start1 == kNoStateId) {
68  fst1->SetStart(start2);
69  fst1->SetProperties(props2, kCopyProperties);
70  return;
71  }
72  if (initial_acyclic1) {
73  fst1->AddArc(start1, Arc(0, 0, Weight::One(), start2 + numstates1));
74  } else {
75  const auto nstart1 = fst1->AddState();
76  fst1->SetStart(nstart1);
77  fst1->AddArc(nstart1, Arc(0, 0, Weight::One(), start1));
78  fst1->AddArc(nstart1, Arc(0, 0, Weight::One(), start2 + numstates1));
79  }
80  fst1->SetProperties(UnionProperties(props1, props2), kFstProperties);
81 }
82 
83 // Computes the union of two FSTs, modifying the RationalFst argument.
84 template <class Arc>
85 void Union(RationalFst<Arc> *fst1, const Fst<Arc> &fst2) {
86  fst1->GetMutableImpl()->AddUnion(fst2);
87 }
88 
90 
91 // Computes the union (sum) of two FSTs. This version is a delayed FST. If A
92 // transduces string x to y with weight a and B transduces string w to v with
93 // weight b, then their union transduces x to y with weight a and w to v with
94 // weight b.
95 //
96 // Complexity:
97 //
98 // Time: O(v_1 + e_1 + v_2 + e_2)
99 // Space: O(v_1 + v_2)
100 //
101 // where vi is the number of states visited, and ei is the number of arcs
102 // visited, in the ith FST. Constant time and space to visit an input state or
103 // arc is assumed and exclusive of caching.
104 template <class A>
105 class UnionFst : public RationalFst<A> {
106  public:
107  using Arc = A;
108  using StateId = typename Arc::StateId;
109  using Weight = typename Arc::Weight;
110 
111  UnionFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2) {
112  GetMutableImpl()->InitUnion(fst1, fst2);
113  }
114 
115  UnionFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2,
116  const UnionFstOptions &opts)
117  : RationalFst<Arc>(opts) {
118  GetMutableImpl()->InitUnion(fst1, fst2);
119  }
120 
121  // See Fst<>::Copy() for doc.
122  UnionFst(const UnionFst<Arc> &fst, bool safe = false)
123  : RationalFst<Arc>(fst, safe) {}
124 
125  // Gets a copy of this UnionFst. See Fst<>::Copy() for further doc.
126  UnionFst<Arc> *Copy(bool safe = false) const override {
127  return new UnionFst<Arc>(*this, safe);
128  }
129 
130  private:
133 };
134 
135 // Specialization for UnionFst.
136 template <class Arc>
137 class StateIterator<UnionFst<Arc>> : public StateIterator<RationalFst<Arc>> {
138  public:
139  explicit StateIterator(const UnionFst<Arc> &fst)
140  : StateIterator<RationalFst<Arc>>(fst) {}
141 };
142 
143 // Specialization for UnionFst.
144 template <class Arc>
145 class ArcIterator<UnionFst<Arc>> : public ArcIterator<RationalFst<Arc>> {
146  public:
147  using StateId = typename Arc::StateId;
148 
150  : ArcIterator<RationalFst<Arc>>(fst, s) {}
151 };
152 
154 
155 } // namespace fst
156 
157 #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:139
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:122
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:111
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:85
UnionFst< Arc > * Copy(bool safe=false) const override
Definition: union.h:126
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:1194
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:149
typename Arc::Weight Weight
Definition: union.h:109
UnionFst(const Fst< Arc > &fst1, const Fst< Arc > &fst2, const UnionFstOptions &opts)
Definition: union.h:115
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