FST  openfst-1.7.1
OpenFst Library
determinize.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 determinize an FST.
5 
6 #ifndef FST_DETERMINIZE_H_
7 #define FST_DETERMINIZE_H_
8 
9 #include <algorithm>
10 #include <climits>
11 #include <forward_list>
12 #include <map>
13 #include <string>
14 #include <utility>
15 #include <vector>
16 
17 #include <fst/log.h>
18 
19 #include <fst/arc-map.h>
20 #include <fst/bi-table.h>
21 #include <fst/cache.h>
22 #include <fst/factor-weight.h>
23 #include <fst/filter-state.h>
24 #include <fst/prune.h>
25 #include <fst/test-properties.h>
26 
27 
28 namespace fst {
29 
30 // Common divisors are used in determinization to compute transition weights.
31 // In the simplest case, it is the same as semiring Plus, but other choices
32 // permit more efficient determinization when the output contains strings.
33 
34 // The default common divisor uses the semiring Plus.
35 template <class W>
37  public:
38  using Weight = W;
39 
40  Weight operator()(const Weight &w1, const Weight &w2) const {
41  return Plus(w1, w2);
42  }
43 };
44 
45 // The label common divisor for a (left) string semiring selects a single
46 // letter common prefix or the empty string. This is used in the
47 // determinization of output strings so that at most a single letter will
48 // appear in the output of a transtion.
49 template <typename Label, StringType S>
51  public:
53 
54  Weight operator()(const Weight &w1, const Weight &w2) const {
55  typename Weight::Iterator iter1(w1);
56  typename Weight::Iterator iter2(w2);
58  FSTERROR() << "LabelCommonDivisor: Weight needs to be left semiring";
59  return Weight::NoWeight();
60  } else if (w1.Size() == 0 || w2.Size() == 0) {
61  return Weight::One();
62  } else if (w1 == Weight::Zero()) {
63  return Weight(iter2.Value());
64  } else if (w2 == Weight::Zero()) {
65  return Weight(iter1.Value());
66  } else if (iter1.Value() == iter2.Value()) {
67  return Weight(iter1.Value());
68  } else {
69  return Weight::One();
70  }
71  }
72 };
73 
74 // The gallic common divisor uses the label common divisor on the string
75 // component and the common divisor on the weight component, which defaults to
76 // the default common divisor.
77 template <class Label, class W, GallicType G,
78  class CommonDivisor = DefaultCommonDivisor<W>>
80  public:
82 
83  Weight operator()(const Weight &w1, const Weight &w2) const {
84  return Weight(label_common_divisor_(w1.Value1(), w2.Value1()),
85  weight_common_divisor_(w1.Value2(), w2.Value2()));
86  }
87 
88  private:
90  CommonDivisor weight_common_divisor_;
91 };
92 
93 // Specialization for general GALLIC weight.
94 template <class Label, class W, class CommonDivisor>
95 class GallicCommonDivisor<Label, W, GALLIC, CommonDivisor> {
96  public:
99  using Iterator =
101 
102  Weight operator()(const Weight &w1, const Weight &w2) const {
103  auto weight = GRWeight::Zero();
104  for (Iterator iter(w1); !iter.Done(); iter.Next()) {
105  weight = common_divisor_(weight, iter.Value());
106  }
107  for (Iterator iter(w2); !iter.Done(); iter.Next()) {
108  weight = common_divisor_(weight, iter.Value());
109  }
110  return weight == GRWeight::Zero() ? Weight::Zero() : Weight(weight);
111  }
112 
113  private:
115 };
116 
117 namespace internal {
118 
119 // Represents an element in a subset
120 template <class Arc>
122  using StateId = typename Arc::StateId;
123  using Weight = typename Arc::Weight;
124 
126  : state_id(s), weight(std::move(weight)) {}
127 
128  inline bool operator==(const DeterminizeElement<Arc> &element) const {
129  return state_id == element.state_id && weight == element.weight;
130  }
131 
132  inline bool operator!=(const DeterminizeElement<Arc> &element) const {
133  return !(*this == element);
134  }
135 
136  inline bool operator<(const DeterminizeElement<Arc> &element) const {
137  return state_id < element.state_id;
138  }
139 
140  StateId state_id; // Input state ID.
141  Weight weight; // Residual weight.
142 };
143 
144 // Represents a weighted subset and determinization filter state
145 template <typename A, typename FilterState>
147  using Arc = A;
149  using Subset = std::forward_list<Element>;
150 
151  DeterminizeStateTuple() : filter_state(FilterState::NoState()) {}
152 
153  inline bool operator==(
154  const DeterminizeStateTuple<Arc, FilterState> &tuple) const {
155  return (tuple.filter_state == filter_state) && (tuple.subset == subset);
156  }
157 
158  inline bool operator!=(
159  const DeterminizeStateTuple<Arc, FilterState> &tuple) const {
160  return (tuple.filter_state != filter_state) || (tuple.subset != subset);
161  }
162 
164  FilterState filter_state;
165 };
166 
167 // Proto-transition for determinization.
168 template <class StateTuple>
170  using Arc = typename StateTuple::Arc;
171  using Label = typename Arc::Label;
172  using Weight = typename Arc::Weight;
173 
175  : label(kNoLabel), weight(Weight::Zero()), dest_tuple(nullptr) {}
176 
177  explicit DeterminizeArc(const Arc &arc)
178  : label(arc.ilabel), weight(Weight::Zero()), dest_tuple(new StateTuple) {}
179 
180  Label label; // Arc label.
181  Weight weight; // Arc weight.
182  StateTuple *dest_tuple; // Destination subset and filter state.
183 };
184 
185 } // namespace internal
186 
187 // Determinization filters are used to compute destination state tuples based
188 // on the source tuple, transition, and destination element or on similar
189 // super-final transition information. The filter operates on a map between a
190 // label and the corresponding destination state tuples. It must define the map
191 // type LabelMap. The default filter is used for weighted determinization.
192 // A determinize filter for implementing weighted determinization.
193 template <class Arc>
195  public:
196  using Label = typename Arc::Label;
197  using StateId = typename Arc::StateId;
198  using Weight = typename Arc::Weight;
199 
203  using LabelMap = std::map<Label, internal::DeterminizeArc<StateTuple>>;
204 
205  // This is needed e.g. to go into the gallic domain for transducers.
206  template <class A>
207  struct rebind {
209  };
210 
211  explicit DefaultDeterminizeFilter(const Fst<Arc> &fst) : fst_(fst.Copy()) {}
212 
213  // This is needed (e.g.) to go into the gallic domain for transducers.
214  // Ownership of the templated filter argument is given to this class.
215  template <class Filter>
216  DefaultDeterminizeFilter(const Fst<Arc> &fst, Filter *filter)
217  : fst_(fst.Copy()) {
218  delete filter;
219  }
220 
221  // Copy constructor; the FST can be passed if it has been deep-copied.
223  const Fst<Arc> *fst = nullptr)
224  : fst_(fst ? fst->Copy() : filter.fst_->Copy()) {}
225 
226  FilterState Start() const { return FilterState(0); }
227 
228  // Does no work.
229  void SetState(StateId s, const StateTuple &tuple) {}
230 
231  // Filters transition, possibly modifying label map. Returns true if arc is
232  // added to the label map.
233  bool FilterArc(const Arc &arc, const Element &src_element,
234  Element &&dest_element, LabelMap *label_map) const {
235  // Adds element to unique state tuple for arc label.
236  auto &det_arc = (*label_map)[arc.ilabel];
237  if (det_arc.label == kNoLabel) {
239  det_arc.dest_tuple->filter_state = FilterState(0);
240  }
241  det_arc.dest_tuple->subset.push_front(std::move(dest_element));
242  return true;
243  }
244 
245  // Filters super-final transition, returning new final weight.
246  Weight FilterFinal(Weight weight, const Element &element) { return weight; }
247 
248  static uint64 Properties(uint64 props) { return props; }
249 
250  private:
251  std::unique_ptr<Fst<Arc>> fst_;
252 };
253 
254 // Determinization state table interface:
255 //
256 // template <class Arc, class FilterState>
257 // class DeterminizeStateTable {
258 // public:
259 // using StateId = typename Arc::StateId;
260 // using StateTuple = internal::DeterminizeStateTuple<Arc, FilterState>;
261 //
262 // // Required sub-class. This is needed (e.g.) to go into the gallic domain.
263 // template <class B, class G>
264 // struct rebind {
265 // using Other = DeterminizeStateTable<B, G>;
266 // }
267 //
268 // // Required constuctor.
269 // DeterminizeStateTable();
270 //
271 // // Required copy constructor that does not copy state.
272 // DeterminizeStateTable(const DeterminizeStateTable<Arc, FilterState>
273 // &table);
274 //
275 // // Looks up state ID by state tuple; if it doesn't exist, then adds it.
276 // // FindState takes ownership of the state tuple argument so that it
277 // // doesn't have to copy it if it creates a new state.
278 // StateId FindState(StateTuple *tuple);
279 //
280 // // Looks up state tuple by ID.
281 // const StateTuple *Tuple(StateId id) const;
282 // };
283 
284 // The default determinization state table based on the compact hash bi-table.
285 template <class Arc, class FilterState>
287  public:
288  using Label = typename Arc::Label;
289  using StateId = typename Arc::StateId;
290  using Weight = typename Arc::Weight;
291 
293  using Element = typename StateTuple::Element;
294  using Subset = typename StateTuple::Subset;
295 
296  template <class B, class G>
297  struct rebind {
299  };
300 
301  explicit DefaultDeterminizeStateTable(size_t table_size = 0)
302  : table_size_(table_size), tuples_(table_size_) {}
303 
306  : table_size_(table.table_size_), tuples_(table_size_) {}
307 
309  for (StateId s = 0; s < tuples_.Size(); ++s) delete tuples_.FindEntry(s);
310  }
311 
312  // Finds the state corresponding to a state tuple. Only creates a new state if
313  // the tuple is not found. FindState takes ownership of the tuple argument so
314  // that it doesn't have to copy it if it creates a new state.
316  const StateId ns = tuples_.Size();
317  const auto s = tuples_.FindId(tuple);
318  if (s != ns) delete tuple; // Tuple found.
319  return s;
320  }
321 
322  const StateTuple *Tuple(StateId s) { return tuples_.FindEntry(s); }
323 
324  private:
325  // Comparison object for StateTuples.
326  class StateTupleEqual {
327  public:
328  bool operator()(const StateTuple *tuple1, const StateTuple *tuple2) const {
329  return *tuple1 == *tuple2;
330  }
331  };
332 
333  // Hash function for StateTuples.
334  class StateTupleKey {
335  public:
336  size_t operator()(const StateTuple *tuple) const {
337  size_t h = tuple->filter_state.Hash();
338  for (auto it = tuple->subset.begin(); it != tuple->subset.end(); ++it) {
339  const size_t h1 = it->state_id;
340  static constexpr auto lshift = 5;
341  static constexpr auto rshift = CHAR_BIT * sizeof(size_t) - 5;
342  h ^= h << 1 ^ h1 << lshift ^ h1 >> rshift ^ it->weight.Hash();
343  }
344  return h;
345  }
346  };
347 
348  size_t table_size_;
349  CompactHashBiTable<StateId, StateTuple *, StateTupleKey, StateTupleEqual,
350  HS_STL>
351  tuples_;
352 
353  DefaultDeterminizeStateTable &operator=(
354  const DefaultDeterminizeStateTable &) = delete;
355 };
356 
357 // Determinization type.
359  // Input transducer is known to be functional (or error).
360  DETERMINIZE_FUNCTIONAL, // Input transducer is functional (error if not).
361  // Input transducer is not known to be functional.
363  // Input transducer is not known to be functional but only keep the min of
364  // of ambiguous outputs.
366 };
367 
368 // Options for finite-state transducer determinization templated on the arc
369 // type, common divisor, the determinization filter and the state table.
370 // DeterminizeFst takes ownership of the determinization filter and state table,
371 // if provided.
372 template <class Arc,
373  class CommonDivisor = DefaultCommonDivisor<typename Arc::Weight>,
374  class Filter = DefaultDeterminizeFilter<Arc>,
375  class StateTable =
378  using Label = typename Arc::Label;
379 
380  float delta; // Quantization delta for subset weights.
381  Label subsequential_label; // Label used for residual final output
382  // when producing subsequential transducers.
383  DeterminizeType type; // Determinization type.
384  bool increment_subsequential_label; // When creating several subsequential
385  // arcs at a given state, make their
386  // label distinct by incrementing.
387  Filter *filter; // Determinization filter;
388  // DeterminizeFst takes ownership.
389  StateTable *state_table; // Determinization state table;
390  // DeterminizeFst takes ownership.
391 
392  explicit DeterminizeFstOptions(const CacheOptions &opts, float delta = kDelta,
393  Label subsequential_label = 0,
395  bool increment_subsequential_label = false,
396  Filter *filter = nullptr,
397  StateTable *state_table = nullptr)
398  : CacheOptions(opts),
399  delta(delta),
400  subsequential_label(subsequential_label),
401  type(type),
402  increment_subsequential_label(increment_subsequential_label),
403  filter(filter),
404  state_table(state_table) {}
405 
406  explicit DeterminizeFstOptions(float delta = kDelta,
407  Label subsequential_label = 0,
409  bool increment_subsequential_label = false,
410  Filter *filter = nullptr,
411  StateTable *state_table = nullptr)
412  : delta(delta),
413  subsequential_label(subsequential_label),
414  type(type),
415  increment_subsequential_label(increment_subsequential_label),
416  filter(filter),
417  state_table(state_table) {}
418 };
419 
420 namespace internal {
421 
422 // Implementation of delayed DeterminizeFst. This base class is
423 // common to the variants that implement acceptor and transducer
424 // determinization.
425 template <class Arc>
426 class DeterminizeFstImplBase : public CacheImpl<Arc> {
427  public:
428  using Label = typename Arc::Label;
429  using StateId = typename Arc::StateId;
430  using Weight = typename Arc::Weight;
431 
433  using State = typename Store::State;
434 
435  using FstImpl<Arc>::SetType;
440 
441  using CacheBaseImpl<CacheState<Arc>>::HasStart;
442  using CacheBaseImpl<CacheState<Arc>>::HasFinal;
443  using CacheBaseImpl<CacheState<Arc>>::HasArcs;
444  using CacheBaseImpl<CacheState<Arc>>::SetFinal;
445  using CacheBaseImpl<CacheState<Arc>>::SetStart;
446 
447  template <class CommonDivisor, class Filter, class StateTable>
449  const Fst<Arc> &fst,
451  : CacheImpl<Arc>(opts), fst_(fst.Copy()) {
452  SetType("determinize");
453  const auto iprops = fst.Properties(kFstProperties, false);
454  const auto dprops =
455  DeterminizeProperties(iprops, opts.subsequential_label != 0,
458  : true);
459  SetProperties(Filter::Properties(dprops), kCopyProperties);
460  SetInputSymbols(fst.InputSymbols());
461  SetOutputSymbols(fst.OutputSymbols());
462  }
463 
465  : CacheImpl<Arc>(impl), fst_(impl.fst_->Copy(true)) {
466  SetType("determinize");
467  SetProperties(impl.Properties(), kCopyProperties);
468  SetInputSymbols(impl.InputSymbols());
469  SetOutputSymbols(impl.OutputSymbols());
470  }
471 
472  virtual DeterminizeFstImplBase<Arc> *Copy() const = 0;
473 
475  if (!HasStart()) {
476  const auto start = ComputeStart();
477  if (start != kNoStateId) SetStart(start);
478  }
479  return CacheImpl<Arc>::Start();
480  }
481 
483  if (!HasFinal(s)) SetFinal(s, ComputeFinal(s));
484  return CacheImpl<Arc>::Final(s);
485  }
486 
487  virtual void Expand(StateId s) = 0;
488 
489  size_t NumArcs(StateId s) {
490  if (!HasArcs(s)) Expand(s);
491  return CacheImpl<Arc>::NumArcs(s);
492  }
493 
495  if (!HasArcs(s)) Expand(s);
497  }
498 
500  if (!HasArcs(s)) Expand(s);
502  }
503 
505  if (!HasArcs(s)) Expand(s);
507  }
508 
509  virtual StateId ComputeStart() = 0;
510 
511  virtual Weight ComputeFinal(StateId s) = 0;
512 
513  const Fst<Arc> &GetFst() const { return *fst_; }
514 
515  private:
516  std::unique_ptr<const Fst<Arc>> fst_; // Input FST.
517 };
518 
519 // Implementation of delayed determinization for weighted acceptors.
520 template <class Arc, class CommonDivisor, class Filter, class StateTable>
522  public:
523  using Label = typename Arc::Label;
524  using StateId = typename Arc::StateId;
525  using Weight = typename Arc::Weight;
526 
527  using FilterState = typename Filter::FilterState;
529  using Element = typename StateTuple::Element;
530  using Subset = typename StateTuple::Subset;
531  using LabelMap = typename Filter::LabelMap;
532 
536 
538  const Fst<Arc> &fst, const std::vector<Weight> *in_dist,
539  std::vector<Weight> *out_dist,
541  : DeterminizeFstImplBase<Arc>(fst, opts),
542  delta_(opts.delta),
543  in_dist_(in_dist),
544  out_dist_(out_dist),
545  filter_(opts.filter ? opts.filter : new Filter(fst)),
546  state_table_(opts.state_table ? opts.state_table : new StateTable()) {
547  if (!fst.Properties(kAcceptor, true)) {
548  FSTERROR() << "DeterminizeFst: Argument not an acceptor";
549  SetProperties(kError, kError);
550  }
551  if (!(Weight::Properties() & kLeftSemiring)) {
552  FSTERROR() << "DeterminizeFst: Weight must be left distributive: "
553  << Weight::Type();
554  SetProperties(kError, kError);
555  }
556  if (out_dist_) out_dist_->clear();
557  }
558 
561  : DeterminizeFstImplBase<Arc>(impl),
562  delta_(impl.delta_),
563  in_dist_(nullptr),
564  out_dist_(nullptr),
565  filter_(new Filter(*impl.filter_, &GetFst())),
566  state_table_(new StateTable(*impl.state_table_)) {
567  if (impl.out_dist_) {
568  FSTERROR() << "DeterminizeFsaImpl: Cannot copy with out_dist vector";
569  SetProperties(kError, kError);
570  }
571  }
572 
574  const override {
576  *this);
577  }
578 
579  uint64 Properties() const override { return Properties(kFstProperties); }
580 
581  // Sets error if found, and returns other FST impl properties.
582  uint64 Properties(uint64 mask) const override {
583  if ((mask & kError) && (GetFst().Properties(kError, false))) {
584  SetProperties(kError, kError);
585  }
586  return FstImpl<Arc>::Properties(mask);
587  }
588 
589  StateId ComputeStart() override {
590  const auto s = GetFst().Start();
591  if (s == kNoStateId) return kNoStateId;
592  auto *tuple = new StateTuple;
593  tuple->subset.emplace_front(s, Weight::One());
594  tuple->filter_state = filter_->Start();
595  return FindState(tuple);
596  }
597 
599  const auto *tuple = state_table_->Tuple(s);
600  filter_->SetState(s, *tuple);
601  auto final_weight = Weight::Zero();
602  for (auto it = tuple->subset.begin(); it != tuple->subset.end(); ++it) {
603  const auto &element = *it;
604  final_weight =
605  Plus(final_weight,
606  Times(element.weight, GetFst().Final(element.state_id)));
607  final_weight = filter_->FilterFinal(final_weight, element);
608  if (!final_weight.Member()) SetProperties(kError, kError);
609  }
610  return final_weight;
611  }
612 
614  const auto s = state_table_->FindState(tuple);
615  if (in_dist_ && out_dist_->size() <= s) {
616  out_dist_->push_back(ComputeDistance(tuple->subset));
617  }
618  return s;
619  }
620 
621  // Computes distance from a state to the final states in the DFA given the
622  // distances in the NFA.
623  Weight ComputeDistance(const Subset &subset) {
624  auto outd = Weight::Zero();
625  for (auto it = subset.begin(); it != subset.end(); ++it) {
626  const auto &element = *it;
627  const auto ind =
628  (element.state_id < in_dist_->size() ? (*in_dist_)[element.state_id]
629  : Weight::Zero());
630  outd = Plus(outd, Times(element.weight, ind));
631  }
632  return outd;
633  }
634 
635  // Computes the outgoing transitions from a state, creating new destination
636  // states as needed.
637  void Expand(StateId s) override {
638  LabelMap label_map;
639  GetLabelMap(s, &label_map);
640  for (auto it = label_map.begin(); it != label_map.end(); ++it) {
641  AddArc(s, std::move(it->second));
642  }
643  SetArcs(s);
644  }
645 
646  private:
648 
649  // Constructs proto-determinization transition, including destination subset,
650  // per label.
651  void GetLabelMap(StateId s, LabelMap *label_map) {
652  const auto *src_tuple = state_table_->Tuple(s);
653  filter_->SetState(s, *src_tuple);
654  for (auto it = src_tuple->subset.begin(); it != src_tuple->subset.end();
655  ++it) {
656  const auto &src_element = *it;
657  for (ArcIterator<Fst<Arc>> aiter(GetFst(), src_element.state_id);
658  !aiter.Done(); aiter.Next()) {
659  const auto &arc = aiter.Value();
660  Element dest_element(arc.nextstate,
661  Times(src_element.weight, arc.weight));
662  filter_->FilterArc(arc, src_element, std::move(dest_element),
663  label_map);
664  }
665  }
666  for (auto it = label_map->begin(); it != label_map->end(); ++it) {
667  NormArc(&it->second);
668  }
669  }
670 
671  // Sorts subsets and removes duplicate elements, normalizing transition and
672  // subset weights.
673  void NormArc(DetArc *det_arc) {
674  auto *dest_tuple = det_arc->dest_tuple;
675  dest_tuple->subset.sort();
676  auto piter = dest_tuple->subset.begin();
677  for (auto diter = dest_tuple->subset.begin();
678  diter != dest_tuple->subset.end();) {
679  auto &dest_element = *diter;
680  auto &prev_element = *piter;
681  // Computes arc weight.
682  det_arc->weight = common_divisor_(det_arc->weight, dest_element.weight);
683  if (piter != diter && dest_element.state_id == prev_element.state_id) {
684  // Found duplicate state: sums state weight and deletes duplicate.
685  prev_element.weight = Plus(prev_element.weight, dest_element.weight);
686  if (!prev_element.weight.Member()) SetProperties(kError, kError);
687  ++diter;
688  dest_tuple->subset.erase_after(piter);
689  } else {
690  piter = diter;
691  ++diter;
692  }
693  }
694  // Divides out label weight from destination subset elements, quantizing to
695  // ensure comparisons are effective.
696  for (auto diter = dest_tuple->subset.begin();
697  diter != dest_tuple->subset.end(); ++diter) {
698  auto &dest_element = *diter;
699  dest_element.weight =
700  Divide(dest_element.weight, det_arc->weight, DIVIDE_LEFT);
701  dest_element.weight = dest_element.weight.Quantize(delta_);
702  }
703  }
704 
705  // Adds an arc from state S to the destination state associated with state
706  // tuple in det_arc as created by GetLabelMap.
707  void AddArc(StateId s, DetArc &&det_arc) {
709  s, det_arc.label, det_arc.label, std::move(det_arc.weight),
710  FindState(det_arc.dest_tuple));
711  }
712 
713  float delta_; // Quantization delta for weights.
714  const std::vector<Weight> *in_dist_; // Distance to final NFA states.
715  std::vector<Weight> *out_dist_; // Distance to final DFA states.
716 
717  // FIXME(kbg): Ought to be static const?
718  CommonDivisor common_divisor_;
719  std::unique_ptr<Filter> filter_;
720  std::unique_ptr<StateTable> state_table_;
721 };
722 
723 // Implementation of delayed determinization for transducers. Transducer
724 // determinization is implemented by mapping the input to the Gallic semiring as
725 // an acceptor whose weights contain the output strings and using acceptor
726 // determinization above to determinize that acceptor.
727 template <class Arc, GallicType G, class CommonDivisor, class Filter,
728  class StateTable>
730  public:
731  using Label = typename Arc::Label;
732  using StateId = typename Arc::StateId;
733  using Weight = typename Arc::Weight;
734 
736  using ToArc = typename ToMapper::ToArc;
740 
742  using ToFilter = typename Filter::template rebind<ToArc>::Other;
743  using ToFilterState = typename ToFilter::FilterState;
744  using ToStateTable =
745  typename StateTable::template rebind<ToArc, ToFilterState>::Other;
747 
750  using CacheBaseImpl<CacheState<Arc>>::GetCacheGc;
751  using CacheBaseImpl<CacheState<Arc>>::GetCacheLimit;
752 
754  const Fst<Arc> &fst,
756  : DeterminizeFstImplBase<Arc>(fst, opts),
757  delta_(opts.delta),
758  subsequential_label_(opts.subsequential_label),
759  increment_subsequential_label_(opts.increment_subsequential_label) {
760  if (opts.state_table) {
761  FSTERROR() << "DeterminizeFst: "
762  << "A state table can not be passed with transducer input";
763  SetProperties(kError, kError);
764  return;
765  }
766  Init(GetFst(), opts.filter);
767  }
768 
771  : DeterminizeFstImplBase<Arc>(impl),
772  delta_(impl.delta_),
773  subsequential_label_(impl.subsequential_label_),
774  increment_subsequential_label_(impl.increment_subsequential_label_) {
775  Init(GetFst(), nullptr);
776  }
777 
779  const override {
781  *this);
782  }
783 
784  uint64 Properties() const override { return Properties(kFstProperties); }
785 
786  // Sets error if found, and returns other FST impl properties.
787  uint64 Properties(uint64 mask) const override {
788  if ((mask & kError) && (GetFst().Properties(kError, false) ||
789  from_fst_->Properties(kError, false))) {
790  SetProperties(kError, kError);
791  }
792  return FstImpl<Arc>::Properties(mask);
793  }
794 
795  StateId ComputeStart() override { return from_fst_->Start(); }
796 
797  Weight ComputeFinal(StateId s) override { return from_fst_->Final(s); }
798 
799  void Expand(StateId s) override {
800  for (ArcIterator<FromFst> aiter(*from_fst_, s); !aiter.Done();
801  aiter.Next()) {
802  CacheImpl<Arc>::PushArc(s, aiter.Value());
803  }
805  }
806 
807  private:
808  // Initialization of transducer determinization implementation, which is
809  // defined after DeterminizeFst since it calls it.
810  void Init(const Fst<Arc> &fst, Filter *filter);
811 
812  float delta_;
813  Label subsequential_label_;
814  bool increment_subsequential_label_;
815  std::unique_ptr<FromFst> from_fst_;
816 };
817 
818 } // namespace internal
819 
820 // Determinizes a weighted transducer. This version is a delayed
821 // FST. The result will be an equivalent FST that has the property
822 // that no state has two transitions with the same input label.
823 // For this algorithm, epsilon transitions are treated as regular
824 // symbols (cf. RmEpsilon).
825 //
826 // The transducer must be functional. The weights must be (weakly) left
827 // divisible (valid for TropicalWeight and LogWeight for instance) and be
828 // zero-sum-free if for all a, b: (Plus(a, b) == 0) => a = b = 0.
829 //
830 // Complexity:
831 //
832 // Determinizable: exponential (polynomial in the size of the output).
833 // Non-determinizable: does not terminate.
834 //
835 // The determinizable automata include all unweighted and all acyclic input.
836 //
837 // For more information, see:
838 //
839 // Mohri, M. 1997. Finite-state transducers in language and speech processing.
840 // Computational Linguistics 23(2): 269-311.
841 //
842 // This class attaches interface to implementation and handles reference
843 // counting, delegating most methods to ImplToFst.
844 template <class A>
845 class DeterminizeFst : public ImplToFst<internal::DeterminizeFstImplBase<A>> {
846  public:
847  using Arc = A;
848  using Label = typename Arc::Label;
849  using StateId = typename Arc::StateId;
850  using Weight = typename Arc::Weight;
851 
853  using State = typename Store::State;
855 
858 
859  template <class B, GallicType G, class CommonDivisor, class Filter,
860  class StateTable>
861  friend class DeterminizeFstImpl;
862 
863  explicit DeterminizeFst(const Fst<A> &fst)
864  : ImplToFst<Impl>(CreateImpl(fst)) {}
865 
866  template <class CommonDivisor, class Filter, class StateTable>
868  const Fst<Arc> &fst,
870  &opts =
872  : ImplToFst<Impl>(CreateImpl(fst, opts)) {}
873 
874  // This acceptor-only version additionally computes the distance to final
875  // states in the output if provided with those distances for the input; this
876  // is useful for e.g., computing the k-shortest unique paths.
877  template <class CommonDivisor, class Filter, class StateTable>
879  const Fst<Arc> &fst, const std::vector<Weight> *in_dist,
880  std::vector<Weight> *out_dist,
882  &opts =
884  : ImplToFst<Impl>(
885  std::make_shared<internal::DeterminizeFsaImpl<Arc, CommonDivisor,
886  Filter, StateTable>>(
887  fst, in_dist, out_dist, opts)) {
888  if (!fst.Properties(kAcceptor, true)) {
889  FSTERROR() << "DeterminizeFst: "
890  << "Distance to final states computed for acceptors only";
891  GetMutableImpl()->SetProperties(kError, kError);
892  }
893  }
894 
895  // See Fst<>::Copy() for doc.
896  DeterminizeFst(const DeterminizeFst<Arc> &fst, bool safe = false)
897  : ImplToFst<Impl>(safe ? std::shared_ptr<Impl>(fst.GetImpl()->Copy())
898  : fst.GetSharedImpl()) {}
899 
900  // Get a copy of this DeterminizeFst. See Fst<>::Copy() for further doc.
901  DeterminizeFst<Arc> *Copy(bool safe = false) const override {
902  return new DeterminizeFst<Arc>(*this, safe);
903  }
904 
905  inline void InitStateIterator(StateIteratorData<Arc> *data) const override;
906 
907  void InitArcIterator(StateId s, ArcIteratorData<Arc> *data) const override {
908  GetMutableImpl()->InitArcIterator(s, data);
909  }
910 
911  private:
914 
915  static std::shared_ptr<Impl> CreateImpl(const Fst<Arc> &fst) {
920  return CreateImpl(fst, opts);
921  }
922 
923  template <class CommonDivisor, class Filter, class StateTable>
924  static std::shared_ptr<Impl> CreateImpl(
925  const Fst<Arc> &fst,
927  &opts) {
928  if (fst.Properties(kAcceptor, true)) {
929  // Calls implementation for acceptors.
930  return std::make_shared<
932  fst, nullptr, nullptr, opts);
933  } else if (opts.type == DETERMINIZE_DISAMBIGUATE) {
934  auto rv = std::make_shared<internal::DeterminizeFstImpl<
935  Arc, GALLIC_MIN, CommonDivisor, Filter, StateTable>>(fst, opts);
936  if (!(Weight::Properties() & kPath)) {
937  FSTERROR() << "DeterminizeFst: Weight needs to have the "
938  << "path property to disambiguate output: "
939  << Weight::Type();
940  rv->SetProperties(kError, kError);
941  }
942  // Calls disambiguating implementation for non-functional transducers.
943  return rv;
944  } else if (opts.type == DETERMINIZE_FUNCTIONAL) {
945  // Calls implementation for functional transducers.
946  return std::make_shared<internal::DeterminizeFstImpl<
947  Arc, GALLIC_RESTRICT, CommonDivisor, Filter, StateTable>>(fst, opts);
948  } else { // opts.type == DETERMINIZE_NONFUNCTIONAL
949  // Calls implementation for non functional transducers;
950  return std::make_shared<internal::DeterminizeFstImpl<
951  Arc, GALLIC, CommonDivisor, Filter, StateTable>>(fst, opts);
952  }
953  }
954 
955  DeterminizeFst &operator=(const DeterminizeFst &) = delete;
956 };
957 
958 namespace internal {
959 
960 // Initialization of transducer determinization implementation, which is defined
961 // after DeterminizeFst since it calls it.
962 template <class A, GallicType G, class D, class F, class T>
963 void DeterminizeFstImpl<A, G, D, F, T>::Init(const Fst<A> &fst, F *filter) {
964  // Mapper to an acceptor.
965  const ToFst to_fst(fst, ToMapper());
966  auto *to_filter = filter ? new ToFilter(to_fst, filter) : nullptr;
967  // This recursive call terminates since it is to a (non-recursive)
968  // different constructor.
969  const CacheOptions copts(GetCacheGc(), GetCacheLimit());
971  dopts(copts, delta_, 0, DETERMINIZE_FUNCTIONAL, false, to_filter);
972  // Uses acceptor-only constructor to avoid template recursion.
973  const DeterminizeFst<ToArc> det_fsa(to_fst, nullptr, nullptr, dopts);
974  // Mapper back to transducer.
975  const FactorWeightOptions<ToArc> fopts(
976  CacheOptions(true, 0), delta_, kFactorFinalWeights, subsequential_label_,
977  subsequential_label_, increment_subsequential_label_,
978  increment_subsequential_label_);
979  const FactorWeightFst<ToArc, FactorIterator> factored_fst(det_fsa, fopts);
980  from_fst_.reset(new FromFst(factored_fst, FromMapper(subsequential_label_)));
981 }
982 
983 } // namespace internal
984 
985 // Specialization for DeterminizeFst.
986 template <class Arc>
988  : public CacheStateIterator<DeterminizeFst<Arc>> {
989  public:
990  explicit StateIterator(const DeterminizeFst<Arc> &fst)
991  : CacheStateIterator<DeterminizeFst<Arc>>(fst, fst.GetMutableImpl()) {}
992 };
993 
994 // Specialization for DeterminizeFst.
995 template <class Arc>
997  : public CacheArcIterator<DeterminizeFst<Arc>> {
998  public:
999  using StateId = typename Arc::StateId;
1000 
1002  : CacheArcIterator<DeterminizeFst<Arc>>(fst.GetMutableImpl(), s) {
1003  if (!fst.GetImpl()->HasArcs(s)) fst.GetMutableImpl()->Expand(s);
1004  }
1005 };
1006 
1007 template <class Arc>
1009  StateIteratorData<Arc> *data) const {
1010  data->base = new StateIterator<DeterminizeFst<Arc>>(*this);
1011 }
1012 
1013 // Useful aliases when using StdArc.
1015 
1016 template <class Arc>
1018  using Label = typename Arc::Label;
1019  using StateId = typename Arc::StateId;
1020  using Weight = typename Arc::Weight;
1021 
1022  float delta; // Quantization delta for subset weights.
1023  Weight weight_threshold; // Pruning weight threshold.
1024  StateId state_threshold; // Pruning state threshold.
1025  Label subsequential_label; // Label used for residual final output.
1027  bool increment_subsequential_label; // When creating several subsequential
1028  // arcs at a given state, make their
1029  // label distinct by incrementation?
1030 
1031  explicit DeterminizeOptions(float delta = kDelta,
1032  Weight weight_threshold = Weight::Zero(),
1033  StateId state_threshold = kNoStateId,
1034  Label subsequential_label = 0,
1036  bool increment_subsequential_label = false)
1037  : delta(delta),
1038  weight_threshold(std::move(weight_threshold)),
1039  state_threshold(state_threshold),
1040  subsequential_label(subsequential_label),
1041  type(type),
1042  increment_subsequential_label(increment_subsequential_label) {}
1043 };
1044 
1045 // Determinizes a weighted transducer. This version writes the
1046 // determinized Fst to an output MutableFst. The result will be an
1047 // equivalent FST that has the property that no state has two
1048 // transitions with the same input label. For this algorithm, epsilon
1049 // transitions are treated as regular symbols (cf. RmEpsilon).
1050 //
1051 // The transducer must be functional. The weights must be (weakly)
1052 // left divisible (valid for TropicalWeight and LogWeight).
1053 //
1054 // Complexity:
1055 //
1056 // Determinizable: exponential (polynomial in the size of the output)
1057 // Non-determinizable: does not terminate
1058 //
1059 // The determinizable automata include all unweighted and all acyclic input.
1060 template <class Arc>
1062  const Fst<Arc> &ifst, MutableFst<Arc> *ofst,
1064  using Weight = typename Arc::Weight;
1066  nopts.delta = opts.delta;
1067  nopts.subsequential_label = opts.subsequential_label;
1068  nopts.type = opts.type;
1069  nopts.increment_subsequential_label = opts.increment_subsequential_label;
1070  nopts.gc_limit = 0; // Caches only the last state for fastest copy.
1071  if (opts.weight_threshold != Weight::Zero() ||
1072  opts.state_threshold != kNoStateId) {
1073  if (ifst.Properties(kAcceptor, false)) {
1074  std::vector<Weight> idistance;
1075  std::vector<Weight> odistance;
1076  ShortestDistance(ifst, &idistance, true);
1077  DeterminizeFst<Arc> dfst(ifst, &idistance, &odistance, nopts);
1079  opts.weight_threshold, opts.state_threshold, AnyArcFilter<Arc>(),
1080  &odistance);
1081  Prune(dfst, ofst, popts);
1082  } else {
1083  *ofst = DeterminizeFst<Arc>(ifst, nopts);
1084  Prune(ofst, opts.weight_threshold, opts.state_threshold);
1085  }
1086  } else {
1087  *ofst = DeterminizeFst<Arc>(ifst, nopts);
1088  }
1089 }
1090 
1091 } // namespace fst
1092 
1093 #endif // FST_DETERMINIZE_H_
typename Impl::Arc Arc
Definition: fst.h:871
DefaultDeterminizeStateTable(const DefaultDeterminizeStateTable< Arc, FilterState > &table)
Definition: determinize.h:304
typename Arc::Label Label
Definition: determinize.h:196
DefaultDeterminizeFilter(const Fst< Arc > &fst)
Definition: determinize.h:211
ssize_t NumOutputEpsilons(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
Definition: expanded-fst.h:99
void InitArcIterator(StateId s, ArcIteratorData< Arc > *data)
Definition: determinize.h:504
uint64 Properties() const override
Definition: determinize.h:784
DeterminizeFst< Arc > * Copy(bool safe=false) const override
Definition: determinize.h:901
ExpectationWeight< X1, X2 > Divide(const ExpectationWeight< X1, X2 > &w1, const ExpectationWeight< X1, X2 > &w2, DivideType typ=DIVIDE_ANY)
FilterState Start() const
Definition: determinize.h:226
typename StateTuple::Arc Arc
Definition: determinize.h:170
constexpr int kNoLabel
Definition: fst.h:179
typename StateTuple::Element Element
Definition: determinize.h:293
DefaultDeterminizeStateTable(size_t table_size=0)
Definition: determinize.h:301
DeterminizeFsaImpl(const Fst< Arc > &fst, const std::vector< Weight > *in_dist, std::vector< Weight > *out_dist, const DeterminizeFstOptions< Arc, CommonDivisor, Filter, StateTable > &opts)
Definition: determinize.h:537
DefaultDeterminizeFilter(const Fst< Arc > &fst, Filter *filter)
Definition: determinize.h:216
bool FilterArc(const Arc &arc, const Element &src_element, Element &&dest_element, LabelMap *label_map) const
Definition: determinize.h:233
uint64_t uint64
Definition: types.h:32
typename StateTuple::Subset Subset
Definition: determinize.h:530
DeterminizeFst(const Fst< Arc > &fst, const std::vector< Weight > *in_dist, std::vector< Weight > *out_dist, const DeterminizeFstOptions< Arc, CommonDivisor, Filter, StateTable > &opts=DeterminizeFstOptions< Arc, CommonDivisor, Filter, StateTable >())
Definition: determinize.h:878
DeterminizeArc(const Arc &arc)
Definition: determinize.h:177
const Label & Value() const
bool operator==(const DeterminizeElement< Arc > &element) const
Definition: determinize.h:128
bool operator!=(const DeterminizeStateTuple< Arc, FilterState > &tuple) const
Definition: determinize.h:158
uint64 Properties(uint64 mask) const override
Definition: determinize.h:787
DeterminizeFsaImpl(const DeterminizeFsaImpl< Arc, CommonDivisor, Filter, StateTable > &impl)
Definition: determinize.h:559
DefaultDeterminizeFilter(const DefaultDeterminizeFilter< Arc > &filter, const Fst< Arc > *fst=nullptr)
Definition: determinize.h:222
bool operator!=(const DeterminizeElement< Arc > &element) const
Definition: determinize.h:132
Arc::Weight Final(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
Definition: expanded-fst.h:82
const SymbolTable * OutputSymbols() const
Definition: fst.h:690
void Determinize(const Fst< Arc > &ifst, MutableFst< Arc > *ofst, const DeterminizeOptions< Arc > &opts=DeterminizeOptions< Arc >())
Definition: determinize.h:1061
std::map< Label, internal::DeterminizeArc< StateTuple >> LabelMap
Definition: determinize.h:203
StateId FindState(StateTuple *tuple)
Definition: determinize.h:613
DeterminizeFstOptions(const CacheOptions &opts, float delta=kDelta, Label subsequential_label=0, DeterminizeType type=DETERMINIZE_FUNCTIONAL, bool increment_subsequential_label=false, Filter *filter=nullptr, StateTable *state_table=nullptr)
Definition: determinize.h:392
Weight operator()(const Weight &w1, const Weight &w2) const
Definition: determinize.h:54
DeterminizeElement(StateId s, Weight weight)
Definition: determinize.h:125
typename Arc::Label Label
Definition: determinize.h:171
ExpectationWeight< X1, X2 > Times(const ExpectationWeight< X1, X2 > &w1, const ExpectationWeight< X1, X2 > &w2)
const W2 & Value2() const
Definition: pair-weight.h:78
SetType
Definition: set-weight.h:37
typename DeterminizeFst< Arc >::Arc Arc
Definition: cache.h:1143
void InitStateIterator(StateIteratorData< Arc > *data) const override
Definition: determinize.h:1008
ssize_t NumArcs(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
Definition: expanded-fst.h:88
DeterminizeType type
Definition: determinize.h:1026
typename StateTuple::Subset Subset
Definition: determinize.h:294
constexpr uint64 kLeftSemiring
Definition: weight.h:112
DeterminizeFsaImpl< Arc, CommonDivisor, Filter, StateTable > * Copy() const override
Definition: determinize.h:573
uint64 Properties() const override
Definition: determinize.h:579
constexpr uint64 kFstProperties
Definition: properties.h:301
constexpr uint64 kCopyProperties
Definition: properties.h:138
constexpr int kNoStateId
Definition: fst.h:180
void InitArcIterator(StateId s, ArcIteratorData< Arc > *data) const override
Definition: determinize.h:907
constexpr uint32 kFactorFinalWeights
Definition: factor-weight.h:23
typename ToMapper::ToArc ToArc
Definition: determinize.h:736
virtual uint64 Properties(uint64 mask, bool test) const =0
#define FSTERROR()
Definition: util.h:35
Weight FilterFinal(Weight weight, const Element &element)
Definition: determinize.h:246
Weight ComputeDistance(const Subset &subset)
Definition: determinize.h:623
typename Store::State State
Definition: determinize.h:853
typename Arc::Weight Weight
Definition: fst.h:873
ArcIterator(const DeterminizeFst< Arc > &fst, StateId s)
Definition: determinize.h:1001
StateIteratorBase< Arc > * base
Definition: fst.h:351
DeterminizeFstOptions(float delta=kDelta, Label subsequential_label=0, DeterminizeType type=DETERMINIZE_FUNCTIONAL, bool increment_subsequential_label=false, Filter *filter=nullptr, StateTable *state_table=nullptr)
Definition: determinize.h:406
IntegerFilterState< signed char > CharFilterState
Definition: filter-state.h:74
ssize_t NumInputEpsilons(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
Definition: expanded-fst.h:93
typename Filter::FilterState FilterState
Definition: determinize.h:527
DeterminizeFst(const DeterminizeFst< Arc > &fst, bool safe=false)
Definition: determinize.h:896
DeterminizeFstImpl< Arc, G, CommonDivisor, Filter, StateTable > * Copy() const override
Definition: determinize.h:778
Weight operator()(const Weight &w1, const Weight &w2) const
Definition: determinize.h:102
void SetState(StateId s, const StateTuple &tuple)
Definition: determinize.h:229
static uint64 Properties(uint64 props)
Definition: determinize.h:248
typename Arc::Weight Weight
Definition: determinize.h:1020
const StateTuple * Tuple(StateId s)
Definition: determinize.h:322
std::forward_list< Element > Subset
Definition: determinize.h:149
typename ToFilter::FilterState ToFilterState
Definition: determinize.h:743
typename FirstCacheStore< VectorCacheStore< CacheState< Arc > > >::State State
Definition: cache.h:644
typename Arc::Weight Weight
Definition: determinize.h:198
typename Filter::template rebind< ToArc >::Other ToFilter
Definition: determinize.h:742
typename Arc::StateId StateId
Definition: determinize.h:289
bool operator==(const DeterminizeStateTuple< Arc, FilterState > &tuple) const
Definition: determinize.h:153
ExpectationWeight< X1, X2 > Plus(const ExpectationWeight< X1, X2 > &w1, const ExpectationWeight< X1, X2 > &w2)
bool Done() const
Definition: fst.h:499
const Fst< Arc > & GetFst() const
Definition: determinize.h:513
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
typename Arc::StateId StateId
Definition: determinize.h:122
typename Arc::Weight Weight
Definition: determinize.h:172
DeterminizeFst(const Fst< A > &fst)
Definition: determinize.h:863
void Expand(StateId s) override
Definition: determinize.h:637
typename Arc::StateId StateId
Definition: fst.h:872
typename Arc::StateId StateId
Definition: determinize.h:1019
StateIterator(const DeterminizeFst< Arc > &fst)
Definition: determinize.h:990
Weight ComputeFinal(StateId s) override
Definition: determinize.h:598
Weight operator()(const Weight &w1, const Weight &w2) const
Definition: determinize.h:40
typename DeterminizeFst< Arc >::Arc Arc
Definition: cache.h:1189
uint64 Properties(uint64 mask) const override
Definition: determinize.h:582
virtual const SymbolTable * InputSymbols() const =0
const SymbolTable * InputSymbols() const
Definition: fst.h:688
DeterminizeFstImpl(const DeterminizeFstImpl< Arc, G, CommonDivisor, Filter, StateTable > &impl)
Definition: determinize.h:769
constexpr uint64 kPath
Definition: weight.h:126
typename Arc::Weight Weight
Definition: determinize.h:123
void Expand(StateId s) override
Definition: determinize.h:799
uint64 DeterminizeProperties(uint64 inprops, bool has_subsequential_label, bool distinct_psubsequential_labels)
Definition: properties.cc:112
constexpr uint64 kError
Definition: properties.h:33
typename StateTuple::Element Element
Definition: determinize.h:529
DeterminizeOptions(float delta=kDelta, Weight weight_threshold=Weight::Zero(), StateId state_threshold=kNoStateId, Label subsequential_label=0, DeterminizeType type=DETERMINIZE_FUNCTIONAL, bool increment_subsequential_label=false)
Definition: determinize.h:1031
size_t Size() const
typename Arc::Label Label
Definition: determinize.h:848
DeterminizeFst(const Fst< Arc > &fst, const DeterminizeFstOptions< Arc, CommonDivisor, Filter, StateTable > &opts=DeterminizeFstOptions< Arc, CommonDivisor, Filter, StateTable >())
Definition: determinize.h:867
void ShortestDistance(const Fst< Arc > &fst, std::vector< typename Arc::Weight > *distance, const ShortestDistanceOptions< Arc, Queue, ArcFilter > &opts)
typename Arc::Label Label
Definition: determinize.h:378
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
typename Filter::LabelMap LabelMap
Definition: determinize.h:531
typename CacheState< Arc >::Arc Arc
Definition: cache.h:833
Impl * GetMutableImpl() const
Definition: fst.h:947
typename Arc::StateId StateId
Definition: determinize.h:197
StateId FindState(StateTuple *tuple)
Definition: determinize.h:315
typename Arc::Weight Weight
Definition: determinize.h:290
DeterminizeFstImplBase(const Fst< Arc > &fst, const DeterminizeFstOptions< Arc, CommonDivisor, Filter, StateTable > &opts)
Definition: determinize.h:448
StateId ComputeStart() override
Definition: determinize.h:795
size_t gc_limit
Definition: cache.h:29
DeterminizeFstImpl(const Fst< Arc > &fst, const DeterminizeFstOptions< Arc, CommonDivisor, Filter, StateTable > &opts)
Definition: determinize.h:753
constexpr float kDelta
Definition: weight.h:109
StateId ComputeStart() override
Definition: determinize.h:589
DeterminizeType
Definition: determinize.h:358
Weight ComputeFinal(StateId s) override
Definition: determinize.h:797
Weight operator()(const Weight &w1, const Weight &w2) const
Definition: determinize.h:83
const Impl * GetImpl() const
Definition: fst.h:945
const W1 & Value1() const
Definition: pair-weight.h:76
typename StateTable::template rebind< ToArc, ToFilterState >::Other ToStateTable
Definition: determinize.h:745
DeterminizeFstImplBase(const DeterminizeFstImplBase< Arc > &impl)
Definition: determinize.h:464
virtual const SymbolTable * OutputSymbols() const =0