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