FST  openfst-1.7.1
OpenFst Library
closure.h
Go to the documentation of this file.
1 // See www.openfst.org for extensive documentation on this weighted
2 // finite-state transducer library.
3 //
4 // Functions and classes to compute the concatenative closure of an FST.
5 
6 #ifndef FST_CLOSURE_H_
7 #define FST_CLOSURE_H_
8 
9 #include <algorithm>
10 #include <vector>
11 
12 #include <fst/mutable-fst.h>
13 #include <fst/rational.h>
14 
15 
16 namespace fst {
17 
18 // Computes the concatenative closure. This version modifies its
19 // MutableFst input. If an FST transduces string x to y with weight a,
20 // then its closure transduces x to y with weight a, xx to yy with
21 // weight Times(a, a), xxx to yyy with with Times(Times(a, a), a),
22 // etc. If closure_type == CLOSURE_STAR, then the empty string is
23 // transduced to itself with weight Weight::One() as well.
24 //
25 // Complexity:
26 //
27 // Time: O(V)
28 // Space: O(V)
29 //
30 // where V is the number of states.
31 template <class Arc>
32 void Closure(MutableFst<Arc> *fst, ClosureType closure_type) {
33  using Label = typename Arc::Label;
34  using StateId = typename Arc::StateId;
35  using Weight = typename Arc::Weight;
36  const auto props = fst->Properties(kFstProperties, false);
37  const auto start = fst->Start();
38  for (StateIterator<MutableFst<Arc>> siter(*fst); !siter.Done();
39  siter.Next()) {
40  const auto s = siter.Value();
41  const auto weight = fst->Final(s);
42  if (weight != Weight::Zero()) fst->AddArc(s, Arc(0, 0, weight, start));
43  }
44  if (closure_type == CLOSURE_STAR) {
45  fst->ReserveStates(fst->NumStates() + 1);
46  const auto nstart = fst->AddState();
47  fst->SetStart(nstart);
48  fst->SetFinal(nstart, Weight::One());
49  if (start != kNoLabel) fst->AddArc(nstart, Arc(0, 0, Weight::One(), start));
50  }
51  fst->SetProperties(ClosureProperties(props, closure_type == CLOSURE_STAR),
53 }
54 
55 // Computes the concatenative closure. This version modifies its
56 // RationalFst input.
57 template <class Arc>
58 void Closure(RationalFst<Arc> *fst, ClosureType closure_type) {
59  fst->GetMutableImpl()->AddClosure(closure_type);
60 }
61 
64 
67  : RationalFstOptions(opts), type(type) {}
68 
69  explicit ClosureFstOptions(ClosureType type = CLOSURE_STAR) : type(type) {}
70 };
71 
72 // Computes the concatenative closure. This version is a delayed FST. If an FST
73 // transduces string x to y with weight a, then its closure transduces x to y
74 // with weight a, xx to yy with weight Times(a, a), xxx to yyy with weight
75 // Times(Times(a, a), a), etc. If closure_type == CLOSURE_STAR, then the empty
76 // string is transduced to itself with weight Weight::One() as well.
77 //
78 // Complexity:
79 //
80 // Time: O(v)
81 // Space: O(v)
82 //
83 // where v is the number of states visited. Constant time and space to visit an
84 // input state or arc is assumed and exclusive of caching.
85 template <class A>
86 class ClosureFst : public RationalFst<A> {
87  public:
88  using Arc = A;
89 
90  ClosureFst(const Fst<Arc> &fst, ClosureType closure_type) {
91  GetMutableImpl()->InitClosure(fst, closure_type);
92  }
93 
95  : RationalFst<A>(opts) {
96  GetMutableImpl()->InitClosure(fst, opts.type);
97  }
98 
99  // See Fst<>::Copy() for doc.
100  ClosureFst(const ClosureFst<Arc> &fst, bool safe = false)
101  : RationalFst<A>(fst, safe) {}
102 
103  // Gets a copy of this ClosureFst. See Fst<>::Copy() for further doc.
104  ClosureFst<A> *Copy(bool safe = false) const override {
105  return new ClosureFst<A>(*this, safe);
106  }
107 
108  private:
110  using ImplToFst<internal::RationalFstImpl<Arc>>::GetMutableImpl;
111 };
112 
113 // Specialization for ClosureFst.
114 template <class Arc>
115 class StateIterator<ClosureFst<Arc>> : public StateIterator<RationalFst<Arc>> {
116  public:
118  : StateIterator<RationalFst<Arc>>(fst) {}
119 };
120 
121 // Specialization for ClosureFst.
122 template <class Arc>
123 class ArcIterator<ClosureFst<Arc>> : public ArcIterator<RationalFst<Arc>> {
124  public:
125  using StateId = typename Arc::StateId;
126 
128  : ArcIterator<RationalFst<Arc>>(fst, s) {}
129 };
130 
131 // Useful alias when using StdArc.
133 
134 } // namespace fst
135 
136 #endif // FST_CLOSURE_H_
ClosureFst(const Fst< Arc > &fst, const ClosureFstOptions &opts)
Definition: closure.h:94
ArcIterator(const ClosureFst< Arc > &fst, StateId s)
Definition: closure.h:127
constexpr int kNoLabel
Definition: fst.h:179
ClosureFst(const ClosureFst< Arc > &fst, bool safe=false)
Definition: closure.h:100
void Closure(MutableFst< Arc > *fst, ClosureType closure_type)
Definition: closure.h:32
uint64 ClosureProperties(uint64 inprops, bool star, bool delayed=false)
Definition: properties.cc:21
virtual void AddArc(StateId, const Arc &arc)=0
virtual Weight Final(StateId) const =0
virtual void SetStart(StateId)=0
ClosureType type
Definition: closure.h:63
typename ReplaceFst< Arc >::Arc Arc
Definition: fst.h:374
typename Arc::StateId StateId
Definition: closure.h:125
constexpr uint64 kFstProperties
Definition: properties.h:301
virtual uint64 Properties(uint64 mask, bool test) const =0
virtual void SetFinal(StateId, Weight)=0
virtual StateId Start() const =0
ClosureFst< A > * Copy(bool safe=false) const override
Definition: closure.h:104
virtual void ReserveStates(StateId n)
Definition: mutable-fst.h:76
StateIterator(const ClosureFst< Arc > &fst)
Definition: closure.h:117
ClosureFst(const Fst< Arc > &fst, ClosureType closure_type)
Definition: closure.h:90
typename ReplaceFst< Arc >::Arc Arc
Definition: cache.h:1189
ClosureType
Definition: rational.h:24
virtual StateId AddState()=0
ClosureFstOptions(const RationalFstOptions &opts, ClosureType type=CLOSURE_STAR)
Definition: closure.h:65
internal::RationalFstImpl< A > * GetMutableImpl() const
Definition: fst.h:947
virtual StateId NumStates() const =0
ClosureFstOptions(ClosureType type=CLOSURE_STAR)
Definition: closure.h:69
virtual void SetProperties(uint64 props, uint64 mask)=0