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