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