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