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
25namespace 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.
36template <class Arc>
37void 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.
86template<class Arc>
87void Union(RationalFst<Arc> *fst1, const Fst<Arc> &fst2) {
88  fst1->Impl()->AddUnion(fst2);
89}
90
91
92typedef 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.
106template <class A>
107class 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
115  UnionFst(const Fst<A> &fst1, const Fst<A> &fst2) {
116    Impl()->InitUnion(fst1, fst2);
117  }
118
119  UnionFst(const Fst<A> &fst1, const Fst<A> &fst2, const UnionFstOptions &opts)
120      : RationalFst<A>(opts) {
121    Impl()->InitUnion(fst1, fst2);
122  }
123
124  UnionFst(const UnionFst<A> &fst) : RationalFst<A>(fst) {}
125
126  virtual UnionFst<A> *Copy() const { return new UnionFst<A>(*this); }
127};
128
129
130// Specialization for UnionFst.
131template <class A>
132class StateIterator< UnionFst<A> > : public StateIterator< RationalFst<A> > {
133 public:
134  explicit StateIterator(const UnionFst<A> &fst)
135      : StateIterator< RationalFst<A> >(fst) {}
136};
137
138
139// Specialization for UnionFst.
140template <class A>
141class ArcIterator< UnionFst<A> > : public ArcIterator< RationalFst<A> > {
142 public:
143  typedef typename A::StateId StateId;
144
145  ArcIterator(const UnionFst<A> &fst, StateId s)
146      : ArcIterator< RationalFst<A> >(fst, s) {}
147};
148
149
150// Useful alias when using StdArc.
151typedef UnionFst<StdArc> StdUnionFst;
152
153}  // namespace fst
154
155#endif  // FST_LIB_UNION_H__
156