FST  openfst-1.8.2
OpenFst Library
rmepsilon.h
Go to the documentation of this file.
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 // Functions and classes that implemement epsilon-removal.
19 
20 #ifndef FST_RMEPSILON_H_
21 #define FST_RMEPSILON_H_
22 
23 #include <cstdint>
24 #include <stack>
25 #include <string>
26 #include <utility>
27 #include <vector>
28 
29 #include <fst/log.h>
30 
31 #include <fst/arcfilter.h>
32 #include <fst/cache.h>
33 #include <fst/connect.h>
34 #include <fst/factor-weight.h>
35 #include <fst/invert.h>
36 #include <fst/prune.h>
37 #include <fst/queue.h>
38 #include <fst/shortest-distance.h>
39 #include <fst/topsort.h>
40 
41 #include <unordered_map>
42 
43 namespace fst {
44 
45 template <class Arc, class Queue>
47  : public ShortestDistanceOptions<Arc, Queue, EpsilonArcFilter<Arc>> {
48  using StateId = typename Arc::StateId;
49  using Weight = typename Arc::Weight;
50 
51  bool connect; // Connect output
52  Weight weight_threshold; // Pruning weight threshold.
53  StateId state_threshold; // Pruning state threshold.
54 
55  explicit RmEpsilonOptions(Queue *queue, float delta = kShortestDelta,
56  bool connect = true,
57  Weight weight_threshold = Weight::Zero(),
58  StateId state_threshold = kNoStateId)
59  : ShortestDistanceOptions<Arc, Queue, EpsilonArcFilter<Arc>>(
60  queue, EpsilonArcFilter<Arc>(), kNoStateId, delta),
61  connect(connect),
62  weight_threshold(std::move(weight_threshold)),
63  state_threshold(state_threshold) {}
64 };
65 
66 namespace internal {
67 
68 // Computation state of the epsilon-removal algorithm.
69 template <class Arc, class Queue>
71  public:
72  using Label = typename Arc::Label;
73  using StateId = typename Arc::StateId;
74  using Weight = typename Arc::Weight;
75 
76  RmEpsilonState(const Fst<Arc> &fst, std::vector<Weight> *distance,
77  const RmEpsilonOptions<Arc, Queue> &opts)
78  : fst_(fst),
79  distance_(distance),
80  sd_state_(fst_, distance, opts, true),
81  expand_id_(0) {}
82 
83  void Expand(StateId s);
84 
85  std::vector<Arc> &Arcs() { return arcs_; }
86 
87  const Weight &Final() const { return final_weight_; }
88 
89  bool Error() const { return sd_state_.Error(); }
90 
91  private:
92  struct Element {
93  Label ilabel;
94  Label olabel;
95  StateId nextstate;
96 
97  Element() {}
98 
99  Element(Label ilabel, Label olabel, StateId nexstate)
100  : ilabel(ilabel), olabel(olabel), nextstate(nexstate) {}
101  };
102 
103  struct ElementHash {
104  public:
105  size_t operator()(const Element &element) const {
106  static constexpr size_t prime0 = 7853;
107  static constexpr size_t prime1 = 7867;
108  return static_cast<size_t>(element.nextstate) +
109  static_cast<size_t>(element.ilabel) * prime0 +
110  static_cast<size_t>(element.olabel) * prime1;
111  }
112  };
113 
114  class ElementEqual {
115  public:
116  bool operator()(const Element &e1, const Element &e2) const {
117  return (e1.ilabel == e2.ilabel) && (e1.olabel == e2.olabel) &&
118  (e1.nextstate == e2.nextstate);
119  }
120  };
121 
122  using ElementMap = std::unordered_map<Element, std::pair<StateId, size_t>,
123  ElementHash, ElementEqual>;
124 
125  const Fst<Arc> &fst_;
126  // Distance from state being expanded in epsilon-closure.
127  std::vector<Weight> *distance_;
128  // Shortest distance algorithm computation state.
130  // Maps an element to a pair corresponding to a position in the arcs vector
131  // of the state being expanded. The element corresopnds to the position in
132  // the arcs_ vector if p.first is equal to the state being expanded.
133  ElementMap element_map_;
134  EpsilonArcFilter<Arc> eps_filter_;
135  std::stack<StateId, std::vector<StateId>>
136  eps_queue_; // Queue used to visit the epsilon-closure.
137  std::vector<bool> visited_; // True if the state has been visited.
138  std::vector<StateId> visited_states_; // List of visited states.
139  std::vector<Arc> arcs_; // Arcs of state being expanded.
140  Weight final_weight_; // Final weight of state being expanded.
141  StateId expand_id_; // Unique ID for each call to Expand
142 
143  RmEpsilonState(const RmEpsilonState &) = delete;
144  RmEpsilonState &operator=(const RmEpsilonState &) = delete;
145 };
146 
147 template <class Arc, class Queue>
148 void RmEpsilonState<Arc, Queue>::Expand(typename Arc::StateId source) {
149  final_weight_ = Weight::Zero();
150  arcs_.clear();
151  sd_state_.ShortestDistance(source);
152  if (sd_state_.Error()) return;
153  eps_queue_.push(source);
154  while (!eps_queue_.empty()) {
155  const auto state = eps_queue_.top();
156  eps_queue_.pop();
157  if (static_cast<decltype(state)>(visited_.size()) <= state) {
158  visited_.resize(state + 1, false);
159  }
160  if (visited_[state]) continue;
161  visited_[state] = true;
162  visited_states_.push_back(state);
163  for (ArcIterator<Fst<Arc>> aiter(fst_, state); !aiter.Done();
164  aiter.Next()) {
165  auto arc = aiter.Value();
166  arc.weight = Times((*distance_)[state], arc.weight);
167  if (eps_filter_(arc)) {
168  if (static_cast<decltype(arc.nextstate)>(visited_.size()) <=
169  arc.nextstate) {
170  visited_.resize(arc.nextstate + 1, false);
171  }
172  if (!visited_[arc.nextstate]) eps_queue_.push(arc.nextstate);
173  } else if (auto [insert_it, success] = element_map_.emplace(
174  Element(arc.ilabel, arc.olabel, arc.nextstate),
175  std::make_pair(expand_id_, arcs_.size()));
176  success) {
177  arcs_.push_back(std::move(arc));
178  } else if (auto &[xid, arc_idx] = insert_it->second; xid == expand_id_) {
179  auto &weight = arcs_[arc_idx].weight;
180  weight = Plus(weight, arc.weight);
181  } else {
182  xid = expand_id_;
183  arc_idx = arcs_.size();
184  arcs_.push_back(std::move(arc));
185  }
186  }
187  final_weight_ =
188  Plus(final_weight_, Times((*distance_)[state], fst_.Final(state)));
189  }
190 
191  for (const auto state_id : visited_states_) visited_[state_id] = false;
192  visited_states_.clear();
193  ++expand_id_;
194 }
195 
196 } // namespace internal
197 
198 // Removes epsilon-transitions (when both the input and output label are an
199 // epsilon) from a transducer. The result will be an equivalent FST that has no
200 // such epsilon transitions. This version modifies its input. It allows fine
201 // control via the options argument; see below for a simpler interface.
202 //
203 // The distance vector will be used to hold the shortest distances during the
204 // epsilon-closure computation. The state queue discipline and convergence delta
205 // are taken in the options argument.
206 template <class Arc, class Queue>
208  std::vector<typename Arc::Weight> *distance,
209  const RmEpsilonOptions<Arc, Queue> &opts) {
210  using StateId = typename Arc::StateId;
211  using Weight = typename Arc::Weight;
212  if (fst->Start() == kNoStateId) return;
213  // noneps_in[s] will be set to true iff s admits a non-epsilon incoming
214  // transition or is the start state.
215  std::vector<bool> noneps_in(fst->NumStates(), false);
216  noneps_in[fst->Start()] = true;
217  for (size_t i = 0; i < fst->NumStates(); ++i) {
218  for (ArcIterator<Fst<Arc>> aiter(*fst, i); !aiter.Done(); aiter.Next()) {
219  const auto &arc = aiter.Value();
220  if (arc.ilabel != 0 || arc.olabel != 0) {
221  noneps_in[arc.nextstate] = true;
222  }
223  }
224  }
225  // States sorted in topological order when (acyclic) or generic topological
226  // order (cyclic).
227  std::vector<StateId> states;
228  states.reserve(fst->NumStates());
229  if (fst->Properties(kTopSorted, false) & kTopSorted) {
230  for (size_t i = 0; i < fst->NumStates(); i++) states.push_back(i);
231  } else if (fst->Properties(kAcyclic, false) & kAcyclic) {
232  std::vector<StateId> order;
233  bool acyclic;
234  TopOrderVisitor<Arc> top_order_visitor(&order, &acyclic);
235  DfsVisit(*fst, &top_order_visitor, EpsilonArcFilter<Arc>());
236  // Sanity check: should be acyclic if property bit is set.
237  if (!acyclic) {
238  FSTERROR() << "RmEpsilon: Inconsistent acyclic property bit";
239  fst->SetProperties(kError, kError);
240  return;
241  }
242  states.resize(order.size());
243  for (StateId i = 0; i < order.size(); i++) states[order[i]] = i;
244  } else {
245  uint64_t props;
246  std::vector<StateId> scc;
247  SccVisitor<Arc> scc_visitor(&scc, nullptr, nullptr, &props);
248  DfsVisit(*fst, &scc_visitor, EpsilonArcFilter<Arc>());
249  std::vector<StateId> first(scc.size(), kNoStateId);
250  std::vector<StateId> next(scc.size(), kNoStateId);
251  for (StateId i = 0; i < scc.size(); i++) {
252  if (first[scc[i]] != kNoStateId) next[i] = first[scc[i]];
253  first[scc[i]] = i;
254  }
255  for (StateId i = 0; i < first.size(); i++) {
256  for (auto j = first[i]; j != kNoStateId; j = next[j]) {
257  states.push_back(j);
258  }
259  }
260  }
261  internal::RmEpsilonState<Arc, Queue> rmeps_state(*fst, distance, opts);
262  while (!states.empty()) {
263  const auto state = states.back();
264  states.pop_back();
265  if (!noneps_in[state] &&
266  (opts.connect || opts.weight_threshold != Weight::Zero() ||
267  opts.state_threshold != kNoStateId)) {
268  continue;
269  }
270  rmeps_state.Expand(state);
271  fst->SetFinal(state, rmeps_state.Final());
272  fst->DeleteArcs(state);
273  auto &arcs = rmeps_state.Arcs();
274  fst->ReserveArcs(state, arcs.size());
275  while (!arcs.empty()) {
276  fst->AddArc(state, arcs.back());
277  arcs.pop_back();
278  }
279  }
280  if (opts.connect || opts.weight_threshold != Weight::Zero() ||
281  opts.state_threshold != kNoStateId) {
282  for (size_t s = 0; s < fst->NumStates(); ++s) {
283  if (!noneps_in[s]) fst->DeleteArcs(s);
284  }
285  }
286  if (rmeps_state.Error()) fst->SetProperties(kError, kError);
287  fst->SetProperties(
290  if (opts.weight_threshold != Weight::Zero() ||
291  opts.state_threshold != kNoStateId) {
292  if constexpr (IsPath<Weight>::value) {
293  Prune(fst, opts.weight_threshold, opts.state_threshold);
294  } else {
295  FSTERROR() << "RmEpsilon: Weight must have path property: "
296  << Weight::Type();
297  fst->SetProperties(kError, kError);
298  return;
299  }
300  }
301  if (opts.connect && opts.weight_threshold == Weight::Zero() &&
302  opts.state_threshold == kNoStateId) {
303  Connect(fst);
304  }
305 }
306 
307 // Removes epsilon-transitions (when both the input and output label
308 // are an epsilon) from a transducer. The result will be an equivalent
309 // FST that has no such epsilon transitions. This version modifies its
310 // input. It has a simplified interface; see above for a version that
311 // allows finer control.
312 //
313 // Complexity:
314 //
315 // - Time:
316 //
317 // Unweighted: O(v^2 + ve).
318 // Acyclic: O(v^2 + V e).
319 // Tropical semiring: O(v^2 log V + ve).
320 // General: exponential.
321 //
322 // - Space: O(vE)
323 //
324 // where v is the number of states visited and e is the number of arcs visited.
325 //
326 // For more information, see:
327 //
328 // Mohri, M. 2002. Generic epsilon-removal and input epsilon-normalization
329 // algorithms for weighted transducers. International Journal of Computer
330 // Science 13(1): 129-143.
331 template <class Arc>
332 void RmEpsilon(MutableFst<Arc> *fst, bool connect = true,
333  typename Arc::Weight weight_threshold = Arc::Weight::Zero(),
334  typename Arc::StateId state_threshold = kNoStateId,
335  float delta = kShortestDelta) {
336  using StateId = typename Arc::StateId;
337  using Weight = typename Arc::Weight;
338  std::vector<Weight> distance;
341  &state_queue, delta, connect, weight_threshold, state_threshold);
342  RmEpsilon(fst, &distance, opts);
343 }
344 
346  float delta;
347 
348  explicit RmEpsilonFstOptions(const CacheOptions &opts,
349  float delta = kShortestDelta)
350  : CacheOptions(opts), delta(delta) {}
351 
352  explicit RmEpsilonFstOptions(float delta = kShortestDelta) : delta(delta) {}
353 };
354 
355 namespace internal {
356 
357 // Implementation of delayed RmEpsilonFst.
358 template <class Arc>
359 class RmEpsilonFstImpl : public CacheImpl<Arc> {
360  public:
361  using StateId = typename Arc::StateId;
362  using Weight = typename Arc::Weight;
363 
365  using State = typename Store::State;
366 
368  using FstImpl<Arc>::SetType;
372 
373  using CacheBaseImpl<CacheState<Arc>>::HasArcs;
374  using CacheBaseImpl<CacheState<Arc>>::HasFinal;
375  using CacheBaseImpl<CacheState<Arc>>::HasStart;
376  using CacheBaseImpl<CacheState<Arc>>::PushArc;
377  using CacheBaseImpl<CacheState<Arc>>::SetArcs;
378  using CacheBaseImpl<CacheState<Arc>>::SetFinal;
379  using CacheBaseImpl<CacheState<Arc>>::SetStart;
380 
382  : CacheImpl<Arc>(opts),
383  fst_(fst.Copy()),
384  delta_(opts.delta),
385  rmeps_state_(
386  *fst_, &distance_,
387  RmEpsilonOptions<Arc, FifoQueue<StateId>>(&queue_, delta_, false)) {
388  SetType("rmepsilon");
389  SetProperties(
390  RmEpsilonProperties(fst.Properties(kFstProperties, false), true),
392  SetInputSymbols(fst.InputSymbols());
393  SetOutputSymbols(fst.OutputSymbols());
394  }
395 
397  : CacheImpl<Arc>(impl),
398  fst_(impl.fst_->Copy(true)),
399  delta_(impl.delta_),
400  rmeps_state_(
401  *fst_, &distance_,
402  RmEpsilonOptions<Arc, FifoQueue<StateId>>(&queue_, delta_, false)) {
403  SetType("rmepsilon");
404  SetProperties(impl.Properties(), kCopyProperties);
405  SetInputSymbols(impl.InputSymbols());
406  SetOutputSymbols(impl.OutputSymbols());
407  }
408 
410  if (!HasStart()) SetStart(fst_->Start());
411  return CacheImpl<Arc>::Start();
412  }
413 
415  if (!HasFinal(s)) Expand(s);
416  return CacheImpl<Arc>::Final(s);
417  }
418 
419  size_t NumArcs(StateId s) {
420  if (!HasArcs(s)) Expand(s);
421  return CacheImpl<Arc>::NumArcs(s);
422  }
423 
425  if (!HasArcs(s)) Expand(s);
427  }
428 
430  if (!HasArcs(s)) Expand(s);
432  }
433 
434  uint64_t Properties() const override { return Properties(kFstProperties); }
435 
436  // Sets error if found and returns other FST impl properties.
437  uint64_t Properties(uint64_t mask) const override {
438  if ((mask & kError) &&
439  (fst_->Properties(kError, false) || rmeps_state_.Error())) {
440  SetProperties(kError, kError);
441  }
442  return FstImpl<Arc>::Properties(mask);
443  }
444 
446  if (!HasArcs(s)) Expand(s);
448  }
449 
450  void Expand(StateId s) {
451  rmeps_state_.Expand(s);
452  SetFinal(s, rmeps_state_.Final());
453  auto &arcs = rmeps_state_.Arcs();
454  while (!arcs.empty()) {
455  PushArc(s, std::move(arcs.back()));
456  arcs.pop_back();
457  }
458  SetArcs(s);
459  }
460 
461  private:
462  std::unique_ptr<const Fst<Arc>> fst_;
463  float delta_;
464  std::vector<Weight> distance_;
465  FifoQueue<StateId> queue_;
467 };
468 
469 } // namespace internal
470 
471 // Removes epsilon-transitions (when both the input and output label are an
472 // epsilon) from a transducer. The result will be an equivalent FST that has no
473 // such epsilon transitions. This version is a
474 // delayed FST.
475 //
476 // Complexity:
477 //
478 // - Time:
479 // Unweighted: O(v^2 + ve).
480 // General: exponential.
481 //
482 // - Space: O(vE)
483 //
484 // where v is the number of states visited and e is the number of arcs visited.
485 // Constant time to visit an input state or arc is assumed and exclusive of
486 // caching.
487 //
488 // For more information, see:
489 //
490 // Mohri, M. 2002. Generic epsilon-removal and input epsilon-normalization
491 // algorithms for weighted transducers. International Journal of Computer
492 // Science 13(1): 129-143.
493 //
494 // This class attaches interface to implementation and handles
495 // reference counting, delegating most methods to ImplToFst.
496 template <class A>
497 class RmEpsilonFst : public ImplToFst<internal::RmEpsilonFstImpl<A>> {
498  public:
499  using Arc = A;
500  using StateId = typename Arc::StateId;
501 
503  using State = typename Store::State;
505 
506  friend class ArcIterator<RmEpsilonFst<Arc>>;
508 
509  explicit RmEpsilonFst(const Fst<Arc> &fst)
510  : ImplToFst<Impl>(std::make_shared<Impl>(fst, RmEpsilonFstOptions())) {}
511 
512  RmEpsilonFst(const Fst<A> &fst, const RmEpsilonFstOptions &opts)
513  : ImplToFst<Impl>(std::make_shared<Impl>(fst, opts)) {}
514 
515  // See Fst<>::Copy() for doc.
516  RmEpsilonFst(const RmEpsilonFst &fst, bool safe = false)
517  : ImplToFst<Impl>(fst, safe) {}
518 
519  // Get a copy of this RmEpsilonFst. See Fst<>::Copy() for further doc.
520  RmEpsilonFst *Copy(bool safe = false) const override {
521  return new RmEpsilonFst(*this, safe);
522  }
523 
524  inline void InitStateIterator(StateIteratorData<Arc> *data) const override;
525 
526  void InitArcIterator(StateId s, ArcIteratorData<Arc> *data) const override {
527  GetMutableImpl()->InitArcIterator(s, data);
528  }
529 
530  private:
533 
534  RmEpsilonFst &operator=(const RmEpsilonFst &) = delete;
535 };
536 
537 // Specialization for RmEpsilonFst.
538 template <class Arc>
540  : public CacheStateIterator<RmEpsilonFst<Arc>> {
541  public:
542  explicit StateIterator(const RmEpsilonFst<Arc> &fst)
543  : CacheStateIterator<RmEpsilonFst<Arc>>(fst, fst.GetMutableImpl()) {}
544 };
545 
546 // Specialization for RmEpsilonFst.
547 template <class Arc>
549  : public CacheArcIterator<RmEpsilonFst<Arc>> {
550  public:
551  using StateId = typename Arc::StateId;
552 
554  : CacheArcIterator<RmEpsilonFst<Arc>>(fst.GetMutableImpl(), s) {
555  if (!fst.GetImpl()->HasArcs(s)) fst.GetMutableImpl()->Expand(s);
556  }
557 };
558 
559 template <class Arc>
561  StateIteratorData<Arc> *data) const {
562  data->base = std::make_unique<StateIterator<RmEpsilonFst<Arc>>>(*this);
563 }
564 
565 // Useful alias when using StdArc.
567 
568 } // namespace fst
569 
570 #endif // FST_RMEPSILON_H_
RmEpsilonState(const Fst< Arc > &fst, std::vector< Weight > *distance, const RmEpsilonOptions< Arc, Queue > &opts)
Definition: rmepsilon.h:76
ssize_t NumOutputEpsilons(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
Definition: expanded-fst.h:114
uint64_t Properties() const override
Definition: rmepsilon.h:434
void RmEpsilon(MutableFst< Arc > *fst, std::vector< typename Arc::Weight > *distance, const RmEpsilonOptions< Arc, Queue > &opts)
Definition: rmepsilon.h:207
typename Arc::Weight Weight
Definition: rmepsilon.h:362
virtual uint64_t Properties(uint64_t mask, bool test) const =0
void InitArcIterator(StateId s, ArcIteratorData< Arc > *data)
Definition: rmepsilon.h:445
ErrorWeight Plus(const ErrorWeight &, const ErrorWeight &)
Definition: error-weight.h:60
size_t NumOutputEpsilons(StateId s)
Definition: rmepsilon.h:429
uint64_t RmEpsilonProperties(uint64_t inprops, bool delayed=false)
Definition: properties.cc:359
RmEpsilonFst(const RmEpsilonFst &fst, bool safe=false)
Definition: rmepsilon.h:516
const Weight & Final() const
Definition: rmepsilon.h:87
void InitStateIterator(StateIteratorData< Arc > *data) const override
Definition: rmepsilon.h:560
Arc::Weight Final(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
Definition: expanded-fst.h:97
const SymbolTable * OutputSymbols() const
Definition: fst.h:762
ErrorWeight Times(const ErrorWeight &, const ErrorWeight &)
Definition: error-weight.h:63
constexpr uint64_t kError
Definition: properties.h:51
void DfsVisit(const FST &fst, Visitor *visitor, ArcFilter filter, bool access_only=false)
Definition: dfs-visit.h:109
typename Store::State State
Definition: rmepsilon.h:503
SetType
Definition: set-weight.h:52
typename RmEpsilonFst< Arc >::Arc Arc
Definition: cache.h:1149
void Connect(MutableFst< Arc > *fst)
Definition: connect.h:278
ssize_t NumArcs(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
Definition: expanded-fst.h:103
constexpr uint64_t kTopSorted
Definition: properties.h:118
constexpr int kNoStateId
Definition: fst.h:202
void Prune(MutableFst< Arc > *fst, const PruneOptions< Arc, ArcFilter > &opts=PruneOptions< Arc, ArcFilter >())
Definition: prune.h:111
virtual void ReserveArcs(StateId, size_t)
Definition: mutable-fst.h:99
#define FSTERROR()
Definition: util.h:53
size_t NumInputEpsilons(StateId s)
Definition: rmepsilon.h:424
RmEpsilonFst(const Fst< A > &fst, const RmEpsilonFstOptions &opts)
Definition: rmepsilon.h:512
ArcIterator(const RmEpsilonFst< Arc > &fst, StateId s)
Definition: rmepsilon.h:553
ssize_t NumInputEpsilons(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
Definition: expanded-fst.h:108
RmEpsilonFstOptions(const CacheOptions &opts, float delta=kShortestDelta)
Definition: rmepsilon.h:348
RmEpsilonFst * Copy(bool safe=false) const override
Definition: rmepsilon.h:520
std::vector< Arc > & Arcs()
Definition: rmepsilon.h:85
constexpr uint64_t kCopyProperties
Definition: properties.h:162
constexpr uint64_t kAcyclic
Definition: properties.h:110
virtual void SetProperties(uint64_t props, uint64_t mask)=0
typename FirstCacheStore< VectorCacheStore< CacheState< Arc > > >::State State
Definition: cache.h:666
virtual void DeleteArcs(StateId, size_t)=0
virtual StateId Start() const =0
size_t NumArcs(StateId s)
Definition: rmepsilon.h:419
RmEpsilonOptions(Queue *queue, float delta=kShortestDelta, bool connect=true, Weight weight_threshold=Weight::Zero(), StateId state_threshold=kNoStateId)
Definition: rmepsilon.h:55
std::unique_ptr< StateIteratorBase< Arc > > base
Definition: fst.h:382
constexpr float kShortestDelta
void Expand(const FstClass &ifst, const std::vector< std::pair< int64_t, int64_t >> &parens, const std::vector< int64_t > &assignments, MutableFstClass *ofst, const MPdtExpandOptions &opts)
Definition: mpdtscript.cc:53
typename Arc::StateId StateId
Definition: rmepsilon.h:361
RmEpsilonFstImpl(const Fst< Arc > &fst, const RmEpsilonFstOptions &opts)
Definition: rmepsilon.h:381
constexpr uint64_t kFstProperties
Definition: properties.h:325
virtual void AddArc(StateId, const Arc &)=0
typename Arc::Weight Weight
Definition: rmepsilon.h:49
RmEpsilonFstImpl(const RmEpsilonFstImpl &impl)
Definition: rmepsilon.h:396
typename internal::RmEpsilonFstImpl< Arc >::Arc Arc
Definition: fst.h:211
void InitArcIterator(StateId s, ArcIteratorData< Arc > *data) const override
Definition: rmepsilon.h:526
RmEpsilonFst(const Fst< Arc > &fst)
Definition: rmepsilon.h:509
typename RmEpsilonFst< Arc >::Arc Arc
Definition: cache.h:1195
virtual const SymbolTable * InputSymbols() const =0
const SymbolTable * InputSymbols() const
Definition: fst.h:760
typename Arc::StateId StateId
Definition: rmepsilon.h:48
virtual void SetFinal(StateId s, Weight weight=Weight::One())=0
void Expand(const Fst< Arc > &ifst, const std::vector< std::pair< typename Arc::Label, typename Arc::Label >> &parens, const std::vector< typename Arc::Label > &assignments, MutableFst< Arc > *ofst, const MPdtExpandOptions &opts)
Definition: expand.h:316
uint64_t Properties(uint64_t mask) const override
Definition: rmepsilon.h:437
StateId state_threshold
Definition: rmepsilon.h:53
StateIterator(const RmEpsilonFst< Arc > &fst)
Definition: rmepsilon.h:542
typename CacheState< Arc >::Arc Arc
Definition: cache.h:852
Impl * GetMutableImpl() const
Definition: fst.h:1028
RmEpsilonFstOptions(float delta=kShortestDelta)
Definition: rmepsilon.h:352
virtual StateId NumStates() const =0
std::bool_constant<(W::Properties()&kPath)!=0 > IsPath
Definition: weight.h:159
const Impl * GetImpl() const
Definition: fst.h:1026
virtual const SymbolTable * OutputSymbols() const =0