FST  openfst-1.7.2
OpenFst Library
minimize.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 to minimize an FST.
5 
6 #ifndef FST_MINIMIZE_H_
7 #define FST_MINIMIZE_H_
8 
9 #include <cmath>
10 
11 #include <algorithm>
12 #include <map>
13 #include <queue>
14 #include <utility>
15 #include <vector>
16 
17 #include <fst/log.h>
18 
19 #include <fst/arcsort.h>
20 #include <fst/connect.h>
21 #include <fst/dfs-visit.h>
22 #include <fst/encode.h>
23 #include <fst/factor-weight.h>
24 #include <fst/fst.h>
25 #include <fst/mutable-fst.h>
26 #include <fst/partition.h>
27 #include <fst/push.h>
28 #include <fst/queue.h>
29 #include <fst/reverse.h>
30 #include <fst/shortest-distance.h>
31 #include <fst/state-map.h>
32 
33 
34 namespace fst {
35 namespace internal {
36 
37 // Comparator for creating partition.
38 template <class Arc>
40  public:
41  using StateId = typename Arc::StateId;
42  using Weight = typename Arc::Weight;
43 
44  StateComparator(const Fst<Arc> &fst, const Partition<StateId> &partition)
45  : fst_(fst), partition_(partition) {}
46 
47  // Compares state x with state y based on sort criteria.
48  bool operator()(const StateId x, const StateId y) const {
49  // Checks for final state equivalence.
50  const auto xfinal = fst_.Final(x).Hash();
51  const auto yfinal = fst_.Final(y).Hash();
52  if (xfinal < yfinal) {
53  return true;
54  } else if (xfinal > yfinal) {
55  return false;
56  }
57  // Checks for number of arcs.
58  if (fst_.NumArcs(x) < fst_.NumArcs(y)) return true;
59  if (fst_.NumArcs(x) > fst_.NumArcs(y)) return false;
60  // If the number of arcs are equal, checks for arc match.
61  for (ArcIterator<Fst<Arc>> aiter1(fst_, x), aiter2(fst_, y);
62  !aiter1.Done() && !aiter2.Done(); aiter1.Next(), aiter2.Next()) {
63  const auto &arc1 = aiter1.Value();
64  const auto &arc2 = aiter2.Value();
65  if (arc1.ilabel < arc2.ilabel) return true;
66  if (arc1.ilabel > arc2.ilabel) return false;
67  if (partition_.ClassId(arc1.nextstate) <
68  partition_.ClassId(arc2.nextstate))
69  return true;
70  if (partition_.ClassId(arc1.nextstate) >
71  partition_.ClassId(arc2.nextstate))
72  return false;
73  }
74  return false;
75  }
76 
77  private:
78  const Fst<Arc> &fst_;
79  const Partition<StateId> &partition_;
80 };
81 
82 // Computes equivalence classes for cyclic unweighted acceptors. For cyclic
83 // minimization we use the classic Hopcroft minimization algorithm, which has
84 // complexity O(E log V) where E is the number of arcs and V is the number of
85 // states.
86 //
87 // For more information, see:
88 //
89 // Hopcroft, J. 1971. An n Log n algorithm for minimizing states in a finite
90 // automaton. Ms, Stanford University.
91 //
92 // Note: the original presentation of the paper was for a finite automaton (==
93 // deterministic, unweighted acceptor), but we also apply it to the
94 // nondeterministic case, where it is also applicable as long as the semiring is
95 // idempotent (if the semiring is not idempotent, there are some complexities
96 // in keeping track of the weight when there are multiple arcs to states that
97 // will be merged, and we don't deal with this).
98 template <class Arc, class Queue>
100  public:
101  using Label = typename Arc::Label;
102  using StateId = typename Arc::StateId;
103  using ClassId = typename Arc::StateId;
104  using Weight = typename Arc::Weight;
106 
108  Initialize(fst);
109  Compute(fst);
110  }
111 
112  const Partition<StateId> &GetPartition() const { return P_; }
113 
114  private:
115  // StateILabelHasher is a hashing object that computes a hash-function
116  // of an FST state that depends only on the set of ilabels on arcs leaving
117  // the state [note: it assumes that the arcs are ilabel-sorted].
118  // In order to work correctly for non-deterministic automata, multiple
119  // instances of the same ilabel count the same as a single instance.
120  class StateILabelHasher {
121  public:
122  explicit StateILabelHasher(const Fst<Arc> &fst) : fst_(fst) {}
123 
124  using Label = typename Arc::Label;
125  using StateId = typename Arc::StateId;
126 
127  size_t operator()(const StateId s) {
128  const size_t p1 = 7603;
129  const size_t p2 = 433024223;
130  size_t result = p2;
131  size_t current_ilabel = kNoLabel;
132  for (ArcIterator<Fst<Arc>> aiter(fst_, s); !aiter.Done(); aiter.Next()) {
133  Label this_ilabel = aiter.Value().ilabel;
134  if (this_ilabel != current_ilabel) { // Ignores repeats.
135  result = p1 * result + this_ilabel;
136  current_ilabel = this_ilabel;
137  }
138  }
139  return result;
140  }
141 
142  private:
143  const Fst<Arc> &fst_;
144  };
145 
146  class ArcIterCompare {
147  public:
148  explicit ArcIterCompare(const Partition<StateId> &partition)
149  : partition_(partition) {}
150 
151  ArcIterCompare(const ArcIterCompare &comp) : partition_(comp.partition_) {}
152 
153  // Compares two iterators based on their input labels.
154  bool operator()(const ArcIterator<Fst<RevArc>> *x,
155  const ArcIterator<Fst<RevArc>> *y) const {
156  const auto &xarc = x->Value();
157  const auto &yarc = y->Value();
158  return xarc.ilabel > yarc.ilabel;
159  }
160 
161  private:
162  const Partition<StateId> &partition_;
163  };
164 
165  using ArcIterQueue =
166  std::priority_queue<ArcIterator<Fst<RevArc>> *,
167  std::vector<ArcIterator<Fst<RevArc>> *>,
168  ArcIterCompare>;
169 
170  private:
171  // Prepartitions the space into equivalence classes. We ensure that final and
172  // non-final states always go into different equivalence classes, and we use
173  // class StateILabelHasher to make sure that most of the time, states with
174  // different sets of ilabels on arcs leaving them, go to different partitions.
175  // Note: for the O(n) guarantees we don't rely on the goodness of this
176  // hashing function---it just provides a bonus speedup.
177  void PrePartition(const ExpandedFst<Arc> &fst) {
178  VLOG(5) << "PrePartition";
179  StateId next_class = 0;
180  auto num_states = fst.NumStates();
181  // Allocates a temporary vector to store the initial class mappings, so that
182  // we can allocate the classes all at once.
183  std::vector<StateId> state_to_initial_class(num_states);
184  {
185  // We maintain two maps from hash-value to class---one for final states
186  // (final-prob == One()) and one for non-final states
187  // (final-prob == Zero()). We are processing unweighted acceptors, so the
188  // are the only two possible values.
189  using HashToClassMap = std::unordered_map<size_t, StateId>;
190  HashToClassMap hash_to_class_nonfinal;
191  HashToClassMap hash_to_class_final;
192  StateILabelHasher hasher(fst);
193  for (StateId s = 0; s < num_states; ++s) {
194  size_t hash = hasher(s);
195  HashToClassMap &this_map =
196  (fst.Final(s) != Weight::Zero() ? hash_to_class_final
197  : hash_to_class_nonfinal);
198  // Avoids two map lookups by using 'insert' instead of 'find'.
199  auto p = this_map.insert(std::make_pair(hash, next_class));
200  state_to_initial_class[s] = p.second ? next_class++ : p.first->second;
201  }
202  // Lets the unordered_maps go out of scope before we allocate the classes,
203  // to reduce the maximum amount of memory used.
204  }
205  P_.AllocateClasses(next_class);
206  for (StateId s = 0; s < num_states; ++s) {
207  P_.Add(s, state_to_initial_class[s]);
208  }
209  for (StateId c = 0; c < next_class; ++c) L_.Enqueue(c);
210  VLOG(5) << "Initial Partition: " << P_.NumClasses();
211  }
212 
213  // Creates inverse transition Tr_ = rev(fst), loops over states in FST and
214  // splits on final, creating two blocks in the partition corresponding to
215  // final, non-final.
216  void Initialize(const ExpandedFst<Arc> &fst) {
217  // Constructs Tr.
218  Reverse(fst, &Tr_);
219  ILabelCompare<RevArc> ilabel_comp;
220  ArcSort(&Tr_, ilabel_comp);
221  // Tells the partition how many elements to allocate. The first state in
222  // Tr_ is super-final state.
223  P_.Initialize(Tr_.NumStates() - 1);
224  // Prepares initial partition.
225  PrePartition(fst);
226  // Allocates arc iterator queue.
227  ArcIterCompare comp(P_);
228  aiter_queue_.reset(new ArcIterQueue(comp));
229  }
230  // Partitions all classes with destination C.
231  void Split(ClassId C) {
232  // Prepares priority queue: opens arc iterator for each state in C, and
233  // inserts into priority queue.
234  for (PartitionIterator<StateId> siter(P_, C); !siter.Done(); siter.Next()) {
235  StateId s = siter.Value();
236  if (Tr_.NumArcs(s + 1)) {
237  aiter_queue_->push(new ArcIterator<Fst<RevArc>>(Tr_, s + 1));
238  }
239  }
240  // Now pops arc iterator from queue, splits entering equivalence class, and
241  // re-inserts updated iterator into queue.
242  Label prev_label = -1;
243  while (!aiter_queue_->empty()) {
244  std::unique_ptr<ArcIterator<Fst<RevArc>>> aiter(aiter_queue_->top());
245  aiter_queue_->pop();
246  if (aiter->Done()) continue;
247  const auto &arc = aiter->Value();
248  auto from_state = aiter->Value().nextstate - 1;
249  auto from_label = arc.ilabel;
250  if (prev_label != from_label) P_.FinalizeSplit(&L_);
251  auto from_class = P_.ClassId(from_state);
252  if (P_.ClassSize(from_class) > 1) P_.SplitOn(from_state);
253  prev_label = from_label;
254  aiter->Next();
255  if (!aiter->Done()) aiter_queue_->push(aiter.release());
256  }
257  P_.FinalizeSplit(&L_);
258  }
259 
260  // Main loop for Hopcroft minimization.
261  void Compute(const Fst<Arc> &fst) {
262  // Processes active classes (FIFO, or FILO).
263  while (!L_.Empty()) {
264  const auto C = L_.Head();
265  L_.Dequeue();
266  Split(C); // Splits on C, all labels in C.
267  }
268  }
269 
270  private:
271  // Partioning of states into equivalence classes.
273  // Set of active classes to be processed in partition P.
274  Queue L_;
275  // Reverses transition function.
276  VectorFst<RevArc> Tr_;
277  // Priority queue of open arc iterators for all states in the splitter
278  // equivalence class.
279  std::unique_ptr<ArcIterQueue> aiter_queue_;
280 };
281 
282 // Computes equivalence classes for acyclic FST.
283 //
284 // Complexity:
285 //
286 // O(E)
287 //
288 // where E is the number of arcs.
289 //
290 // For more information, see:
291 //
292 // Revuz, D. 1992. Minimization of acyclic deterministic automata in linear
293 // time. Theoretical Computer Science 92(1): 181-189.
294 template <class Arc>
296  public:
297  using Label = typename Arc::Label;
298  using StateId = typename Arc::StateId;
299  using ClassId = typename Arc::StateId;
300  using Weight = typename Arc::Weight;
301 
303  Initialize(fst);
304  Refine(fst);
305  }
306 
307  const Partition<StateId> &GetPartition() { return partition_; }
308 
309  private:
310  // DFS visitor to compute the height (distance) to final state.
311  class HeightVisitor {
312  public:
313  HeightVisitor() : max_height_(0), num_states_(0) {}
314 
315  // Invoked before DFS visit.
316  void InitVisit(const Fst<Arc> &fst) {}
317 
318  // Invoked when state is discovered (2nd arg is DFS tree root).
319  bool InitState(StateId s, StateId root) {
320  // Extends height array and initialize height (distance) to 0.
321  for (StateId i = height_.size(); i <= s; ++i) height_.push_back(-1);
322  if (s >= num_states_) num_states_ = s + 1;
323  return true;
324  }
325 
326  // Invoked when tree arc examined (to undiscovered state).
327  bool TreeArc(StateId s, const Arc &arc) { return true; }
328 
329  // Invoked when back arc examined (to unfinished state).
330  bool BackArc(StateId s, const Arc &arc) { return true; }
331 
332  // Invoked when forward or cross arc examined (to finished state).
333  bool ForwardOrCrossArc(StateId s, const Arc &arc) {
334  if (height_[arc.nextstate] + 1 > height_[s]) {
335  height_[s] = height_[arc.nextstate] + 1;
336  }
337  return true;
338  }
339 
340  // Invoked when state finished (parent is kNoStateId for tree root).
341  void FinishState(StateId s, StateId parent, const Arc *parent_arc) {
342  if (height_[s] == -1) height_[s] = 0;
343  const auto h = height_[s] + 1;
344  if (parent >= 0) {
345  if (h > height_[parent]) height_[parent] = h;
346  if (h > max_height_) max_height_ = h;
347  }
348  }
349 
350  // Invoked after DFS visit.
351  void FinishVisit() {}
352 
353  size_t max_height() const { return max_height_; }
354 
355  const std::vector<StateId> &height() const { return height_; }
356 
357  size_t num_states() const { return num_states_; }
358 
359  private:
360  std::vector<StateId> height_;
361  size_t max_height_;
362  size_t num_states_;
363  };
364 
365  private:
366  // Cluster states according to height (distance to final state)
367  void Initialize(const Fst<Arc> &fst) {
368  // Computes height (distance to final state).
369  HeightVisitor hvisitor;
370  DfsVisit(fst, &hvisitor);
371  // Creates initial partition based on height.
372  partition_.Initialize(hvisitor.num_states());
373  partition_.AllocateClasses(hvisitor.max_height() + 1);
374  const auto &hstates = hvisitor.height();
375  for (StateId s = 0; s < hstates.size(); ++s) partition_.Add(s, hstates[s]);
376  }
377 
378  // Refines states based on arc sort (out degree, arc equivalence).
379  void Refine(const Fst<Arc> &fst) {
380  using EquivalenceMap = std::map<StateId, StateId, StateComparator<Arc>>;
381  StateComparator<Arc> comp(fst, partition_);
382  // Starts with tail (height = 0).
383  auto height = partition_.NumClasses();
384  for (StateId h = 0; h < height; ++h) {
385  EquivalenceMap equiv_classes(comp);
386  // Sorts states within equivalence class.
387  PartitionIterator<StateId> siter(partition_, h);
388  equiv_classes[siter.Value()] = h;
389  for (siter.Next(); !siter.Done(); siter.Next()) {
390  auto insert_result =
391  equiv_classes.insert(std::make_pair(siter.Value(), kNoStateId));
392  if (insert_result.second) {
393  insert_result.first->second = partition_.AddClass();
394  }
395  }
396  // Creates refined partition.
397  for (siter.Reset(); !siter.Done();) {
398  const auto s = siter.Value();
399  const auto old_class = partition_.ClassId(s);
400  const auto new_class = equiv_classes[s];
401  // A move operation can invalidate the iterator, so we first update
402  // the iterator to the next element before we move the current element
403  // out of the list.
404  siter.Next();
405  if (old_class != new_class) partition_.Move(s, new_class);
406  }
407  }
408  }
409 
410  private:
411  Partition<StateId> partition_;
412 };
413 
414 // Given a partition and a Mutable FST, merges states of Fst in place (i.e.,
415 // destructively). Merging works by taking the first state in a class of the
416 // partition to be the representative state for the class. Each arc is then
417 // reconnected to this state. All states in the class are merged by adding
418 // their arcs to the representative state.
419 template <class Arc>
421  MutableFst<Arc> *fst) {
422  using StateId = typename Arc::StateId;
423  std::vector<StateId> state_map(partition.NumClasses());
424  for (StateId i = 0; i < partition.NumClasses(); ++i) {
425  PartitionIterator<StateId> siter(partition, i);
426  state_map[i] = siter.Value(); // First state in partition.
427  }
428  // Relabels destination states.
429  for (StateId c = 0; c < partition.NumClasses(); ++c) {
430  for (PartitionIterator<StateId> siter(partition, c); !siter.Done();
431  siter.Next()) {
432  const auto s = siter.Value();
433  for (MutableArcIterator<MutableFst<Arc>> aiter(fst, s); !aiter.Done();
434  aiter.Next()) {
435  auto arc = aiter.Value();
436  arc.nextstate = state_map[partition.ClassId(arc.nextstate)];
437  if (s == state_map[c]) { // For the first state, just sets destination.
438  aiter.SetValue(arc);
439  } else {
440  fst->AddArc(state_map[c], std::move(arc));
441  }
442  }
443  }
444  }
445  fst->SetStart(state_map[partition.ClassId(fst->Start())]);
446  Connect(fst);
447 }
448 
449 template <class Arc>
451  bool allow_acyclic_minimization = true) {
452  if (!(fst->Properties(kAcceptor | kUnweighted, true) ==
453  (kAcceptor | kUnweighted))) {
454  FSTERROR() << "FST is not an unweighted acceptor";
455  fst->SetProperties(kError, kError);
456  return;
457  }
458  // Connects FST before minimization, handles disconnected states.
459  Connect(fst);
460  if (fst->NumStates() == 0) return;
461  if (allow_acyclic_minimization && fst->Properties(kAcyclic, true)) {
462  // Acyclic minimization (Revuz).
463  VLOG(2) << "Acyclic minimization";
464  ArcSort(fst, ILabelCompare<Arc>());
465  AcyclicMinimizer<Arc> minimizer(*fst);
466  MergeStates(minimizer.GetPartition(), fst);
467  } else {
468  // Either the FST has cycles, or it's generated from non-deterministic input
469  // (which the Revuz algorithm can't handle), so use the cyclic minimization
470  // algorithm of Hopcroft.
471  VLOG(2) << "Cyclic minimization";
473  MergeStates(minimizer.GetPartition(), fst);
474  }
475  // Merges in appropriate semiring
476  ArcUniqueMapper<Arc> mapper(*fst);
477  StateMap(fst, mapper);
478 }
479 
480 } // namespace internal
481 
482 // In place minimization of deterministic weighted automata and transducers,
483 // and also non-deterministic ones if they use an idempotent semiring.
484 // For transducers, if the 'sfst' argument is not null, the algorithm
485 // produces a compact factorization of the minimal transducer.
486 //
487 // In the acyclic deterministic case, we use an algorithm from Revuz that is
488 // linear in the number of arcs (edges) in the machine.
489 //
490 // In the cyclic or non-deterministic case, we use the classical Hopcroft
491 // minimization (which was presented for the deterministic case but which
492 // also works for non-deterministic FSTs); this has complexity O(e log v).
493 //
494 template <class Arc>
496  float delta = kShortestDelta, bool allow_nondet = false) {
497  using Weight = typename Arc::Weight;
498  const auto props = fst->Properties(
500  bool allow_acyclic_minimization;
501  if (props & kIDeterministic) {
502  allow_acyclic_minimization = true;
503  } else {
504  // Our approach to minimization of non-deterministic FSTs will only work in
505  // idempotent semirings---for non-deterministic inputs, a state could have
506  // multiple transitions to states that will get merged, and we'd have to
507  // sum their weights. The algorithm doesn't handle that.
508  if (!(Weight::Properties() & kIdempotent)) {
509  fst->SetProperties(kError, kError);
510  FSTERROR() << "Cannot minimize a non-deterministic FST over a "
511  "non-idempotent semiring";
512  return;
513  } else if (!allow_nondet) {
514  fst->SetProperties(kError, kError);
515  FSTERROR() << "Refusing to minimize a non-deterministic FST with "
516  << "allow_nondet = false";
517  return;
518  }
519  // The Revuz algorithm won't work for nondeterministic inputs, so if the
520  // input is nondeterministic, we'll have to pass a bool saying not to use
521  // that algorithm. We check at this level rather than in AcceptorMinimize(),
522  // because it's possible that the FST at this level could be deterministic,
523  // but a harmless type of non-determinism could be introduced by Encode()
524  // (thanks to kEncodeWeights, if the FST has epsilons and has a final
525  // weight with weights equal to some epsilon arc.)
526  allow_acyclic_minimization = false;
527  }
528  if (!(props & kAcceptor)) { // Weighted transducer.
531  fst->DeleteStates();
532  gfst.SetProperties(kAcceptor, kAcceptor);
533  Push(&gfst, REWEIGHT_TO_INITIAL, delta);
536  kEncodeLabels | kEncodeWeights, ENCODE);
537  Encode(&gfst, &encoder);
538  internal::AcceptorMinimize(&gfst, allow_acyclic_minimization);
539  Decode(&gfst, encoder);
540  if (!sfst) {
543  fwfst(gfst);
544  std::unique_ptr<SymbolTable> osyms(
545  fst->OutputSymbols() ? fst->OutputSymbols()->Copy() : nullptr);
547  fst->SetOutputSymbols(osyms.get());
548  } else {
549  sfst->SetOutputSymbols(fst->OutputSymbols());
551  ArcMap(gfst, fst, &mapper);
552  fst->SetOutputSymbols(sfst->InputSymbols());
553  }
554  } else if (props & kWeighted) { // Weighted acceptor.
555  Push(fst, REWEIGHT_TO_INITIAL, delta);
556  ArcMap(fst, QuantizeMapper<Arc>(delta));
557  EncodeMapper<Arc> encoder(kEncodeLabels | kEncodeWeights, ENCODE);
558  Encode(fst, &encoder);
559  internal::AcceptorMinimize(fst, allow_acyclic_minimization);
560  Decode(fst, encoder);
561  } else { // Unweighted acceptor.
562  internal::AcceptorMinimize(fst, allow_acyclic_minimization);
563  }
564 }
565 
566 } // namespace fst
567 
568 #endif // FST_MINIMIZE_H_
typename Arc::StateId ClassId
Definition: minimize.h:299
void ArcMap(MutableFst< A > *fst, C *mapper)
Definition: arc-map.h:94
typename Arc::Weight Weight
Definition: minimize.h:42
typename Arc::StateId StateId
Definition: minimize.h:41
typename Arc::Label Label
Definition: minimize.h:101
typename Arc::StateId StateId
Definition: minimize.h:298
constexpr int kNoLabel
Definition: fst.h:179
void SetProperties(uint64 props, uint64 mask) override
Definition: mutable-fst.h:290
AcyclicMinimizer(const ExpandedFst< Arc > &fst)
Definition: minimize.h:302
void Encode(MutableFst< Arc > *fst, EncodeMapper< Arc > *mapper)
Definition: encode.h:419
bool operator()(const StateId x, const StateId y) const
Definition: minimize.h:48
virtual size_t NumArcs(StateId) const =0
typename Arc::Weight Weight
Definition: minimize.h:104
virtual void AddArc(StateId, const Arc &arc)=0
virtual SymbolTable * Copy() const
Definition: symbol-table.h:266
const Partition< StateId > & GetPartition() const
Definition: minimize.h:112
void DfsVisit(const FST &fst, Visitor *visitor, ArcFilter filter, bool access_only=false)
Definition: dfs-visit.h:94
virtual Weight Final(StateId) const =0
virtual void SetStart(StateId)=0
void Connect(MutableFst< Arc > *fst)
Definition: connect.h:268
void MergeStates(const Partition< typename Arc::StateId > &partition, MutableFst< Arc > *fst)
Definition: minimize.h:420
constexpr int kNoStateId
Definition: fst.h:180
const T NumClasses() const
Definition: partition.h:179
void Reverse(const Fst< Arc > &ifst, const std::vector< std::pair< typename Arc::Label, typename Arc::Label >> &parens, std::vector< typename Arc::Label > *assignments, MutableFst< RevArc > *ofst)
Definition: reverse.h:20
virtual uint64 Properties(uint64 mask, bool test) const =0
#define FSTERROR()
Definition: util.h:35
void AcceptorMinimize(MutableFst< Arc > *fst, bool allow_acyclic_minimization=true)
Definition: minimize.h:450
constexpr uint64 kUnweighted
Definition: properties.h:87
const SymbolTable * OutputSymbols() const override=0
void ArcSort(MutableFst< Arc > *fst, Compare comp)
Definition: arcsort.h:87
constexpr uint64 kIdempotent
Definition: weight.h:123
constexpr uint64 kIDeterministic
Definition: properties.h:50
const Partition< StateId > & GetPartition()
Definition: minimize.h:307
#define VLOG(level)
Definition: log.h:49
virtual StateId Start() const =0
constexpr float kShortestDelta
constexpr uint64 kAcceptor
Definition: properties.h:45
void StateMap(MutableFst< A > *fst, C *mapper)
Definition: state-map.h:79
const T ClassId(T element_id) const
Definition: partition.h:175
StateComparator(const Fst< Arc > &fst, const Partition< StateId > &partition)
Definition: minimize.h:44
void Minimize(MutableFst< Arc > *fst, MutableFst< Arc > *sfst=nullptr, float delta=kShortestDelta, bool allow_nondet=false)
Definition: minimize.h:495
CyclicMinimizer(const ExpandedFst< Arc > &fst)
Definition: minimize.h:107
constexpr uint64 kAcyclic
Definition: properties.h:92
constexpr uint64 kWeighted
Definition: properties.h:85
constexpr uint64 kError
Definition: properties.h:33
typename Arc::Label Label
Definition: minimize.h:297
virtual void DeleteStates(const std::vector< StateId > &)=0
typename Arc::Weight Weight
Definition: minimize.h:300
virtual void SetOutputSymbols(const SymbolTable *osyms)=0
virtual StateId NumStates() const =0
void Push(MutableFst< Arc > *fst, ReweightType type, float delta=kDelta, bool remove_total_weight=false)
Definition: push.h:77
typename Arc::StateId ClassId
Definition: minimize.h:103
typename Arc::StateId StateId
Definition: minimize.h:102
void Decode(MutableFst< Arc > *fst, const EncodeMapper< Arc > &mapper)
Definition: encode.h:426
virtual void SetProperties(uint64 props, uint64 mask)=0