FST  openfst-1.7.2
OpenFst Library
rmfinalepsilon.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 // Function to remove of final states that have epsilon-only input arcs.
5 
6 #ifndef FST_RMFINALEPSILON_H_
7 #define FST_RMFINALEPSILON_H_
8 
9 #include <unordered_set>
10 #include <vector>
11 
12 #include <fst/connect.h>
13 #include <fst/mutable-fst.h>
14 
15 
16 namespace fst {
17 
18 // Removes final states that have epsilon-only input arcs.
19 template <class Arc>
21  using StateId = typename Arc::StateId;
22  using Weight = typename Arc::Weight;
23  // Determines the coaccesibility of states.
24  std::vector<bool> access;
25  std::vector<bool> coaccess;
26  uint64 props = 0;
27  SccVisitor<Arc> scc_visitor(nullptr, &access, &coaccess, &props);
28  DfsVisit(*fst, &scc_visitor);
29  // Finds potential list of removable final states. These are final states that
30  // have no outgoing transitions or final states that have a non-coaccessible
31  // future.
32  std::unordered_set<StateId> finals;
33  for (StateIterator<Fst<Arc>> siter(*fst); !siter.Done(); siter.Next()) {
34  const auto s = siter.Value();
35  if (fst->Final(s) != Weight::Zero()) {
36  bool future_coaccess = false;
37  for (ArcIterator<Fst<Arc>> aiter(*fst, s); !aiter.Done(); aiter.Next()) {
38  const auto &arc = aiter.Value();
39  if (coaccess[arc.nextstate]) {
40  future_coaccess = true;
41  break;
42  }
43  }
44  if (!future_coaccess) finals.insert(s);
45  }
46  }
47  // Moves the final weight.
48  std::vector<Arc> arcs;
49  for (StateIterator<Fst<Arc>> siter(*fst); !siter.Done(); siter.Next()) {
50  const auto s = siter.Value();
51  auto weight = fst->Final(s);
52  arcs.clear();
53  for (ArcIterator<Fst<Arc>> aiter(*fst, s); !aiter.Done(); aiter.Next()) {
54  const auto &arc = aiter.Value();
55  // Next state is in the list of finals.
56  if (finals.find(arc.nextstate) != finals.end()) {
57  // Sums up all epsilon arcs.
58  if (arc.ilabel == 0 && arc.olabel == 0) {
59  weight = Plus(Times(fst->Final(arc.nextstate), arc.weight), weight);
60  } else {
61  arcs.push_back(arc);
62  }
63  } else {
64  arcs.push_back(arc);
65  }
66  }
67  // If some arcs (epsilon arcs) were deleted, delete all arcs and add back
68  // only the non-epsilon arcs.
69  if (arcs.size() < fst->NumArcs(s)) {
70  fst->DeleteArcs(s);
71  fst->SetFinal(s, weight);
72  for (const auto &arc : arcs) fst->AddArc(s, arc);
73  }
74  }
75  Connect(fst);
76 }
77 
78 } // namespace fst
79 
80 #endif // FST_RMFINALEPSILON_H_
uint64_t uint64
Definition: types.h:32
virtual size_t NumArcs(StateId) const =0
virtual void AddArc(StateId, const Arc &arc)=0
void DfsVisit(const FST &fst, Visitor *visitor, ArcFilter filter, bool access_only=false)
Definition: dfs-visit.h:94
void RmFinalEpsilon(MutableFst< Arc > *fst)
virtual Weight Final(StateId) const =0
ExpectationWeight< X1, X2 > Times(const ExpectationWeight< X1, X2 > &w1, const ExpectationWeight< X1, X2 > &w2)
void Connect(MutableFst< Arc > *fst)
Definition: connect.h:268
virtual void SetFinal(StateId, Weight)=0
ExpectationWeight< X1, X2 > Plus(const ExpectationWeight< X1, X2 > &w1, const ExpectationWeight< X1, X2 > &w2)
virtual void DeleteArcs(StateId, size_t n)=0