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