FST  openfst-1.8.3
OpenFst Library
connect.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 // Classes and functions to remove unsuccessful paths from an FST.
19 
20 #ifndef FST_CONNECT_H_
21 #define FST_CONNECT_H_
22 
23 #include <algorithm>
24 #include <cstddef>
25 #include <cstdint>
26 #include <utility>
27 #include <vector>
28 
29 #include <fst/cc-visitors.h>
30 #include <fst/dfs-visit.h>
31 #include <fst/fst.h>
32 #include <fst/mutable-fst.h>
33 #include <fst/properties.h>
34 
35 namespace fst {
36 
37 // Trims an FST, removing states and arcs that are not on successful paths.
38 // This version modifies its input.
39 //
40 // Complexity:
41 //
42 // Time: O(V + E)
43 // Space: O(V + E)
44 //
45 // where V = # of states and E = # of arcs.
46 template <class Arc>
48  using StateId = typename Arc::StateId;
49  std::vector<bool> access;
50  std::vector<bool> coaccess;
51  uint64_t props = 0;
52  SccVisitor<Arc> scc_visitor(nullptr, &access, &coaccess, &props);
53  DfsVisit(*fst, &scc_visitor);
54  std::vector<StateId> dstates;
55  dstates.reserve(access.size());
56  for (StateId s = 0; s < access.size(); ++s) {
57  if (!access[s] || !coaccess[s]) dstates.push_back(s);
58  }
59  fst->DeleteStates(dstates);
61 }
62 
63 // Returns an acyclic FST where each SCC in the input FST has been condensed to
64 // a single state with transitions between SCCs retained and within SCCs
65 // dropped. Also populates 'scc' with a mapping from input to output states.
66 template <class Arc>
67 void Condense(const Fst<Arc> &ifst, MutableFst<Arc> *ofst,
68  std::vector<typename Arc::StateId> *scc) {
69  using StateId = typename Arc::StateId;
70  ofst->DeleteStates();
71  uint64_t props = 0;
72  SccVisitor<Arc> scc_visitor(scc, nullptr, nullptr, &props);
73  DfsVisit(ifst, &scc_visitor);
74  const auto iter = std::max_element(scc->cbegin(), scc->cend());
75  if (iter == scc->cend()) return;
76  const StateId num_condensed_states = 1 + *iter;
77  ofst->ReserveStates(num_condensed_states);
78  for (StateId c = 0; c < num_condensed_states; ++c) {
79  ofst->AddState();
80  }
81  for (StateId s = 0; s < scc->size(); ++s) {
82  const auto c = (*scc)[s];
83  if (s == ifst.Start()) ofst->SetStart(c);
84  const auto weight = ifst.Final(s);
85  if (weight != Arc::Weight::Zero())
86  ofst->SetFinal(c, Plus(ofst->Final(c), weight));
87  for (ArcIterator<Fst<Arc>> aiter(ifst, s); !aiter.Done(); aiter.Next()) {
88  const auto &arc = aiter.Value();
89  const auto nextc = (*scc)[arc.nextstate];
90  if (nextc != c) {
91  Arc condensed_arc = arc;
92  condensed_arc.nextstate = nextc;
93  ofst->AddArc(c, std::move(condensed_arc));
94  }
95  }
96  }
98 }
99 
100 } // namespace fst
101 
102 #endif // FST_CONNECT_H_
ErrorWeight Plus(const ErrorWeight &, const ErrorWeight &)
Definition: error-weight.h:61
constexpr uint64_t kCoAccessible
Definition: properties.h:129
void DfsVisit(const FST &fst, Visitor *visitor, ArcFilter filter, bool access_only=false)
Definition: dfs-visit.h:112
constexpr uint64_t kInitialAcyclic
Definition: properties.h:116
virtual Weight Final(StateId) const =0
virtual void SetStart(StateId)=0
void Connect(MutableFst< Arc > *fst)
Definition: connect.h:47
constexpr uint64_t kAcyclic
Definition: properties.h:111
virtual void SetProperties(uint64_t props, uint64_t mask)=0
constexpr uint64_t kAccessible
Definition: properties.h:124
virtual StateId Start() const =0
virtual void AddArc(StateId, const Arc &)=0
void Condense(const Fst< Arc > &ifst, MutableFst< Arc > *ofst, std::vector< typename Arc::StateId > *scc)
Definition: connect.h:67
virtual StateId AddState()=0
virtual void ReserveStates(size_t)
Definition: mutable-fst.h:101
virtual void SetFinal(StateId s, Weight weight=Weight::One())=0
virtual void DeleteStates(const std::vector< StateId > &)=0