FST  openfst-1.8.2
OpenFst Library
label-reachable.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 // Class to determine if a non-epsilon label can be read as the first
19 // non-epsilon symbol along some path from a given state.
20 
21 #ifndef FST_LABEL_REACHABLE_H_
22 #define FST_LABEL_REACHABLE_H_
23 
24 #include <memory>
25 #include <utility>
26 #include <vector>
27 
28 #include <fst/log.h>
29 
30 #include <fst/accumulator.h>
31 #include <fst/arcsort.h>
32 #include <fst/interval-set.h>
33 #include <fst/state-reachable.h>
34 #include <fst/util.h>
35 #include <fst/vector-fst.h>
36 
37 #include <unordered_map>
38 
39 namespace fst {
40 
41 // Stores shareable data for label reachable class copies.
42 template <typename Label>
44  public:
47 
48  explicit LabelReachableData(bool reach_input, bool keep_relabel_data = true)
49  : reach_input_(reach_input),
50  keep_relabel_data_(keep_relabel_data),
51  have_relabel_data_(true),
52  final_label_(kNoLabel) {}
53 
55 
56  bool ReachInput() const { return reach_input_; }
57 
58  std::vector<LabelIntervalSet> *MutableIntervalSets() {
59  return &interval_sets_;
60  }
61 
62  const LabelIntervalSet &GetIntervalSet(int s) const {
63  return interval_sets_[s];
64  }
65 
66  int NumIntervalSets() const { return interval_sets_.size(); }
67 
68  std::unordered_map<Label, Label> *MutableLabel2Index() {
69  if (!have_relabel_data_) {
70  FSTERROR() << "LabelReachableData: No relabeling data";
71  }
72  return &label2index_;
73  }
74 
75  const std::unordered_map<Label, Label> *Label2Index() const {
76  if (!have_relabel_data_) {
77  FSTERROR() << "LabelReachableData: No relabeling data";
78  }
79  return &label2index_;
80  }
81 
82  void SetFinalLabel(Label final_label) { final_label_ = final_label; }
83 
84  Label FinalLabel() const { return final_label_; }
85 
86  static LabelReachableData *Read(std::istream &istrm,
87  const FstReadOptions &opts) {
88  // NB: Using `new` to access private constructor.
89  auto data = fst::WrapUnique(new LabelReachableData());
90  ReadType(istrm, &data->reach_input_);
91  ReadType(istrm, &data->keep_relabel_data_);
92  data->have_relabel_data_ = data->keep_relabel_data_;
93  if (data->keep_relabel_data_) ReadType(istrm, &data->label2index_);
94  ReadType(istrm, &data->final_label_);
95  ReadType(istrm, &data->interval_sets_);
96  return data.release();
97  }
98 
99  bool Write(std::ostream &ostrm, const FstWriteOptions &opts) const {
100  WriteType(ostrm, reach_input_);
101  WriteType(ostrm, keep_relabel_data_);
102  if (keep_relabel_data_) WriteType(ostrm, label2index_);
103  WriteType(ostrm, FinalLabel());
104  WriteType(ostrm, interval_sets_);
105  return true;
106  }
107 
108  private:
109  LabelReachableData() {}
110 
111  bool reach_input_; // Input labels considered?
112  bool keep_relabel_data_; // Save label2index_ to file?
113  bool have_relabel_data_; // Using label2index_?
114  Label final_label_; // Final label.
115  std::unordered_map<Label, Label> label2index_; // Finds index for a label.
116  std::vector<LabelIntervalSet> interval_sets_; // Interval sets per state.
117 };
118 
119 // Apply a new state order to a vector of LabelIntervalSets. order[i] gives
120 // the StateId after sorting that corresponds to the StateId i before
121 // sorting; it must therefore be a permutation of the input FST's StateId
122 // sequence.
123 template <typename Label, typename StateId>
124 bool StateSort(std::vector<IntervalSet<Label>> *interval_sets,
125  const std::vector<StateId> &order) {
126  if (order.size() != interval_sets->size()) {
127  FSTERROR() << "StateSort: Bad order vector size: " << order.size()
128  << ", expected: " << interval_sets->size();
129  return false;
130  }
131  std::vector<IntervalSet<Label>> reordered_interval_sets(
132  interval_sets->size());
133  // TODO(jrosenstock): Use storage-efficient cycle-following algorithm
134  // from StateSort(MutableFst *, order).
135  for (StateId s = 0; s < order.size(); ++s) {
136  reordered_interval_sets[order[s]] = std::move((*interval_sets)[s]);
137  }
138  *interval_sets = std::move(reordered_interval_sets);
139  return true;
140 }
141 
142 // Apply a new state order to LabelReachableData.
143 template <typename Label, typename StateId>
145  const std::vector<StateId> &order) {
146  return StateSort(data->MutableIntervalSets(), order);
147 }
148 
149 // Functor to find the LowerBound of a Label using an ArcIterator.
150 // Used by LabelReachable. Other, more efficient implementations of
151 // this interface specialized to certain FST types may be used instead.
152 template <class Arc>
154  public:
155  using Label = typename Arc::Label;
156  using StateId = typename Arc::StateId;
157 
158  // Initializes with the FST that will later supply the ArcIterator for
159  // `operator()`. `reach_input` specified whether `operator()` will search
160  // input or output labels. If `is_copy == true`, then `fst` is a copy
161  // of the one previously passed to `Init`, so any expensive initialization
162  // can be skipped.
163  template <class FST>
164  void Init(const FST &fst, bool reach_input, bool is_copy) {
165  reach_input_ = reach_input;
166  }
167 
168  // Sets state that will be searched by `operator()`.
169  void SetState(StateId aiter_s) {}
170 
171  // Positions `aiter` at the first Arc with `label >= match_label` in the
172  // half-open interval `[aiter_begin, aiter_end)`. Returns the position
173  // of `aiter`. `aiter` must be an iterator of the FST that was passed to
174  // `Init`.
175  template <class ArcIterator>
176  ssize_t operator()(ArcIterator *aiter, ssize_t aiter_begin, ssize_t aiter_end,
177  Label match_label) const {
178  // Only needs to compute the ilabel or olabel of arcs when performing the
179  // binary search.
180  aiter->SetFlags(reach_input_ ? kArcILabelValue : kArcOLabelValue,
182  ssize_t low = aiter_begin;
183  ssize_t high = aiter_end;
184  while (low < high) {
185  const ssize_t mid = low + (high - low) / 2;
186  aiter->Seek(mid);
187  auto label = reach_input_ ? aiter->Value().ilabel : aiter->Value().olabel;
188  if (label < match_label) {
189  low = mid + 1;
190  } else {
191  high = mid;
192  }
193  }
194  aiter->Seek(low);
196  return low;
197  }
198 
199  private:
200  bool reach_input_ = false;
201 };
202 
203 // Tests reachability of labels from a given state. If reach_input is true, then
204 // input labels are considered, o.w. output labels are considered. To test for
205 // reachability from a state s, first do SetState(s), then a label l can be
206 // reached from state s of FST f iff Reach(r) is true where r = Relabel(l). The
207 // relabeling is required to ensure the consecutive ones property (C1P); this
208 // allows a compact representation of the reachable labels. See Section 2.3.3 of
209 // "A Generalized Composition Algorithm for Weighted Finite-State Transducers",
210 // Cyril Allauzen, Michael Riley, Johan Schalkwyk, Interspeech 2009.
211 // https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/35539.pdf
212 
213 // The whole FST can be relabeled instead with Relabel(&f, reach_input) so that
214 // the test Reach(r) applies directly to the labels of the transformed FST f.
215 // The relabeled FST will also be sorted appropriately for composition.
216 //
217 // Reachablity of a final state from state s (via an epsilon path) can be
218 // tested with ReachFinal().
219 //
220 // Reachability can also be tested on the set of labels specified by an arc
221 // iterator, useful for FST composition. In particular, Reach(aiter, ...) is
222 // true if labels on the input (output) side of the transitions of the arc
223 // iterator, when iter_input is true (false), can be reached from the state s.
224 // The iterator labels must have already been relabeled.
225 //
226 // With the arc iterator test of reachability, the begin position, end position
227 // and accumulated arc weight of the matches can be returned. The optional
228 // template argument controls how reachable arc weights are accumulated. The
229 // default uses semiring Plus(). Alternative ones can be used to distribute the
230 // weights in composition in various ways.
231 template <class Arc, class Accumulator = DefaultAccumulator<Arc>,
232  class D = LabelReachableData<typename Arc::Label>,
233  class LB = LabelLowerBound<Arc>>
235  public:
236  using Label = typename Arc::Label;
237  using StateId = typename Arc::StateId;
238  using Weight = typename Arc::Weight;
239  using Data = D;
240  using LowerBound = LB;
241 
242  using LabelIntervalSet = typename Data::LabelIntervalSet;
243 
245 
246  LabelReachable(const Fst<Arc> &fst, bool reach_input,
247  std::unique_ptr<Accumulator> accumulator = nullptr,
248  bool keep_relabel_data = true)
249  : fst_(std::make_unique<VectorFst<Arc>>(fst)),
250  s_(kNoStateId),
251  data_(std::make_shared<Data>(reach_input, keep_relabel_data)),
252  accumulator_(accumulator ? std::move(accumulator)
253  : std::make_unique<Accumulator>()) {
254  const auto ins = fst_->NumStates();
255  TransformFst();
256  FindIntervals(ins);
257  fst_.reset();
258  }
259 
260  explicit LabelReachable(std::shared_ptr<Data> data,
261  std::unique_ptr<Accumulator> accumulator = nullptr)
262  : s_(kNoStateId),
263  data_(std::move(data)),
264  accumulator_(accumulator ? std::move(accumulator)
265  : std::make_unique<Accumulator>()) {}
266 
267  LabelReachable(const LabelReachable &reachable, bool safe = false)
268  : s_(kNoStateId),
269  data_(reachable.data_),
270  accumulator_(
271  std::make_unique<Accumulator>(*reachable.accumulator_, safe)),
272  lower_bound_(reachable.lower_bound_),
273  reach_fst_input_(reachable.reach_fst_input_),
274  error_(reachable.error_) {}
275 
277  if (ncalls_ > 0) {
278  VLOG(2) << "# of calls: " << ncalls_;
279  VLOG(2) << "# of intervals/call: " << (nintervals_ / ncalls_);
280  }
281  }
282 
283  // Relabels w.r.t labels that give compact label sets.
284  Label Relabel(Label label) {
285  if (label == 0 || error_) return label;
286  const auto &label2index = *data_->Label2Index();
287  auto iter = label2index.find(label);
288  if (iter != label2index.end()) return iter->second;
289  auto &relabel = oov_label2index_[label];
290  if (!relabel) {
291  // Adds new label.
292  relabel = label2index.size() + oov_label2index_.size() + 1;
293  }
294  return relabel;
295  }
296 
297  // Relabels FST w.r.t to labels that give compact label sets.
298  void Relabel(MutableFst<Arc> *fst, bool relabel_input) {
299  for (StateIterator<MutableFst<Arc>> siter(*fst); !siter.Done();
300  siter.Next()) {
301  for (MutableArcIterator<MutableFst<Arc>> aiter(fst, siter.Value());
302  !aiter.Done(); aiter.Next()) {
303  auto arc = aiter.Value();
304  if (relabel_input) {
305  arc.ilabel = Relabel(arc.ilabel);
306  } else {
307  arc.olabel = Relabel(arc.olabel);
308  }
309  aiter.SetValue(arc);
310  }
311  }
312  if (relabel_input) {
313  ArcSort(fst, ILabelCompare<Arc>());
314  fst->SetInputSymbols(nullptr);
315  } else {
316  ArcSort(fst, OLabelCompare<Arc>());
317  fst->SetOutputSymbols(nullptr);
318  }
319  }
320 
321  // Returns relabeling pairs (cf. relabel.h::Relabel()). If avoid_collisions is
322  // true, extra pairs are added to ensure no collisions when relabeling
323  // automata that have labels unseen here.
324  void RelabelPairs(std::vector<std::pair<Label, Label>> *pairs,
325  bool avoid_collisions = false) {
326  pairs->clear();
327  const auto &label2index = *data_->Label2Index();
328  // Maps labels to their new values in [1, label2index().size()].
329  for (const auto &kv : label2index) {
330  if (kv.second != data_->FinalLabel()) {
331  pairs->emplace_back(kv);
332  }
333  }
334  // Maps oov labels to their values > label2index().size().
335  pairs->insert(pairs->end(), oov_label2index_.begin(),
336  oov_label2index_.end());
337  if (avoid_collisions) {
338  // Ensures any label in [1, label2index().size()] is mapped either
339  // by the above steps or to label2index() + 1 (to avoid collisions).
340  for (size_t i = 1; i <= label2index.size(); ++i) {
341  const auto it = label2index.find(i);
342  bool unmapped = it == label2index.end();
343  if (unmapped) unmapped = oov_label2index_.count(i) == 0;
344  if (unmapped || it->second == data_->FinalLabel()) {
345  pairs->emplace_back(i, label2index.size() + 1);
346  }
347  }
348  }
349  }
350 
351  // Set current state. Optionally set state associated
352  // with arc iterator to be passed to Reach.
353  void SetState(StateId s, StateId aiter_s = kNoStateId) {
354  s_ = s;
355  if (aiter_s != kNoStateId) {
356  accumulator_->SetState(aiter_s);
357  if (accumulator_->Error()) error_ = true;
358  lower_bound_.SetState(aiter_s);
359  }
360  }
361 
362  // Can reach this label from current state?
363  // Original labels must be transformed by the Relabel methods above.
364  bool Reach(Label label) const {
365  if (label == 0 || error_) return false;
366  return data_->GetIntervalSet(s_).Member(label);
367  }
368 
369  // Can reach final state (via epsilon transitions) from this state?
370  bool ReachFinal() const {
371  if (error_) return false;
372  return data_->GetIntervalSet(s_).Member(data_->FinalLabel());
373  }
374 
375  // Initialize with secondary FST to be used with Reach(Iterator,...).
376  // If reach_input = true, then arc input labels are considered in
377  // Reach(aiter, ...), o.w. output labels are considered. If copy is true, then
378  // the FST is a copy of the FST used in the previous call to this method
379  // (useful to avoid unnecessary updates).
380  template <class FST>
381  void ReachInit(const FST &fst, bool reach_input, bool copy = false) {
382  reach_fst_input_ = reach_input;
383  if (!fst.Properties(reach_fst_input_ ? kILabelSorted : kOLabelSorted,
384  true)) {
385  FSTERROR() << "LabelReachable::ReachInit: Fst is not sorted";
386  error_ = true;
387  }
388  accumulator_->Init(fst, copy);
389  if (accumulator_->Error()) error_ = true;
390  lower_bound_.Init(fst, /*reach_input=*/reach_input, /*is_copy=*/copy);
391  }
392 
393  // Can reach any arc iterator label between iterator positions
394  // aiter_begin and aiter_end?
395  // Arc iterator labels must be transformed by the Relabel methods
396  // above. If compute_weight is true, user may call ReachWeight().
397  template <class Iterator>
398  bool Reach(Iterator *aiter, ssize_t aiter_begin, ssize_t aiter_end,
399  bool compute_weight) {
400  if (error_) return false;
401  const auto &interval_set = data_->GetIntervalSet(s_);
402  ++ncalls_;
403  nintervals_ += interval_set.Size();
404  reach_begin_ = -1;
405  reach_end_ = -1;
406  reach_weight_ = Weight::Zero();
407  const auto flags = aiter->Flags(); // Save flags to restore them on exit.
408  aiter->SetFlags(kArcNoCache, kArcNoCache); // Makes caching optional.
409  aiter->Seek(aiter_begin);
410  if (2 * (aiter_end - aiter_begin) < interval_set.Size()) {
411  // Checks each arc against intervals, setting arc iterator flags to only
412  // compute the ilabel or olabel values, since they are the only values
413  // required for most of the arcs processed.
414  aiter->SetFlags(reach_fst_input_ ? kArcILabelValue : kArcOLabelValue,
416  Label reach_label = kNoLabel;
417  for (auto aiter_pos = aiter_begin; aiter_pos < aiter_end;
418  aiter->Next(), ++aiter_pos) {
419  const auto &arc = aiter->Value();
420  const auto label = reach_fst_input_ ? arc.ilabel : arc.olabel;
421  if (label == reach_label || Reach(label)) {
422  reach_label = label;
423  if (reach_begin_ < 0) reach_begin_ = aiter_pos;
424  reach_end_ = aiter_pos + 1;
425  if (compute_weight) {
426  if (!(aiter->Flags() & kArcWeightValue)) {
427  // If arc.weight wasn't computed by the call to aiter->Value()
428  // above, we need to call aiter->Value() again after having set
429  // the arc iterator flags to compute the arc weight value.
430  aiter->SetFlags(kArcWeightValue, kArcValueFlags);
431  const auto &arcb = aiter->Value();
432  // Call the accumulator.
433  reach_weight_ = accumulator_->Sum(reach_weight_, arcb.weight);
434  // Only ilabel or olabel required to process the following arcs.
435  aiter->SetFlags(
436  reach_fst_input_ ? kArcILabelValue : kArcOLabelValue,
438  } else {
439  // Calls the accumulator.
440  reach_weight_ = accumulator_->Sum(reach_weight_, arc.weight);
441  }
442  }
443  }
444  }
445  } else {
446  // Checks each interval against arcs.
447  auto begin_low = aiter_begin;
448  auto end_low = aiter_begin;
449  for (const auto &interval : interval_set) {
450  begin_low = lower_bound_(aiter, end_low, aiter_end, interval.begin);
451  end_low = lower_bound_(aiter, begin_low, aiter_end, interval.end);
452  if (end_low - begin_low > 0) {
453  if (reach_begin_ < 0) reach_begin_ = begin_low;
454  reach_end_ = end_low;
455  if (compute_weight) {
456  aiter->SetFlags(kArcWeightValue, kArcValueFlags);
457  reach_weight_ =
458  accumulator_->Sum(reach_weight_, aiter, begin_low, end_low);
459  }
460  }
461  }
462  }
463  aiter->SetFlags(flags, kArcFlags); // Restores original flag values.
464  return reach_begin_ >= 0;
465  }
466 
467  // Returns iterator position of first matching arc.
468  ssize_t ReachBegin() const { return reach_begin_; }
469 
470  // Returns iterator position one past last matching arc.
471  ssize_t ReachEnd() const { return reach_end_; }
472 
473  // Return the sum of the weights for matching arcs. Valid only if
474  // compute_weight was true in Reach() call.
475  Weight ReachWeight() const { return reach_weight_; }
476 
477  // Access to the relabeling map. Excludes epsilon (0) label but
478  // includes kNoLabel that is used internally for super-final
479  // transitions.
480  const std::unordered_map<Label, Label> &Label2Index() const {
481  return *data_->Label2Index();
482  }
483 
484  const Data *GetData() const { return data_.get(); }
485 
486  std::shared_ptr<Data> GetSharedData() const { return data_; }
487 
488  bool Error() const { return error_ || accumulator_->Error(); }
489 
490  private:
491  // Redirects labeled arcs (input or output labels determined by ReachInput())
492  // to new label-specific final states. Each original final state is
493  // redirected via a transition labeled with kNoLabel to a new
494  // kNoLabel-specific final state. Creates super-initial state for all states
495  // with zero in-degree.
496  void TransformFst() {
497  auto ins = fst_->NumStates();
498  auto ons = ins;
499  std::vector<ssize_t> indeg(ins, 0);
500  // Redirects labeled arcs to new final states.
501  for (StateId s = 0; s < ins; ++s) {
502  for (MutableArcIterator<VectorFst<Arc>> aiter(fst_.get(), s);
503  !aiter.Done(); aiter.Next()) {
504  auto arc = aiter.Value();
505  const auto label = data_->ReachInput() ? arc.ilabel : arc.olabel;
506  if (label) {
507  if (auto insert_result = label2state_.emplace(label, ons);
508  insert_result.second) {
509  indeg.push_back(0);
510  ++ons;
511  }
512  arc.nextstate = label2state_[label];
513  aiter.SetValue(arc);
514  }
515  ++indeg[arc.nextstate]; // Finds in-degrees for next step.
516  }
517  // Redirects final weights to new final state.
518  auto final_weight = fst_->Final(s);
519  if (final_weight != Weight::Zero()) {
520  if (auto insert_result = label2state_.emplace(kNoLabel, ons);
521  insert_result.second) {
522  indeg.push_back(0);
523  ++ons;
524  }
525  const auto nextstate = label2state_[kNoLabel];
526  fst_->EmplaceArc(s, kNoLabel, kNoLabel, std::move(final_weight),
527  nextstate);
528  ++indeg[nextstate]; // Finds in-degrees for next step.
529  fst_->SetFinal(s, Weight::Zero());
530  }
531  }
532  // Adds new final states to the FST.
533  while (fst_->NumStates() < ons) {
534  StateId s = fst_->AddState();
535  fst_->SetFinal(s);
536  }
537  // Creates a super-initial state for all states with zero in-degree.
538  const auto start = fst_->AddState();
539  fst_->SetStart(start);
540  for (StateId s = 0; s < start; ++s) {
541  if (indeg[s] == 0) fst_->EmplaceArc(start, 0, 0, s);
542  }
543  }
544 
545  void FindIntervals(StateId ins) {
546  StateReachable<Arc, Label, LabelIntervalSet> state_reachable(*fst_);
547  if (state_reachable.Error()) {
548  error_ = true;
549  return;
550  }
551  auto &state2index = state_reachable.State2Index();
552  auto &interval_sets = *data_->MutableIntervalSets();
553  interval_sets = state_reachable.IntervalSets();
554  interval_sets.resize(ins);
555  auto &label2index = *data_->MutableLabel2Index();
556  for (const auto &kv : label2state_) {
557  Label i = state2index[kv.second];
558  label2index[kv.first] = i;
559  if (kv.first == kNoLabel) data_->SetFinalLabel(i);
560  }
561  label2state_.clear();
562  double nintervals = 0;
563  ssize_t non_intervals = 0;
564  for (StateId s = 0; s < ins; ++s) {
565  nintervals += interval_sets[s].Size();
566  if (interval_sets[s].Size() > 1) {
567  ++non_intervals;
568  VLOG(3) << "state: " << s
569  << " # of intervals: " << interval_sets[s].Size();
570  }
571  }
572  VLOG(2) << "# of states: " << ins;
573  VLOG(2) << "# of intervals: " << nintervals;
574  VLOG(2) << "# of intervals/state: " << nintervals / ins;
575  VLOG(2) << "# of non-interval states: " << non_intervals;
576  }
577 
578  std::unique_ptr<VectorFst<Arc>> fst_;
579  // Current state
580  StateId s_;
581  // Finds final state for a label
582  std::unordered_map<Label, StateId> label2state_;
583  // Iterator position of first match.
584  ssize_t reach_begin_;
585  // Iterator position after last match.
586  ssize_t reach_end_;
587  // Gives weight sum of arc iterator arcs with reachable labels.
588  Weight reach_weight_;
589  // Shareable data between copies.
590  std::shared_ptr<Data> data_;
591  // Sums arc weights.
592  std::unique_ptr<Accumulator> accumulator_;
593  // Functor for computing LowerBound(Iterator*, begin, end, label).
594  LowerBound lower_bound_;
595  // Relabeling map for OOV labels.
596  std::unordered_map<Label, Label> oov_label2index_;
597  double ncalls_ = 0;
598  double nintervals_ = 0;
599  bool reach_fst_input_ = false;
600  bool error_ = false;
601 };
602 
603 } // namespace fst
604 
605 #endif // FST_LABEL_REACHABLE_H_
void Relabel(MutableFst< Arc > *fst, bool relabel_input)
typename Data::LabelIntervalSet LabelIntervalSet
constexpr uint8_t kArcValueFlags
Definition: fst.h:453
typename Arc::Weight Weight
constexpr int kNoLabel
Definition: fst.h:201
const std::unordered_map< Label, Label > * Label2Index() const
const std::vector< ISet > & IntervalSets()
ssize_t ReachEnd() const
constexpr uint8_t kArcNoCache
Definition: fst.h:452
std::shared_ptr< Data > GetSharedData() const
std::vector< Index > & State2Index()
LabelReachable(const LabelReachable &reachable, bool safe=false)
void SetFinalLabel(Label final_label)
typename Arc::Label Label
constexpr uint8_t kArcFlags
Definition: fst.h:455
virtual void SetInputSymbols(const SymbolTable *isyms)=0
bool Reach(Iterator *aiter, ssize_t aiter_begin, ssize_t aiter_end, bool compute_weight)
constexpr uint8_t kArcILabelValue
Definition: fst.h:444
std::unordered_map< Label, Label > * MutableLabel2Index()
std::unique_ptr< T > WrapUnique(T *ptr)
Definition: compat.h:125
void SetState(StateId aiter_s)
constexpr int kNoStateId
Definition: fst.h:202
Label Relabel(Label label)
const Arc & Value() const
Definition: fst.h:537
LabelReachableData(bool reach_input, bool keep_relabel_data=true)
void Relabel(MutableFst< Arc > *fst, const std::vector< std::pair< typename Arc::Label, typename Arc::Label >> &ipairs, const std::vector< std::pair< typename Arc::Label, typename Arc::Label >> &opairs)
Definition: relabel.h:42
void RelabelPairs(std::vector< std::pair< Label, Label >> *pairs, bool avoid_collisions=false)
std::ostream & WriteType(std::ostream &strm, const T t)
Definition: util.h:211
#define FSTERROR()
Definition: util.h:53
void SetFlags(uint8_t flags, uint8_t mask)
Definition: fst.h:571
int NumIntervalSets() const
static LabelReachableData * Read(std::istream &istrm, const FstReadOptions &opts)
void Seek(size_t a)
Definition: fst.h:557
void ArcSort(MutableFst< Arc > *fst, Compare comp)
Definition: arcsort.h:102
constexpr uint64_t kOLabelSorted
Definition: properties.h:98
typename Arc::StateId StateId
LabelReachable(const Fst< Arc > &fst, bool reach_input, std::unique_ptr< Accumulator > accumulator=nullptr, bool keep_relabel_data=true)
constexpr uint8_t kArcOLabelValue
Definition: fst.h:446
#define VLOG(level)
Definition: log.h:50
ssize_t operator()(ArcIterator *aiter, ssize_t aiter_begin, ssize_t aiter_end, Label match_label) const
bool Reach(Label label) const
typename Arc::Label Label
typename LabelIntervalSet::Interval Interval
const Data * GetData() const
Weight ReachWeight() const
bool ReachFinal() const
constexpr uint8_t kArcWeightValue
Definition: fst.h:448
constexpr uint64_t kILabelSorted
Definition: properties.h:93
Label FinalLabel() const
LabelReachable(std::shared_ptr< Data > data, std::unique_ptr< Accumulator > accumulator=nullptr)
ssize_t ReachBegin() const
const std::unordered_map< Label, Label > & Label2Index() const
std::istream & ReadType(std::istream &strm, T *t)
Definition: util.h:65
virtual void SetOutputSymbols(const SymbolTable *osyms)=0
IntInterval< T > Interval
Definition: interval-set.h:125
void SetState(StateId s, StateId aiter_s=kNoStateId)
typename Arc::StateId StateId
std::vector< LabelIntervalSet > * MutableIntervalSets()
void ReachInit(const FST &fst, bool reach_input, bool copy=false)
bool Write(std::ostream &ostrm, const FstWriteOptions &opts) const
bool StateSort(std::vector< IntervalSet< Label >> *interval_sets, const std::vector< StateId > &order)
const LabelIntervalSet & GetIntervalSet(int s) const
typename LabelIntervalSet::Interval Interval
void Init(const FST &fst, bool reach_input, bool is_copy)