FST  openfst-1.7.2 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 Weight = typename Arc::Weight;
34  const auto props = fst->Properties(kFstProperties, false);
35  const auto start = fst->Start();
36  for (StateIterator<MutableFst<Arc>> siter(*fst); !siter.Done();
37  siter.Next()) {
38  const auto s = siter.Value();
39  const auto weight = fst->Final(s);
40  if (weight != Weight::Zero()) fst->AddArc(s, Arc(0, 0, weight, start));
41  }
42  if (closure_type == CLOSURE_STAR) {
43  fst->ReserveStates(fst->NumStates() + 1);
44  const auto nstart = fst->AddState();
45  fst->SetStart(nstart);
46  fst->SetFinal(nstart, Weight::One());
47  if (start != kNoLabel) fst->AddArc(nstart, Arc(0, 0, Weight::One(), start));
48  }
49  fst->SetProperties(ClosureProperties(props, closure_type == CLOSURE_STAR),
51 }
52
53 // Computes the concatenative closure. This version modifies its
54 // RationalFst input.
55 template <class Arc>
56 void Closure(RationalFst<Arc> *fst, ClosureType closure_type) {
58 }
59
62
65  : RationalFstOptions(opts), type(type) {}
66
67  explicit ClosureFstOptions(ClosureType type = CLOSURE_STAR) : type(type) {}
68 };
69
70 // Computes the concatenative closure. This version is a delayed FST. If an FST
71 // transduces string x to y with weight a, then its closure transduces x to y
72 // with weight a, xx to yy with weight Times(a, a), xxx to yyy with weight
73 // Times(Times(a, a), a), etc. If closure_type == CLOSURE_STAR, then the empty
74 // string is transduced to itself with weight Weight::One() as well.
75 //
76 // Complexity:
77 //
78 // Time: O(v)
79 // Space: O(v)
80 //
81 // where v is the number of states visited. Constant time and space to visit an
82 // input state or arc is assumed and exclusive of caching.
83 template <class A>
84 class ClosureFst : public RationalFst<A> {
85  public:
86  using Arc = A;
87
88  ClosureFst(const Fst<Arc> &fst, ClosureType closure_type) {
89  GetMutableImpl()->InitClosure(fst, closure_type);
90  }
91
93  : RationalFst<A>(opts) {
94  GetMutableImpl()->InitClosure(fst, opts.type);
95  }
96
97  // See Fst<>::Copy() for doc.
98  ClosureFst(const ClosureFst<Arc> &fst, bool safe = false)
99  : RationalFst<A>(fst, safe) {}
100
101  // Gets a copy of this ClosureFst. See Fst<>::Copy() for further doc.
102  ClosureFst<A> *Copy(bool safe = false) const override {
103  return new ClosureFst<A>(*this, safe);
104  }
105
106  private:
108  using ImplToFst<internal::RationalFstImpl<Arc>>::GetMutableImpl;
109 };
110
111 // Specialization for ClosureFst.
112 template <class Arc>
113 class StateIterator<ClosureFst<Arc>> : public StateIterator<RationalFst<Arc>> {
114  public:
116  : StateIterator<RationalFst<Arc>>(fst) {}
117 };
118
119 // Specialization for ClosureFst.
120 template <class Arc>
121 class ArcIterator<ClosureFst<Arc>> : public ArcIterator<RationalFst<Arc>> {
122  public:
123  using StateId = typename Arc::StateId;
124
126  : ArcIterator<RationalFst<Arc>>(fst, s) {}
127 };
128
129 // Useful alias when using StdArc.
131
132 } // namespace fst
133
134 #endif // FST_CLOSURE_H_
ClosureFst(const Fst< Arc > &fst, const ClosureFstOptions &opts)
Definition: closure.h:92
ArcIterator(const ClosureFst< Arc > &fst, StateId s)
Definition: closure.h:125
constexpr int kNoLabel
Definition: fst.h:179
ClosureFst(const ClosureFst< Arc > &fst, bool safe=false)
Definition: closure.h:98
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:61
typename ReplaceFst< Arc >::Arc Arc
Definition: fst.h:374
typename Arc::StateId StateId
Definition: closure.h:123
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:102
virtual void ReserveStates(StateId n)
Definition: mutable-fst.h:76
StateIterator(const ClosureFst< Arc > &fst)
Definition: closure.h:115
ClosureFst(const Fst< Arc > &fst, ClosureType closure_type)
Definition: closure.h:88
typename ReplaceFst< Arc >::Arc Arc
Definition: cache.h:1194
ClosureType
Definition: rational.h:24