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