FST  openfst-1.8.3
OpenFst Library
rmfinalepsilon.h
Go to the documentation of this file.
1 // Copyright 2005-2024 Google LLC
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 // See www.openfst.org for extensive documentation on this weighted
16 // finite-state transducer library.
17 //
18 // Function to remove of final states that have epsilon-only input arcs.
19 
20 #ifndef FST_RMFINALEPSILON_H_
21 #define FST_RMFINALEPSILON_H_
22 
23 #include <cstdint>
24 #include <vector>
25 
26 #include <fst/cc-visitors.h>
27 #include <fst/connect.h>
28 #include <fst/dfs-visit.h>
29 #include <fst/fst.h>
30 #include <fst/mutable-fst.h>
31 #include <unordered_set>
32 
33 namespace fst {
34 
35 // Removes final states that have epsilon-only input arcs.
36 template <class Arc>
38  using StateId = typename Arc::StateId;
39  using Weight = typename Arc::Weight;
40  // Determines the coaccesibility of states.
41  std::vector<bool> access;
42  std::vector<bool> coaccess;
43  uint64_t props = 0;
44  SccVisitor<Arc> scc_visitor(nullptr, &access, &coaccess, &props);
45  DfsVisit(*fst, &scc_visitor);
46  // Finds potential list of removable final states. These are final states that
47  // have no outgoing transitions or final states that have a non-coaccessible
48  // future.
49  std::unordered_set<StateId> finals;
50  for (StateIterator<Fst<Arc>> siter(*fst); !siter.Done(); siter.Next()) {
51  const auto s = siter.Value();
52  if (fst->Final(s) != Weight::Zero()) {
53  bool future_coaccess = false;
54  for (ArcIterator<Fst<Arc>> aiter(*fst, s); !aiter.Done(); aiter.Next()) {
55  const auto &arc = aiter.Value();
56  if (coaccess[arc.nextstate]) {
57  future_coaccess = true;
58  break;
59  }
60  }
61  if (!future_coaccess) finals.insert(s);
62  }
63  }
64  // Moves the final weight.
65  std::vector<Arc> arcs;
66  for (StateIterator<Fst<Arc>> siter(*fst); !siter.Done(); siter.Next()) {
67  const auto s = siter.Value();
68  auto weight = fst->Final(s);
69  arcs.clear();
70  for (ArcIterator<Fst<Arc>> aiter(*fst, s); !aiter.Done(); aiter.Next()) {
71  const auto &arc = aiter.Value();
72  // Next state is in the list of finals.
73  if (finals.find(arc.nextstate) != finals.end()) {
74  // Sums up all epsilon arcs.
75  if (arc.ilabel == 0 && arc.olabel == 0) {
76  weight = Plus(Times(fst->Final(arc.nextstate), arc.weight), weight);
77  } else {
78  arcs.push_back(arc);
79  }
80  } else {
81  arcs.push_back(arc);
82  }
83  }
84  // If some arcs (epsilon arcs) were deleted, delete all arcs and add back
85  // only the non-epsilon arcs.
86  if (arcs.size() < fst->NumArcs(s)) {
87  fst->DeleteArcs(s);
88  fst->SetFinal(s, weight);
89  for (const auto &arc : arcs) fst->AddArc(s, arc);
90  }
91  }
92  Connect(fst);
93 }
94 
95 } // namespace fst
96 
97 #endif // FST_RMFINALEPSILON_H_
ErrorWeight Plus(const ErrorWeight &, const ErrorWeight &)
Definition: error-weight.h:61
virtual size_t NumArcs(StateId) const =0
ErrorWeight Times(const ErrorWeight &, const ErrorWeight &)
Definition: error-weight.h:64
void DfsVisit(const FST &fst, Visitor *visitor, ArcFilter filter, bool access_only=false)
Definition: dfs-visit.h:112
void RmFinalEpsilon(MutableFst< Arc > *fst)
virtual Weight Final(StateId) const =0
void Connect(MutableFst< Arc > *fst)
Definition: connect.h:47
virtual void DeleteArcs(StateId, size_t)=0
virtual void AddArc(StateId, const Arc &)=0
virtual void SetFinal(StateId s, Weight weight=Weight::One())=0