concat.h revision 4a68b3365c8c50aa93505e99ead2565ab73dcdb0 
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
27namespace 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.
38template<class Arc>
39void 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.
84template<class Arc>
85void Concat(RationalFst<Arc> *fst1, const Fst<Arc> &fst2) {
86  fst1->Impl()->AddConcat(fst2);
87}
88
89
90typedef 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.
104template <class A>
105class 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
113  ConcatFst(const Fst<A> &fst1, const Fst<A> &fst2) {
114    Impl()->InitConcat(fst1, fst2);
115  }
116
117  ConcatFst(const Fst<A> &fst1, const Fst<A> &fst2,
118            const ConcatFstOptions &opts) : RationalFst<A>(opts) {
119    Impl()->InitConcat(fst1, fst2);
120  }
121
122  ConcatFst(const ConcatFst<A> &fst) : RationalFst<A>(fst) {}
123
124  virtual ConcatFst<A> *Copy() const { return new ConcatFst<A>(*this); }
125};
126
127
128// Specialization for ConcatFst.
129template <class A>
130class StateIterator< ConcatFst<A> > : public StateIterator< RationalFst<A> > {
131 public:
132  explicit StateIterator(const ConcatFst<A> &fst)
133      : StateIterator< RationalFst<A> >(fst) {}
134};
135
136
137// Specialization for ConcatFst.
138template <class A>
139class ArcIterator< ConcatFst<A> > : public ArcIterator< RationalFst<A> > {
140 public:
141  typedef typename A::StateId StateId;
142
143  ArcIterator(const ConcatFst<A> &fst, StateId s)
144      : ArcIterator< RationalFst<A> >(fst, s) {}
145};
146
147
148// Useful alias when using StdArc.
149typedef ConcatFst<StdArc> StdConcatFst;
150
151}  // namespace fst
152
153#endif  // FST_LIB_CONCAT_H__
154