1 // Copyright 2005-2020 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 <vector>
24
25 #include <fst/types.h>
26
27 #include <fst/connect.h>
28 #include <fst/mutable-fst.h>
29
30 #include <unordered_set>
31
32 namespace fst {
33
34 // Removes final states that have epsilon-only input arcs.
35 template <class Arc>
RmFinalEpsilon(MutableFst<Arc> * fst)36 void RmFinalEpsilon(MutableFst<Arc> *fst) {
37 using StateId = typename Arc::StateId;
38 using Weight = typename Arc::Weight;
39 // Determines the coaccesibility of states.
40 std::vector<bool> access;
41 std::vector<bool> coaccess;
42 uint64 props = 0;
43 SccVisitor<Arc> scc_visitor(nullptr, &access, &coaccess, &props);
44 DfsVisit(*fst, &scc_visitor);
45 // Finds potential list of removable final states. These are final states that
46 // have no outgoing transitions or final states that have a non-coaccessible
47 // future.
48 std::unordered_set<StateId> finals;
49 for (StateIterator<Fst<Arc>> siter(*fst); !siter.Done(); siter.Next()) {
50 const auto s = siter.Value();
51 if (fst->Final(s) != Weight::Zero()) {
52 bool future_coaccess = false;
53 for (ArcIterator<Fst<Arc>> aiter(*fst, s); !aiter.Done(); aiter.Next()) {
54 const auto &arc = aiter.Value();
55 if (coaccess[arc.nextstate]) {
56 future_coaccess = true;
57 break;
58 }
59 }
60 if (!future_coaccess) finals.insert(s);
61 }
62 }
63 // Moves the final weight.
64 std::vector<Arc> arcs;
65 for (StateIterator<Fst<Arc>> siter(*fst); !siter.Done(); siter.Next()) {
66 const auto s = siter.Value();
67 auto weight = fst->Final(s);
68 arcs.clear();
69 for (ArcIterator<Fst<Arc>> aiter(*fst, s); !aiter.Done(); aiter.Next()) {
70 const auto &arc = aiter.Value();
71 // Next state is in the list of finals.
72 if (finals.find(arc.nextstate) != finals.end()) {
73 // Sums up all epsilon arcs.
74 if (arc.ilabel == 0 && arc.olabel == 0) {
75 weight = Plus(Times(fst->Final(arc.nextstate), arc.weight), weight);
76 } else {
77 arcs.push_back(arc);
78 }
79 } else {
80 arcs.push_back(arc);
81 }
82 }
83 // If some arcs (epsilon arcs) were deleted, delete all arcs and add back
84 // only the non-epsilon arcs.
85 if (arcs.size() < fst->NumArcs(s)) {
86 fst->DeleteArcs(s);
87 fst->SetFinal(s, weight);
88 for (const auto &arc : arcs) fst->AddArc(s, arc);
89 }
90 }
91 Connect(fst);
92 }
93
94 } // namespace fst
95
96 #endif // FST_RMFINALEPSILON_H_
97