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