FST  openfst-1.7.2
OpenFst Library
disambiguate.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 disambiguate an FST.
5 
6 #ifndef FST_DISAMBIGUATE_H_
7 #define FST_DISAMBIGUATE_H_
8 
9 #include <list>
10 #include <map>
11 #include <set>
12 #include <utility>
13 #include <vector>
14 
15 #include <fst/arcsort.h>
16 #include <fst/compose.h>
17 #include <fst/connect.h>
18 #include <fst/determinize.h>
19 #include <fst/dfs-visit.h>
20 #include <fst/project.h>
21 #include <fst/prune.h>
22 #include <fst/state-map.h>
23 #include <fst/state-table.h>
24 #include <fst/union-find.h>
25 #include <fst/verify.h>
26 
27 
28 namespace fst {
29 
30 template <class Arc>
32  using Label = typename Arc::Label;
33  using StateId = typename Arc::StateId;
34  using Weight = typename Arc::Weight;
35 
36  explicit DisambiguateOptions(float delta = kDelta,
37  Weight weight = Weight::Zero(),
38  StateId n = kNoStateId, Label label = 0)
39  : DeterminizeOptions<Arc>(delta, std::move(weight), n, label,
41 };
42 
43 namespace internal {
44 
45 // A determinization filter based on a subset element relation. The relation is
46 // assumed to be reflexive and symmetric.
47 template <class Arc, class Relation>
49  public:
50  using Label = typename Arc::Label;
51  using StateId = typename Arc::StateId;
52  using Weight = typename Arc::Weight;
53 
56  using Subset = typename StateTuple::Subset;
57  using Element = typename StateTuple::Element;
58  using LabelMap = std::multimap<Label, DeterminizeArc<StateTuple>>;
59 
60  // This is needed (e.g.) to go into the gallic domain for transducers; there
61  // is no need to rebind the relation since its use here only depends on the
62  // state IDs.
63  template <class A>
64  struct rebind {
66  };
67 
69  : fst_(fst.Copy()), r_(new Relation()), s_(kNoStateId), head_(nullptr) {}
70 
71  // Ownership of the relation is given to this class.
72  RelationDeterminizeFilter(const Fst<Arc> &fst, Relation *r)
73  : fst_(fst.Copy()), r_(r), s_(kNoStateId), head_(0) {}
74 
75  // Ownership of the relation is given to this class.
76  RelationDeterminizeFilter(const Fst<Arc> &fst, Relation *r,
77  std::vector<StateId> *head)
78  : fst_(fst.Copy()), r_(r), s_(kNoStateId), head_(head) {}
79 
80  // This is needed, e.g., to go into the gallic domain for transducers.
81  // Ownership of the templated filter argument is given to this class.
82  template <class Filter>
83  RelationDeterminizeFilter(const Fst<Arc> &fst, Filter *filter)
84  : fst_(fst.Copy()),
85  r_(new Relation(filter->GetRelation())),
86  s_(kNoStateId),
87  head_(filter->GetHeadStates()) {
88  delete filter;
89  }
90 
91  // Copy constructor; the FST can be passed if it has been deep-copied.
93  const Fst<Arc> *fst = nullptr)
94  : fst_(fst ? fst->Copy() : filter.fst_->Copy()),
95  r_(new Relation(*filter.r_)),
96  s_(kNoStateId),
97  head_() {}
98 
99  FilterState Start() const { return FilterState(fst_->Start()); }
100 
101  void SetState(StateId s, const StateTuple &tuple) {
102  if (s_ != s) {
103  s_ = s;
104  tuple_ = &tuple;
105  const auto head = tuple.filter_state.GetState();
106  is_final_ = fst_->Final(head) != Weight::Zero();
107  if (head_) {
108  if (head_->size() <= s) head_->resize(s + 1, kNoStateId);
109  (*head_)[s] = head;
110  }
111  }
112  }
113 
114  // Filters transition, possibly modifying label map. Returns true if arc is
115  // added to label map.
116  bool FilterArc(const Arc &arc, const Element &src_element,
117  const Element &dest_element, LabelMap *label_map) const;
118 
119  // Filters super-final transition, returning new final weight.
120  Weight FilterFinal(const Weight final_weight, const Element &element) const {
121  return is_final_ ? final_weight : Weight::Zero();
122  }
123 
124  static uint64 Properties(uint64 props) {
125  return props & ~(kIDeterministic | kODeterministic);
126  }
127 
128  const Relation &GetRelation() { return *r_; }
129 
130  std::vector<StateId> *GetHeadStates() { return head_; }
131 
132  private:
133  // Pairs arc labels with state tuples with possible heads and empty subsets.
134  void InitLabelMap(LabelMap *label_map) const;
135 
136  std::unique_ptr<Fst<Arc>> fst_; // Input FST.
137  std::unique_ptr<Relation> r_; // Relation compatible with inv. trans. fnc.
138  StateId s_; // Current state.
139  const StateTuple *tuple_; // Current tuple.
140  bool is_final_; // Is the current head state final?
141  std::vector<StateId> *head_; // Head state for a given state,
142  // owned by the Disambiguator.
143 };
144 
145 template <class Arc, class Relation>
147  const Arc &arc, const Element &src_element, const Element &dest_element,
148  LabelMap *label_map) const {
149  bool added = false;
150  if (label_map->empty()) InitLabelMap(label_map);
151  // Adds element to state tuple if element state is related to tuple head.
152  for (auto liter = label_map->lower_bound(arc.ilabel);
153  liter != label_map->end() && liter->first == arc.ilabel; ++liter) {
154  auto *dest_tuple = liter->second.dest_tuple;
155  const auto dest_head = dest_tuple->filter_state.GetState();
156  if ((*r_)(dest_element.state_id, dest_head)) {
157  dest_tuple->subset.push_front(dest_element);
158  added = true;
159  }
160  }
161  return added;
162 }
163 
164 template <class Arc, class Relation>
166  LabelMap *label_map) const {
167  const auto src_head = tuple_->filter_state.GetState();
168  Label label = kNoLabel;
169  StateId nextstate = kNoStateId;
170  for (ArcIterator<Fst<Arc>> aiter(*fst_, src_head); !aiter.Done();
171  aiter.Next()) {
172  const auto &arc = aiter.Value();
173  // Continues if multiarc.
174  if (arc.ilabel == label && arc.nextstate == nextstate) continue;
175  DeterminizeArc<StateTuple> det_arc(arc);
176  det_arc.dest_tuple->filter_state = FilterState(arc.nextstate);
177  label_map->insert(std::make_pair(arc.ilabel, det_arc));
178  label = arc.ilabel;
179  nextstate = arc.nextstate;
180  }
181 }
182 
183 // Helper class to disambiguate an FST via Disambiguate().
184 template <class Arc>
186  public:
187  using Label = typename Arc::Label;
188  using StateId = typename Arc::StateId;
189  using Weight = typename Arc::Weight;
190 
191  // IDs arcs with state ID and arc position. Arc position -1 indicates final
192  // (super-final transition).
193  using ArcId = std::pair<StateId, ssize_t>;
194 
195  Disambiguator() : error_(false) {}
196 
198  const Fst<Arc> &ifst, MutableFst<Arc> *ofst,
200  VectorFst<Arc> sfst(ifst);
201  Connect(&sfst);
202  ArcSort(&sfst, ArcCompare());
203  PreDisambiguate(sfst, ofst, opts);
204  ArcSort(ofst, ArcCompare());
205  FindAmbiguities(*ofst);
206  RemoveSplits(ofst);
207  MarkAmbiguities();
208  RemoveAmbiguities(ofst);
209  if (error_) ofst->SetProperties(kError, kError);
210  }
211 
212  private:
213  // Comparison functor for comparing input labels and next states of arcs. This
214  // sort order facilitates the predisambiguation.
215  class ArcCompare {
216  public:
217  bool operator()(const Arc &arc1, const Arc &arc2) const {
218  return arc1.ilabel < arc2.ilabel ||
219  (arc1.ilabel == arc2.ilabel && arc1.nextstate < arc2.nextstate);
220  }
221 
222  uint64 Properties(uint64 props) const {
223  return (props & kArcSortProperties) | kILabelSorted |
224  (props & kAcceptor ? kOLabelSorted : 0);
225  }
226  };
227 
228  // Comparison functor for comparing transitions represented by their arc ID.
229  // This sort order facilitates ambiguity detection.
230  class ArcIdCompare {
231  public:
232  explicit ArcIdCompare(const std::vector<StateId> &head) : head_(head) {}
233 
234  bool operator()(const ArcId &a1, const ArcId &a2) const {
235  // Sort first by source head state...
236  const auto src1 = a1.first;
237  const auto src2 = a2.first;
238  const auto head1 = head_[src1];
239  const auto head2 = head_[src2];
240  if (head1 < head2) return true;
241  if (head2 < head1) return false;
242  // ...then by source state...
243  if (src1 < src2) return true;
244  if (src2 < src1) return false;
245  // ...then by position.
246  return a1.second < a2.second;
247  }
248 
249  private:
250  const std::vector<StateId> &head_;
251  };
252 
253  // A relation that determines if two states share a common future.
254  class CommonFuture {
255  public:
257  using StateTuple = typename StateTable::StateTuple;
258 
259  // Needed for compilation with DeterminizeRelationFilter.
260  CommonFuture() {
261  FSTERROR() << "Disambiguate::CommonFuture: FST not provided";
262  }
263 
264  explicit CommonFuture(const Fst<Arc> &ifst) {
265  using M = Matcher<Fst<Arc>>;
267  // Ensures composition is between acceptors.
268  const bool trans = ifst.Properties(kNotAcceptor, true);
269  const auto *fsa =
270  trans ? new ProjectFst<Arc>(ifst, PROJECT_INPUT) : &ifst;
271  opts.state_table = new StateTable(*fsa, *fsa);
272  const ComposeFst<Arc> cfst(*fsa, *fsa, opts);
273  std::vector<bool> coaccess;
274  uint64 props = 0;
275  SccVisitor<Arc> scc_visitor(nullptr, nullptr, &coaccess, &props);
276  DfsVisit(cfst, &scc_visitor);
277  for (StateId s = 0; s < coaccess.size(); ++s) {
278  if (coaccess[s]) {
279  related_.insert(opts.state_table->Tuple(s).StatePair());
280  }
281  }
282  if (trans) delete fsa;
283  }
284 
285  bool operator()(const StateId s1, StateId s2) const {
286  return related_.count(std::make_pair(s1, s2)) > 0;
287  }
288 
289  private:
290  // States s1 and s2 resp. are in this relation iff they there is a
291  // path from s1 to a final state that has the same label as some
292  // path from s2 to a final state.
293  std::set<std::pair<StateId, StateId>> related_;
294  };
295 
296  using ArcIdMap = std::multimap<ArcId, ArcId, ArcIdCompare>;
297 
298  // Inserts candidate into the arc ID map.
299  inline void InsertCandidate(StateId s1, StateId s2, const ArcId &a1,
300  const ArcId &a2) {
301  candidates_->insert(head_[s1] > head_[s2] ? std::make_pair(a1, a2)
302  : std::make_pair(a2, a1));
303  }
304 
305  // Returns the arc corresponding to ArcId a.
306  static Arc GetArc(const Fst<Arc> &fst, ArcId aid) {
307  if (aid.second == -1) { // Returns super-final transition.
308  return Arc(kNoLabel, kNoLabel, fst.Final(aid.first), kNoStateId);
309  } else {
310  ArcIterator<Fst<Arc>> aiter(fst, aid.first);
311  aiter.Seek(aid.second);
312  return aiter.Value();
313  }
314  }
315 
316  // Outputs an equivalent FST whose states are subsets of states that have a
317  // future path in common.
318  void PreDisambiguate(const ExpandedFst<Arc> &ifst, MutableFst<Arc> *ofst,
319  const DisambiguateOptions<Arc> &opts);
320 
321  // Finds transitions that are ambiguous candidates in the result of
322  // PreDisambiguate.
323  void FindAmbiguities(const ExpandedFst<Arc> &fst);
324 
325  // Finds transition pairs that are ambiguous candidates from two specified
326  // source states.
327  void FindAmbiguousPairs(const ExpandedFst<Arc> &fst, StateId s1, StateId s2);
328 
329  // Marks ambiguous transitions to be removed.
330  void MarkAmbiguities();
331 
332  // Deletes spurious ambiguous transitions (due to quantization).
333  void RemoveSplits(MutableFst<Arc> *ofst);
334 
335  // Deletes actual ambiguous transitions.
336  void RemoveAmbiguities(MutableFst<Arc> *ofst);
337 
338  // States s1 and s2 are in this relation iff there is a path from the initial
339  // state to s1 that has the same label as some path from the initial state to
340  // s2. We store only state pairs s1, s2 such that s1 <= s2.
341  std::set<std::pair<StateId, StateId>> coreachable_;
342 
343  // Queue of disambiguation-related states to be processed. We store only
344  // state pairs s1, s2 such that s1 <= s2.
345  std::list<std::pair<StateId, StateId>> queue_;
346 
347  // Head state in the pre-disambiguation for a given state.
348  std::vector<StateId> head_;
349 
350  // Maps from a candidate ambiguous arc A to each ambiguous candidate arc B
351  // with the same label and destination state as A, whose source state s' is
352  // coreachable with the source state s of A, and for which head(s') < head(s).
353  std::unique_ptr<ArcIdMap> candidates_;
354 
355  // Set of ambiguous transitions to be removed.
356  std::set<ArcId> ambiguous_;
357 
358  // States to merge due to quantization issues.
359  std::unique_ptr<UnionFind<StateId>> merge_;
360  // Marks error condition.
361  bool error_;
362 
363  Disambiguator(const Disambiguator &) = delete;
364  Disambiguator &operator=(const Disambiguator &) = delete;
365 };
366 
367 template <class Arc>
369  MutableFst<Arc> *ofst,
370  const DisambiguateOptions<Arc> &opts) {
371  using CommonDivisor = DefaultCommonDivisor<Weight>;
373  // Subset elements with states s1 and s2 (resp.) are in this relation iff they
374  // there is a path from s1 to a final state that has the same label as some
375  // path from s2 to a final state.
376  auto *common_future = new CommonFuture(ifst);
378  nopts.delta = opts.delta;
380  nopts.filter = new Filter(ifst, common_future, &head_);
381  // The filter takes ownership of 'common_future', and determinization takes
382  // ownership of the filter itself.
383  nopts.gc_limit = 0; // Cache only the last state for fastest copy.
384  if (opts.weight_threshold != Weight::Zero() ||
385  opts.state_threshold != kNoStateId) {
386  /* TODO(riley): fails regression test; understand why
387  if (ifst.Properties(kAcceptor, true)) {
388  std::vector<Weight> idistance, odistance;
389  ShortestDistance(ifst, &idistance, true);
390  DeterminizeFst<Arc> dfst(ifst, &idistance, &odistance, nopts);
391  PruneOptions< Arc, AnyArcFilter<Arc>> popts(opts.weight_threshold,
392  opts.state_threshold,
393  AnyArcFilter<Arc>(),
394  &odistance);
395  Prune(dfst, ofst, popts);
396  } else */ {
397  *ofst = DeterminizeFst<Arc>(ifst, nopts);
398  Prune(ofst, opts.weight_threshold, opts.state_threshold);
399  }
400  } else {
401  *ofst = DeterminizeFst<Arc>(ifst, nopts);
402  }
403  head_.resize(ofst->NumStates(), kNoStateId);
404 }
405 
406 template <class Arc>
408  if (fst.Start() == kNoStateId) return;
409  candidates_.reset(new ArcIdMap(ArcIdCompare(head_)));
410  const auto start_pr = std::make_pair(fst.Start(), fst.Start());
411  coreachable_.insert(start_pr);
412  queue_.push_back(start_pr);
413  while (!queue_.empty()) {
414  const auto &pr = queue_.front();
415  const auto s1 = pr.first;
416  const auto s2 = pr.second;
417  queue_.pop_front();
418  FindAmbiguousPairs(fst, s1, s2);
419  }
420 }
421 
422 template <class Arc>
424  StateId s1, StateId s2) {
425  if (fst.NumArcs(s2) > fst.NumArcs(s1)) FindAmbiguousPairs(fst, s2, s1);
426  SortedMatcher<Fst<Arc>> matcher(fst, MATCH_INPUT);
427  matcher.SetState(s2);
428  for (ArcIterator<Fst<Arc>> aiter(fst, s1); !aiter.Done(); aiter.Next()) {
429  const auto &arc1 = aiter.Value();
430  const ArcId a1(s1, aiter.Position());
431  if (matcher.Find(arc1.ilabel)) {
432  for (; !matcher.Done(); matcher.Next()) {
433  const auto &arc2 = matcher.Value();
434  // Continues on implicit epsilon match.
435  if (arc2.ilabel == kNoLabel) continue;
436  const ArcId a2(s2, matcher.Position());
437  // Actual transition is ambiguous.
438  if (s1 != s2 && arc1.nextstate == arc2.nextstate) {
439  InsertCandidate(s1, s2, a1, a2);
440  }
441  const auto spr = arc1.nextstate <= arc2.nextstate
442  ? std::make_pair(arc1.nextstate, arc2.nextstate)
443  : std::make_pair(arc2.nextstate, arc1.nextstate);
444  // Not already marked as coreachable?
445  if (coreachable_.insert(spr).second) {
446  // Only possible if state split by quantization issues.
447  if (spr.first != spr.second &&
448  head_[spr.first] == head_[spr.second]) {
449  if (!merge_) {
450  merge_.reset(new UnionFind<StateId>(fst.NumStates(), kNoStateId));
451  merge_->MakeAllSet(fst.NumStates());
452  }
453  merge_->Union(spr.first, spr.second);
454  } else {
455  queue_.push_back(spr);
456  }
457  }
458  }
459  }
460  }
461  // Super-final transition is ambiguous.
462  if (s1 != s2 && fst.Final(s1) != Weight::Zero() &&
463  fst.Final(s2) != Weight::Zero()) {
464  const ArcId a1(s1, -1);
465  const ArcId a2(s2, -1);
466  InsertCandidate(s1, s2, a1, a2);
467  }
468 }
469 
470 template <class Arc>
472  if (!candidates_) return;
473  for (auto it = candidates_->begin(); it != candidates_->end(); ++it) {
474  const auto a = it->first;
475  const auto b = it->second;
476  // If b is not to be removed, then a is.
477  if (ambiguous_.count(b) == 0) ambiguous_.insert(a);
478  }
479  coreachable_.clear();
480  candidates_.reset();
481 }
482 
483 template <class Arc>
485  if (!merge_) return;
486  // Merges split states to remove spurious ambiguities.
487  for (StateIterator<MutableFst<Arc>> siter(*ofst); !siter.Done();
488  siter.Next()) {
489  for (MutableArcIterator<MutableFst<Arc>> aiter(ofst, siter.Value());
490  !aiter.Done(); aiter.Next()) {
491  auto arc = aiter.Value();
492  const auto nextstate = merge_->FindSet(arc.nextstate);
493  if (nextstate != arc.nextstate) {
494  arc.nextstate = nextstate;
495  aiter.SetValue(arc);
496  }
497  }
498  }
499  // Repeats search for actual ambiguities on modified FST.
500  coreachable_.clear();
501  merge_.reset();
502  candidates_.reset();
503  FindAmbiguities(*ofst);
504  if (merge_) { // Shouldn't get here; sanity test.
505  FSTERROR() << "Disambiguate: Unable to remove spurious ambiguities";
506  error_ = true;
507  return;
508  }
509 }
510 
511 template <class Arc>
513  if (ambiguous_.empty()) return;
514  // Adds dead state to redirect ambiguous transitions to be removed.
515  const auto dead = ofst->AddState();
516  for (auto it = ambiguous_.begin(); it != ambiguous_.end(); ++it) {
517  const auto pos = it->second;
518  if (pos >= 0) { // Actual transition.
519  MutableArcIterator<MutableFst<Arc>> aiter(ofst, it->first);
520  aiter.Seek(pos);
521  auto arc = aiter.Value();
522  arc.nextstate = dead;
523  aiter.SetValue(arc);
524  } else { // Super-final transition.
525  ofst->SetFinal(it->first, Weight::Zero());
526  }
527  }
528  Connect(ofst);
529  ambiguous_.clear();
530 }
531 
532 } // namespace internal
533 
534 // Disambiguates a weighted FST. This version writes the disambiguated FST to an
535 // output MutableFst. The result will be an equivalent FST that has the
536 // property that there are not two distinct paths from the initial state to a
537 // final state with the same input labeling.
538 //
539 // The weights must be (weakly) left divisible (valid for Tropical and
540 // LogWeight).
541 //
542 // Complexity:
543 //
544 // Disambiguable: exponential (polynomial in the size of the output).
545 // Non-disambiguable: does not terminate.
546 //
547 // The disambiguable transducers include all automata and functional transducers
548 // that are unweighted or that are acyclic or that are unambiguous.
549 //
550 // For more information, see:
551 //
552 // Mohri, M. and Riley, M. 2015. On the disambiguation of weighted automata.
553 // In CIAA, pages 263-278.
554 template <class Arc>
556  const Fst<Arc> &ifst, MutableFst<Arc> *ofst,
558  internal::Disambiguator<Arc> disambiguator;
559  disambiguator.Disambiguate(ifst, ofst, opts);
560 }
561 
562 } // namespace fst
563 
564 #endif // FST_DISAMBIGUATE_H_
void Next() final
Definition: matcher.h:295
void SetState(StateId s) final
Definition: matcher.h:234
constexpr int kNoLabel
Definition: fst.h:179
size_t Position() const
Definition: matcher.h:317
uint64_t uint64
Definition: types.h:32
RelationDeterminizeFilter(const Fst< Arc > &fst)
Definition: disambiguate.h:68
typename Arc::StateId StateId
Definition: disambiguate.h:188
virtual size_t NumArcs(StateId) const =0
RelationDeterminizeFilter(const RelationDeterminizeFilter &filter, const Fst< Arc > *fst=nullptr)
Definition: disambiguate.h:92
const Arc & Value() const final
Definition: matcher.h:289
std::multimap< Label, DeterminizeArc< StateTuple >> LabelMap
Definition: disambiguate.h:58
constexpr uint64 kILabelSorted
Definition: properties.h:75
typename Arc::Weight Weight
Definition: disambiguate.h:189
void DfsVisit(const FST &fst, Visitor *visitor, ArcFilter filter, bool access_only=false)
Definition: dfs-visit.h:94
virtual Weight Final(StateId) const =0
typename Arc::Label Label
Definition: disambiguate.h:187
void Connect(MutableFst< Arc > *fst)
Definition: connect.h:268
void SetValue(const Arc &arc)
Definition: mutable-fst.h:223
void SetState(StateId s, const StateTuple &tuple)
Definition: disambiguate.h:101
constexpr int kNoStateId
Definition: fst.h:180
const Arc & Value() const
Definition: fst.h:503
const Arc & Value() const
Definition: mutable-fst.h:213
virtual uint64 Properties(uint64 mask, bool test) const =0
#define FSTERROR()
Definition: util.h:35
typename StateTuple::Subset Subset
Definition: disambiguate.h:56
bool Done() const final
Definition: matcher.h:279
std::pair< StateId, ssize_t > ArcId
Definition: disambiguate.h:193
bool Find(Label match_label) final
Definition: matcher.h:248
virtual void SetFinal(StateId, Weight)=0
RelationDeterminizeFilter(const Fst< Arc > &fst, Filter *filter)
Definition: disambiguate.h:83
void Seek(size_t a)
Definition: mutable-fst.h:221
constexpr uint64 kArcSortProperties
Definition: properties.h:226
void Seek(size_t a)
Definition: fst.h:523
void ArcSort(MutableFst< Arc > *fst, Compare comp)
Definition: arcsort.h:87
typename Arc::Weight Weight
Definition: determinize.h:1020
std::forward_list< Element > Subset
Definition: determinize.h:149
constexpr uint64 kOLabelSorted
Definition: properties.h:80
constexpr uint64 kIDeterministic
Definition: properties.h:50
virtual StateId Start() const =0
RelationDeterminizeFilter(const Fst< Arc > &fst, Relation *r, std::vector< StateId > *head)
Definition: disambiguate.h:76
typename Arc::Label Label
Definition: determinize.h:1018
constexpr uint64 kAcceptor
Definition: properties.h:45
void Prune(MutableFst< Arc > *fst, const PruneOptions< Arc, ArcFilter > &opts=PruneOptions< Arc, ArcFilter >())
Definition: prune.h:99
Weight FilterFinal(const Weight final_weight, const Element &element) const
Definition: disambiguate.h:120
typename StateTuple::Element Element
Definition: disambiguate.h:57
typename Arc::StateId StateId
Definition: determinize.h:1019
RelationDeterminizeFilter(const Fst< Arc > &fst, Relation *r)
Definition: disambiguate.h:72
constexpr uint64 kNotAcceptor
Definition: properties.h:47
std::vector< StateId > * GetHeadStates()
Definition: disambiguate.h:130
static uint64 Properties(uint64 props)
Definition: disambiguate.h:124
constexpr uint64 kError
Definition: properties.h:33
virtual StateId AddState()=0
DisambiguateOptions(float delta=kDelta, Weight weight=Weight::Zero(), StateId n=kNoStateId, Label label=0)
Definition: disambiguate.h:36
virtual StateId NumStates() const =0
constexpr uint64 kODeterministic
Definition: properties.h:55
size_t gc_limit
Definition: cache.h:29
constexpr float kDelta
Definition: weight.h:109
void Disambiguate(const Fst< Arc > &ifst, MutableFst< Arc > *ofst, const DisambiguateOptions< Arc > &opts=DisambiguateOptions< Arc >())
Definition: disambiguate.h:555
void Disambiguate(const Fst< Arc > &ifst, MutableFst< Arc > *ofst, const DisambiguateOptions< Arc > &opts=DisambiguateOptions< Arc >())
Definition: disambiguate.h:197
virtual void SetProperties(uint64 props, uint64 mask)=0
StateTable * state_table
Definition: compose.h:43