1// closure.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// Copyright 2005-2010 Google, Inc.
16// Author: riley@google.com (Michael Riley)
17//
18// \file
19// Functions and classes to compute the concatenative closure of an Fst.
20
21#ifndef FST_LIB_CLOSURE_H__
22#define FST_LIB_CLOSURE_H__
23
24#include <vector>
25using std::vector;
26#include <algorithm>
27
28#include <fst/mutable-fst.h>
29#include <fst/rational.h>
30
31
32namespace fst {
33
34// Computes the concatenative closure. This version modifies its
35// MutableFst input. If FST transduces string x to y with weight a,
36// then the closure transduces x to y with weight a, xx to yy with
37// weight Times(a, a), xxx to yyy with with Times(Times(a, a), a),
38// etc. If closure_type == CLOSURE_STAR, then the empty string is
39// transduced to itself with weight Weight::One() as well.
40//
41// Complexity:
42// - Time: O(V)
43// - Space: O(V)
44// where V = # of states.
45template<class Arc>
46void Closure(MutableFst<Arc> *fst, ClosureType closure_type) {
47  typedef typename Arc::StateId StateId;
48  typedef typename Arc::Label Label;
49  typedef typename Arc::Weight Weight;
50
51  uint64 props = fst->Properties(kFstProperties, false);
52  StateId start = fst->Start();
53  for (StateIterator< MutableFst<Arc> > siter(*fst);
54       !siter.Done();
55       siter.Next()) {
56    StateId s = siter.Value();
57    Weight final = fst->Final(s);
58    if (final != Weight::Zero())
59      fst->AddArc(s, Arc(0, 0, final, start));
60  }
61  if (closure_type == CLOSURE_STAR) {
62    fst->ReserveStates(fst->NumStates() + 1);
63    StateId nstart = fst->AddState();
64    fst->SetStart(nstart);
65    fst->SetFinal(nstart, Weight::One());
66    if (start != kNoLabel)
67      fst->AddArc(nstart, Arc(0, 0, Weight::One(), start));
68  }
69  fst->SetProperties(ClosureProperties(props, closure_type == CLOSURE_STAR),
70                     kFstProperties);
71}
72
73// Computes the concatenative closure. This version modifies its
74// RationalFst input.
75template<class Arc>
76void Closure(RationalFst<Arc> *fst, ClosureType closure_type) {
77  fst->GetImpl()->AddClosure(closure_type);
78}
79
80
81struct ClosureFstOptions : RationalFstOptions {
82  ClosureType type;
83
84  ClosureFstOptions(const RationalFstOptions &opts, ClosureType t)
85      : RationalFstOptions(opts), type(t) {}
86  explicit ClosureFstOptions(ClosureType t) : type(t) {}
87  ClosureFstOptions() : type(CLOSURE_STAR) {}
88};
89
90
91// Computes the concatenative closure. This version is a delayed
92// Fst. If FST transduces string x to y with weight a, then the
93// closure transduces x to y with weight a, xx to yy with weight
94// Times(a, a), xxx to yyy with weight Times(Times(a, a), a), etc. If
95// closure_type == CLOSURE_STAR, then The empty string is transduced
96// to itself with weight Weight::One() as well.
97//
98// Complexity:
99// - Time: O(v)
100// - Space: O(v)
101// where v = # of states visited. Constant time and space to visit an
102// input state or arc is assumed and exclusive of caching.
103template <class A>
104class ClosureFst : public RationalFst<A> {
105 public:
106  using ImplToFst< RationalFstImpl<A> >::GetImpl;
107
108  typedef A Arc;
109
110  ClosureFst(const Fst<A> &fst, ClosureType closure_type) {
111    GetImpl()->InitClosure(fst, closure_type);
112  }
113
114  ClosureFst(const Fst<A> &fst, const ClosureFstOptions &opts)
115      : RationalFst<A>(opts) {
116    GetImpl()->InitClosure(fst, opts.type);
117  }
118
119  // See Fst<>::Copy() for doc.
120  ClosureFst(const ClosureFst<A> &fst, bool safe = false)
121      : RationalFst<A>(fst, safe) {}
122
123  // Get a copy of this ClosureFst. See Fst<>::Copy() for further doc.
124  virtual ClosureFst<A> *Copy(bool safe = false) const {
125    return new ClosureFst<A>(*this, safe);
126  }
127};
128
129
130// Specialization for ClosureFst.
131template <class A>
132class StateIterator< ClosureFst<A> > : public StateIterator< RationalFst<A> > {
133 public:
134  explicit StateIterator(const ClosureFst<A> &fst)
135      : StateIterator< RationalFst<A> >(fst) {}
136};
137
138
139// Specialization for ClosureFst.
140template <class A>
141class ArcIterator< ClosureFst<A> > : public ArcIterator< RationalFst<A> > {
142 public:
143  typedef typename A::StateId StateId;
144
145  ArcIterator(const ClosureFst<A> &fst, StateId s)
146      : ArcIterator< RationalFst<A> >(fst, s) {}
147};
148
149
150// Useful alias when using StdArc.
151typedef ClosureFst<StdArc> StdClosureFst;
152
153}  // namespace fst
154
155#endif  // FST_LIB_CLOSURE_H__
156