FST  openfst-1.7.1
OpenFst Library
concat.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 concatenation of two FSTs.
5 
6 #ifndef FST_CONCAT_H_
7 #define FST_CONCAT_H_
8 
9 #include <algorithm>
10 #include <vector>
11 
12 #include <fst/mutable-fst.h>
13 #include <fst/rational.h>
14 
15 
16 namespace fst {
17 
18 // Computes the concatenation (product) of two FSTs. If FST1 transduces string
19 // x to y with weight a and FST2 transduces string w to v with weight b, then
20 // their concatenation transduces string xw to yv with weight Times(a, b).
21 //
22 // This version modifies its MutableFst argument (in first position).
23 //
24 // Complexity:
25 //
26 // Time: O(V1 + V2 + E2)
27 // Space: O(V1 + V2 + E2)
28 //
29 // where Vi is the number of states, and Ei is the number of arcs, of the ith
30 // FST.
31 template <class Arc>
32 void Concat(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 that the symbol table are compatible.
37  if (!CompatSymbols(fst1->InputSymbols(), fst2.InputSymbols()) ||
38  !CompatSymbols(fst1->OutputSymbols(), fst2.OutputSymbols())) {
39  FSTERROR() << "Concat: Input/output symbol tables of 1st argument "
40  << "does not match input/output symbol tables of 2nd argument";
41  fst1->SetProperties(kError, kError);
42  return;
43  }
44  const auto props1 = fst1->Properties(kFstProperties, false);
45  const auto props2 = fst2.Properties(kFstProperties, false);
46  const auto start1 = fst1->Start();
47  if (start1 == kNoStateId) {
48  if (props2 & kError) fst1->SetProperties(kError, kError);
49  return;
50  }
51  const auto numstates1 = fst1->NumStates();
52  if (fst2.Properties(kExpanded, false)) {
53  fst1->ReserveStates(numstates1 + CountStates(fst2));
54  }
55  for (StateIterator<Fst<Arc>> siter2(fst2); !siter2.Done(); siter2.Next()) {
56  const auto s1 = fst1->AddState();
57  const auto s2 = siter2.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();
62  arc.nextstate += numstates1;
63  fst1->AddArc(s1, arc);
64  }
65  }
66  const auto start2 = fst2.Start();
67  for (StateId s1 = 0; s1 < numstates1; ++s1) {
68  const auto weight = fst1->Final(s1);
69  if (weight != Weight::Zero()) {
70  fst1->SetFinal(s1, Weight::Zero());
71  if (start2 != kNoStateId) {
72  fst1->AddArc(s1, Arc(0, 0, weight, start2 + numstates1));
73  }
74  }
75  }
76  if (start2 != kNoStateId) {
77  fst1->SetProperties(ConcatProperties(props1, props2), kFstProperties);
78  }
79 }
80 
81 // Computes the concatentation of two FSTs. This version modifies its
82 // MutableFst argument (in second position).
83 //
84 // Complexity:
85 //
86 // Time: O(V1 + E1)
87 // Space: O(V1 + E1)
88 //
89 // where Vi is the number of states, and Ei is the number of arcs, of the ith
90 // FST.
91 template <class Arc>
92 void Concat(const Fst<Arc> &fst1, MutableFst<Arc> *fst2) {
93  using Label = typename Arc::Label;
94  using StateId = typename Arc::StateId;
95  using Weight = typename Arc::Weight;
96  // Checks that the symbol table are compatible.
97  if (!CompatSymbols(fst1.InputSymbols(), fst2->InputSymbols()) ||
98  !CompatSymbols(fst1.OutputSymbols(), fst2->OutputSymbols())) {
99  FSTERROR() << "Concat: Input/output symbol tables of 1st argument "
100  << "does not match input/output symbol tables of 2nd argument";
101  fst2->SetProperties(kError, kError);
102  return;
103  }
104  const auto props1 = fst1.Properties(kFstProperties, false);
105  const auto props2 = fst2->Properties(kFstProperties, false);
106  const auto start2 = fst2->Start();
107  if (start2 == kNoStateId) {
108  if (props1 & kError) fst2->SetProperties(kError, kError);
109  return;
110  }
111  const auto numstates2 = fst2->NumStates();
112  if (fst1.Properties(kExpanded, false)) {
113  fst2->ReserveStates(numstates2 + CountStates(fst1));
114  }
115  for (StateIterator<Fst<Arc>> siter(fst1); !siter.Done(); siter.Next()) {
116  const auto s1 = siter.Value();
117  const auto s2 = fst2->AddState();
118  const auto weight = fst1.Final(s1);
119  if (weight != Weight::Zero()) {
120  fst2->ReserveArcs(s2, fst1.NumArcs(s1) + 1);
121  fst2->AddArc(s2, Arc(0, 0, weight, start2));
122  } else {
123  fst2->ReserveArcs(s2, fst1.NumArcs(s1));
124  }
125  for (ArcIterator<Fst<Arc>> aiter(fst1, s1); !aiter.Done(); aiter.Next()) {
126  auto arc = aiter.Value();
127  arc.nextstate += numstates2;
128  fst2->AddArc(s2, arc);
129  }
130  }
131  const auto start1 = fst1.Start();
132  if (start1 != kNoStateId) {
133  fst2->SetStart(start1 + numstates2);
134  fst2->SetProperties(ConcatProperties(props1, props2), kFstProperties);
135  } else {
136  fst2->SetStart(fst2->AddState());
137  }
138 }
139 
140 // Computes the concatentation of two FSTs. This version modifies its
141 // RationalFst input (in first position).
142 template <class Arc>
143 void Concat(RationalFst<Arc> *fst1, const Fst<Arc> &fst2) {
144  fst1->GetMutableImpl()->AddConcat(fst2, true);
145 }
146 
147 // Computes the concatentation of two FSTs. This version modifies its
148 // RationalFst input (in second position).
149 template <class Arc>
150 void Concat(const Fst<Arc> &fst1, RationalFst<Arc> *fst2) {
151  fst2->GetMutableImpl()->AddConcat(fst1, false);
152 }
153 
155 
156 // Computes the concatenation (product) of two FSTs; this version is a delayed
157 // FST. If FST1 transduces string x to y with weight a and FST2 transduces
158 // string w to v with weight b, then their concatenation transduces string xw
159 // to yv with Times(a, b).
160 //
161 // Complexity:
162 //
163 // Time: O(v1 + e1 + v2 + e2),
164 // Space: O(v1 + v2)
165 //
166 // where vi is the number of states visited, and ei is the number of arcs
167 // visited, of the ith FST. Constant time and space to visit an input state or
168 // arc is assumed and exclusive of caching.
169 template <class A>
170 class ConcatFst : public RationalFst<A> {
171  public:
172  using Arc = A;
173  using StateId = typename Arc::StateId;
174  using Weight = typename Arc::Weight;
175 
176  ConcatFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2) {
177  GetMutableImpl()->InitConcat(fst1, fst2);
178  }
179 
180  ConcatFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2,
181  const ConcatFstOptions &opts)
182  : RationalFst<Arc>(opts) {
183  GetMutableImpl()->InitConcat(fst1, fst2);
184  }
185 
186  // See Fst<>::Copy() for doc.
187  ConcatFst(const ConcatFst<Arc> &fst, bool safe = false)
188  : RationalFst<Arc>(fst, safe) {}
189 
190  // Get a copy of this ConcatFst. See Fst<>::Copy() for further doc.
191  ConcatFst<Arc> *Copy(bool safe = false) const override {
192  return new ConcatFst<Arc>(*this, safe);
193  }
194 
195  private:
198 };
199 
200 // Specialization for ConcatFst.
201 template <class Arc>
202 class StateIterator<ConcatFst<Arc>> : public StateIterator<RationalFst<Arc>> {
203  public:
205  : StateIterator<RationalFst<Arc>>(fst) {}
206 };
207 
208 // Specialization for ConcatFst.
209 template <class Arc>
210 class ArcIterator<ConcatFst<Arc>> : public ArcIterator<RationalFst<Arc>> {
211  public:
212  using StateId = typename Arc::StateId;
213 
215  : ArcIterator<RationalFst<Arc>>(fst, s) {}
216 };
217 
218 // Useful alias when using StdArc.
220 
221 } // namespace fst
222 
223 #endif // FST_CONCAT_H_
virtual size_t NumArcs(StateId) const =0
virtual void AddArc(StateId, const Arc &arc)=0
typename Arc::StateId StateId
Definition: concat.h:173
const SymbolTable * InputSymbols() const override=0
ConcatFst(const Fst< Arc > &fst1, const Fst< Arc > &fst2, const ConcatFstOptions &opts)
Definition: concat.h:180
virtual Weight Final(StateId) const =0
virtual void SetStart(StateId)=0
typename ReplaceFst< Arc >::Arc Arc
Definition: fst.h:374
typename Arc::Weight Weight
Definition: concat.h:174
constexpr uint64 kFstProperties
Definition: properties.h:301
CacheOptions RationalFstOptions
Definition: rational.h:21
constexpr int kNoStateId
Definition: fst.h:180
constexpr uint64 kExpanded
Definition: properties.h:27
virtual uint64 Properties(uint64 mask, bool test) const =0
ArcIterator(const ConcatFst< Arc > &fst, StateId s)
Definition: concat.h:214
ConcatFst< Arc > * Copy(bool safe=false) const override
Definition: concat.h:191
#define FSTERROR()
Definition: util.h:35
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: concat.h:212
virtual StateId Start() const =0
ConcatFst(const Fst< Arc > &fst1, const Fst< Arc > &fst2)
Definition: concat.h:176
virtual void ReserveStates(StateId n)
Definition: mutable-fst.h:76
void Concat(MutableFst< Arc > *fst1, const Fst< Arc > &fst2)
Definition: concat.h:32
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
uint64 ConcatProperties(uint64 inprops1, uint64 inprops2, bool delayed=false)
Definition: properties.cc:77
constexpr uint64 kError
Definition: properties.h:33
virtual StateId AddState()=0
StateIterator(const ConcatFst< Arc > &fst)
Definition: concat.h:204
bool CompatSymbols(const SymbolTable *syms1, const SymbolTable *syms2, bool warning=true)
ConcatFst(const ConcatFst< Arc > &fst, bool safe=false)
Definition: concat.h:187
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