1 // concat.h
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 //
16 // \file
17 // Functions and classes to compute the concat of two FSTs.
18
19 #ifndef FST_LIB_CONCAT_H__
20 #define FST_LIB_CONCAT_H__
21
22 #include <algorithm>
23
24 #include "fst/lib/mutable-fst.h"
25 #include "fst/lib/rational.h"
26
27 namespace fst {
28
29 // Computes the concatenation (product) of two FSTs; this version
30 // modifies its MutableFst argument. If FST1 transduces string x to y
31 // with weight a and FST2 transduces string w to v with weight b, then
32 // their concatenation transduces string xw to yv with Times(a, b).
33 //
34 // Complexity:
35 // - Time: O(V1 + V2 + E2)
36 // - Space: O(V1 + V2 + E2)
37 // where Vi = # of states and Ei = # of arcs of the ith FST.
38 template<class Arc>
Concat(MutableFst<Arc> * fst1,const Fst<Arc> & fst2)39 void Concat(MutableFst<Arc> *fst1, const Fst<Arc> &fst2) {
40 typedef typename Arc::StateId StateId;
41 typedef typename Arc::Label Label;
42 typedef typename Arc::Weight Weight;
43
44 StateId start1 = fst1->Start();
45 if (start1 == kNoStateId)
46 return;
47
48 uint64 props1 = fst1->Properties(kFstProperties, false);
49 uint64 props2 = fst2.Properties(kFstProperties, false);
50
51 StateId numstates1= fst1->NumStates();
52
53 for (StateIterator< Fst<Arc> > siter2(fst2);
54 !siter2.Done();
55 siter2.Next()) {
56 StateId s1 = fst1->AddState();
57 StateId s2 = siter2.Value();
58 fst1->SetFinal(s1, fst2.Final(s2));
59 for (ArcIterator< Fst<Arc> > aiter(fst2, s2);
60 !aiter.Done();
61 aiter.Next()) {
62 Arc arc = aiter.Value();
63 arc.nextstate += numstates1;
64 fst1->AddArc(s1, arc);
65 }
66 }
67
68 StateId start2 = fst2.Start();
69 for (StateId s1 = 0; s1 < numstates1; ++s1) {
70 Weight final = fst1->Final(s1);
71 if (final != Weight::Zero()) {
72 fst1->SetFinal(s1, Weight::Zero());
73 if (start2 != kNoStateId)
74 fst1->AddArc(s1, Arc(0, 0, final, start2 + numstates1));
75 }
76 }
77 if (start2 != kNoStateId)
78 fst1->SetProperties(ConcatProperties(props1, props2), kFstProperties);
79 }
80
81
82 // Computes the concatentation of two FSTs. This version modifies its
83 // RationalFst input.
84 template<class Arc>
Concat(RationalFst<Arc> * fst1,const Fst<Arc> & fst2)85 void Concat(RationalFst<Arc> *fst1, const Fst<Arc> &fst2) {
86 fst1->Impl()->AddConcat(fst2);
87 }
88
89
90 typedef RationalFstOptions ConcatFstOptions;
91
92
93 // Computes the concatenation (product) of two FSTs; this version is a
94 // delayed Fst. If FST1 transduces string x to y with weight a and FST2
95 // transduces string w to v with weight b, then their concatenation
96 // transduces string xw to yv with Times(a, b).
97 //
98 // Complexity:
99 // - Time: O(v1 + e1 + v2 + e2),
100 // - Space: O(v1 + v2)
101 // where vi = # of states visited and ei = # of arcs visited of the
102 // ith FST. Constant time and space to visit an input state or arc is
103 // assumed and exclusive of caching.
104 template <class A>
105 class ConcatFst : public RationalFst<A> {
106 public:
107 using RationalFst<A>::Impl;
108
109 typedef A Arc;
110 typedef typename A::Weight Weight;
111 typedef typename A::StateId StateId;
112
ConcatFst(const Fst<A> & fst1,const Fst<A> & fst2)113 ConcatFst(const Fst<A> &fst1, const Fst<A> &fst2) {
114 Impl()->InitConcat(fst1, fst2);
115 }
116
ConcatFst(const Fst<A> & fst1,const Fst<A> & fst2,const ConcatFstOptions & opts)117 ConcatFst(const Fst<A> &fst1, const Fst<A> &fst2,
118 const ConcatFstOptions &opts) : RationalFst<A>(opts) {
119 Impl()->InitConcat(fst1, fst2);
120 }
121
ConcatFst(const ConcatFst<A> & fst)122 ConcatFst(const ConcatFst<A> &fst) : RationalFst<A>(fst) {}
123
Copy()124 virtual ConcatFst<A> *Copy() const { return new ConcatFst<A>(*this); }
125 };
126
127
128 // Specialization for ConcatFst.
129 template <class A>
130 class StateIterator< ConcatFst<A> > : public StateIterator< RationalFst<A> > {
131 public:
StateIterator(const ConcatFst<A> & fst)132 explicit StateIterator(const ConcatFst<A> &fst)
133 : StateIterator< RationalFst<A> >(fst) {}
134 };
135
136
137 // Specialization for ConcatFst.
138 template <class A>
139 class ArcIterator< ConcatFst<A> > : public ArcIterator< RationalFst<A> > {
140 public:
141 typedef typename A::StateId StateId;
142
ArcIterator(const ConcatFst<A> & fst,StateId s)143 ArcIterator(const ConcatFst<A> &fst, StateId s)
144 : ArcIterator< RationalFst<A> >(fst, s) {}
145 };
146
147
148 // Useful alias when using StdArc.
149 typedef ConcatFst<StdArc> StdConcatFst;
150
151 } // namespace fst
152
153 #endif // FST_LIB_CONCAT_H__
154