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