FST  openfst-1.8.2.post1
OpenFst Library
linear-fst.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 // Classes for building, storing and representing log-linear models as FSTs.
19 
20 #ifndef FST_EXTENSIONS_LINEAR_LINEAR_FST_H_
21 #define FST_EXTENSIONS_LINEAR_LINEAR_FST_H_
22 
23 #include <algorithm>
24 #include <cstdint>
25 #include <iostream>
26 #include <memory>
27 #include <string>
28 #include <vector>
29 
30 #include <fst/compat.h>
31 #include <fst/log.h>
34 #include <fst/bi-table.h>
35 #include <fst/cache.h>
36 #include <fstream>
37 #include <fst/fst.h>
38 #include <fst/matcher.h>
39 #include <fst/symbol-table.h>
40 
41 namespace fst {
42 
43 // Forward declaration of the specialized matcher for both
44 // LinearTaggerFst and LinearClassifierFst.
45 template <class F>
47 
48 namespace internal {
49 
50 // Implementation class for on-the-fly generated LinearTaggerFst with
51 // special optimization in matching.
52 template <class A>
53 class LinearTaggerFstImpl : public CacheImpl<A> {
54  public:
55  using FstImpl<A>::SetType;
60 
68 
69  typedef A Arc;
70  typedef typename A::Label Label;
71  typedef typename A::Weight Weight;
72  typedef typename A::StateId StateId;
74 
75  // Constructs an empty FST by default.
77  : CacheImpl<A>(CacheOptions()),
78  data_(std::make_shared<LinearFstData<A>>()),
79  delay_(0) {
80  SetType("linear-tagger");
81  }
82 
83  // Constructs the FST with given data storage and symbol
84  // tables.
85  //
86  // TODO(wuke): when there is no constraint on output we can delay
87  // less than `data->MaxFutureSize` positions.
89  const SymbolTable *osyms, CacheOptions opts)
90  : CacheImpl<A>(opts), data_(data), delay_(data->MaxFutureSize()) {
91  SetType("linear-tagger");
93  SetInputSymbols(isyms);
94  SetOutputSymbols(osyms);
95  ReserveStubSpace();
96  }
97 
98  // Copy by sharing the underlying data storage.
100  : CacheImpl<A>(impl), data_(impl.data_), delay_(impl.delay_) {
101  SetType("linear-tagger");
105  ReserveStubSpace();
106  }
107 
108  StateId Start() {
109  if (!HasStart()) {
110  StateId start = FindStartState();
111  SetStart(start);
112  }
113  return CacheImpl<A>::Start();
114  }
115 
116  Weight Final(StateId s) {
117  if (!HasFinal(s)) {
118  state_stub_.clear();
119  FillState(s, &state_stub_);
120  if (CanBeFinal(state_stub_))
121  SetFinal(s, data_->FinalWeight(InternalBegin(state_stub_),
122  InternalEnd(state_stub_)));
123  else
124  SetFinal(s, Weight::Zero());
125  }
126  return CacheImpl<A>::Final(s);
127  }
128 
129  size_t NumArcs(StateId s) {
130  if (!HasArcs(s)) Expand(s);
131  return CacheImpl<A>::NumArcs(s);
132  }
133 
134  size_t NumInputEpsilons(StateId s) {
135  if (!HasArcs(s)) Expand(s);
137  }
138 
139  size_t NumOutputEpsilons(StateId s) {
140  if (!HasArcs(s)) Expand(s);
142  }
143 
144  void InitArcIterator(StateId s, ArcIteratorData<A> *data) {
145  if (!HasArcs(s)) Expand(s);
147  }
148 
149  // Computes the outgoing transitions from a state, creating new
150  // destination states as needed.
151  void Expand(StateId s);
152 
153  // Appends to `arcs` all out-going arcs from state `s` that matches `label` as
154  // the input label.
155  void MatchInput(StateId s, Label ilabel, std::vector<Arc> *arcs);
156 
157  static LinearTaggerFstImpl *Read(std::istream &strm,
158  const FstReadOptions &opts);
159 
160  bool Write(std::ostream &strm, const FstWriteOptions &opts) const {
161  FstHeader header;
162  header.SetStart(kNoStateId);
163  WriteHeader(strm, opts, kFileVersion, &header);
164  data_->Write(strm);
165  if (!strm) {
166  LOG(ERROR) << "LinearTaggerFst::Write: Write failed: " << opts.source;
167  return false;
168  }
169  return true;
170  }
171 
172  private:
173  static constexpr int kMinFileVersion = 1;
174  static constexpr int kFileVersion = 1;
175 
176  // A collection of functions to access parts of the state tuple. A
177  // state tuple is a vector of `Label`s with two parts:
178  // [buffer] [internal].
179  //
180  // - [buffer] is a buffer of observed input labels with length
181  // `delay_`. `LinearFstData<A>::kStartOfSentence`
182  // (resp. `LinearFstData<A>::kEndOfSentence`) are used as
183  // paddings when the buffer has fewer than `delay_` elements, which
184  // can only appear as the prefix (resp. suffix) of the buffer.
185  //
186  // - [internal] is the internal state tuple for `LinearFstData`
187  typename std::vector<Label>::const_iterator BufferBegin(
188  const std::vector<Label> &state) const {
189  return state.begin();
190  }
191 
192  typename std::vector<Label>::const_iterator BufferEnd(
193  const std::vector<Label> &state) const {
194  return state.begin() + delay_;
195  }
196 
197  typename std::vector<Label>::const_iterator InternalBegin(
198  const std::vector<Label> &state) const {
199  return state.begin() + delay_;
200  }
201 
202  typename std::vector<Label>::const_iterator InternalEnd(
203  const std::vector<Label> &state) const {
204  return state.end();
205  }
206 
207  // The size of state tuples are fixed, reserve them in stubs
208  void ReserveStubSpace() {
209  state_stub_.reserve(delay_ + data_->NumGroups());
210  next_stub_.reserve(delay_ + data_->NumGroups());
211  }
212 
213  // Computes the start state tuple and maps it to the start state id.
214  StateId FindStartState() {
215  // Empty buffer with start-of-sentence paddings
216  state_stub_.clear();
217  state_stub_.resize(delay_, LinearFstData<A>::kStartOfSentence);
218  // Append internal states
219  data_->EncodeStartState(&state_stub_);
220  return FindState(state_stub_);
221  }
222 
223  // Tests whether the buffer in `(begin, end)` is empty.
224  bool IsEmptyBuffer(typename std::vector<Label>::const_iterator begin,
225  typename std::vector<Label>::const_iterator end) const {
226  // The following is guanranteed by `ShiftBuffer()`:
227  // - buffer[i] == LinearFstData<A>::kEndOfSentence =>
228  // buffer[i+x] == LinearFstData<A>::kEndOfSentence
229  // - buffer[i] == LinearFstData<A>::kStartOfSentence =>
230  // buffer[i-x] == LinearFstData<A>::kStartOfSentence
231  return delay_ == 0 || *(end - 1) == LinearFstData<A>::kStartOfSentence ||
233  }
234 
235  // Tests whether the given state tuple can be a final state. A state
236  // is final iff there is no observed input in the buffer.
237  bool CanBeFinal(const std::vector<Label> &state) {
238  return IsEmptyBuffer(BufferBegin(state), BufferEnd(state));
239  }
240 
241  // Finds state corresponding to an n-gram. Creates new state if n-gram not
242  // found.
243  StateId FindState(const std::vector<Label> &ngram) {
244  StateId sparse = ngrams_.FindId(ngram, true);
245  StateId dense = condensed_.FindId(sparse, true);
246  return dense;
247  }
248 
249  // Appends after `output` the state tuple corresponding to the state id. The
250  // state id must exist.
251  void FillState(StateId s, std::vector<Label> *output) {
252  s = condensed_.FindEntry(s);
253  for (NGramIterator it = ngrams_.FindSet(s); !it.Done(); it.Next()) {
254  Label label = it.Element();
255  output->push_back(label);
256  }
257  }
258 
259  // Shifts the buffer in `state` by appending `ilabel` and popping
260  // the one in the front as the return value. `next_stub_` is a
261  // shifted buffer of size `delay_` where the first `delay_ - 1`
262  // elements are the last `delay_ - 1` elements in the buffer of
263  // `state`. The last (if any) element in `next_stub_` will be
264  // `ilabel` after the call returns.
265  Label ShiftBuffer(const std::vector<Label> &state, Label ilabel,
266  std::vector<Label> *next_stub_);
267 
268  // Builds an arc from state tuple `state` consuming `ilabel` and
269  // `olabel`. `next_stub_` is the buffer filled in `ShiftBuffer`.
270  Arc MakeArc(const std::vector<Label> &state, Label ilabel, Label olabel,
271  std::vector<Label> *next_stub_);
272 
273  // Expands arcs from state `s`, equivalent to state tuple `state`,
274  // with input `ilabel`. `next_stub_` is the buffer filled in
275  // `ShiftBuffer`.
276  void ExpandArcs(StateId s, const std::vector<Label> &state, Label ilabel,
277  std::vector<Label> *next_stub_);
278 
279  // Appends arcs from state `s`, equivalent to state tuple `state`,
280  // with input `ilabel` to `arcs`. `next_stub_` is the buffer filled
281  // in `ShiftBuffer`.
282  void AppendArcs(StateId s, const std::vector<Label> &state, Label ilabel,
283  std::vector<Label> *next_stub_, std::vector<Arc> *arcs);
284 
285  std::shared_ptr<const LinearFstData<A>> data_;
286  size_t delay_;
287  // Mapping from internal state tuple to *non-consecutive* IDs.
289  // Mapping from non-consecutive id to actual state ID.
291  // Two frequently used vectors, reuse to avoid repeated heap allocation.
292  std::vector<Label> state_stub_;
293  std::vector<Label> next_stub_;
294 
295  LinearTaggerFstImpl &operator=(const LinearTaggerFstImpl &) = delete;
296 };
297 
298 template <class A>
299 inline typename A::Label LinearTaggerFstImpl<A>::ShiftBuffer(
300  const std::vector<Label> &state, Label ilabel,
301  std::vector<Label> *next_stub_) {
302  DCHECK(ilabel > 0 || ilabel == LinearFstData<A>::kEndOfSentence);
303  if (delay_ == 0) {
304  DCHECK_GT(ilabel, 0);
305  return ilabel;
306  } else {
307  (*next_stub_)[BufferEnd(*next_stub_) - next_stub_->begin() - 1] = ilabel;
308  return *BufferBegin(state);
309  }
310 }
311 
312 template <class A>
313 inline A LinearTaggerFstImpl<A>::MakeArc(const std::vector<Label> &state,
314  Label ilabel, Label olabel,
315  std::vector<Label> *next_stub_) {
316  DCHECK(ilabel > 0 || ilabel == LinearFstData<A>::kEndOfSentence);
317  DCHECK(olabel > 0 || olabel == LinearFstData<A>::kStartOfSentence);
318  Weight weight(Weight::One());
319  data_->TakeTransition(BufferEnd(state), InternalBegin(state),
320  InternalEnd(state), ilabel, olabel, next_stub_,
321  &weight);
322  StateId nextstate = FindState(*next_stub_);
323  // Restore `next_stub_` to its size before the call
324  next_stub_->resize(delay_);
325  // In the actual arc, we use epsilons instead of boundaries.
326  return A(ilabel == LinearFstData<A>::kEndOfSentence ? 0 : ilabel,
327  olabel == LinearFstData<A>::kStartOfSentence ? 0 : olabel, weight,
328  nextstate);
329 }
330 
331 template <class A>
333  const std::vector<Label> &state,
334  Label ilabel,
335  std::vector<Label> *next_stub_) {
336  // Input label to constrain the output with, observed `delay_` steps
337  // back. `ilabel` is the input label to be put on the arc, which
338  // fires features.
339  Label obs_ilabel = ShiftBuffer(state, ilabel, next_stub_);
340  if (obs_ilabel == LinearFstData<A>::kStartOfSentence) {
341  // This happens when input is shorter than `delay_`.
342  PushArc(s, MakeArc(state, ilabel, LinearFstData<A>::kStartOfSentence,
343  next_stub_));
344  } else {
345  std::pair<typename std::vector<typename A::Label>::const_iterator,
346  typename std::vector<typename A::Label>::const_iterator>
347  range = data_->PossibleOutputLabels(obs_ilabel);
348  for (typename std::vector<typename A::Label>::const_iterator it =
349  range.first;
350  it != range.second; ++it)
351  PushArc(s, MakeArc(state, ilabel, *it, next_stub_));
352  }
353 }
354 
355 // TODO(wuke): this has much in duplicate with `ExpandArcs()`
356 template <class A>
358  const std::vector<Label> &state,
359  Label ilabel,
360  std::vector<Label> *next_stub_,
361  std::vector<Arc> *arcs) {
362  // Input label to constrain the output with, observed `delay_` steps
363  // back. `ilabel` is the input label to be put on the arc, which
364  // fires features.
365  Label obs_ilabel = ShiftBuffer(state, ilabel, next_stub_);
366  if (obs_ilabel == LinearFstData<A>::kStartOfSentence) {
367  // This happens when input is shorter than `delay_`.
368  arcs->push_back(
369  MakeArc(state, ilabel, LinearFstData<A>::kStartOfSentence, next_stub_));
370  } else {
371  std::pair<typename std::vector<typename A::Label>::const_iterator,
372  typename std::vector<typename A::Label>::const_iterator>
373  range = data_->PossibleOutputLabels(obs_ilabel);
374  for (typename std::vector<typename A::Label>::const_iterator it =
375  range.first;
376  it != range.second; ++it)
377  arcs->push_back(MakeArc(state, ilabel, *it, next_stub_));
378  }
379 }
380 
381 template <class A>
383  VLOG(3) << "Expand " << s;
384  state_stub_.clear();
385  FillState(s, &state_stub_);
386 
387  // Precompute the first `delay_ - 1` elements in the buffer of
388  // next states, which are identical for different input/output.
389  next_stub_.clear();
390  next_stub_.resize(delay_);
391  if (delay_ > 0)
392  std::copy(BufferBegin(state_stub_) + 1, BufferEnd(state_stub_),
393  next_stub_.begin());
394 
395  // Epsilon transition for flushing out the next observed input
396  if (!IsEmptyBuffer(BufferBegin(state_stub_), BufferEnd(state_stub_)))
397  ExpandArcs(s, state_stub_, LinearFstData<A>::kEndOfSentence, &next_stub_);
398 
399  // Non-epsilon input when we haven't flushed
400  if (delay_ == 0 ||
401  *(BufferEnd(state_stub_) - 1) != LinearFstData<A>::kEndOfSentence) {
402  for (Label ilabel = data_->MinInputLabel();
403  ilabel <= data_->MaxInputLabel(); ++ilabel) {
404  ExpandArcs(s, state_stub_, ilabel, &next_stub_);
405  }
406  }
407 
408  SetArcs(s);
409 }
410 
411 template <class A>
413  std::vector<Arc> *arcs) {
414  state_stub_.clear();
415  FillState(s, &state_stub_);
416 
417  // Precompute the first `delay_ - 1` elements in the buffer of
418  // next states, which are identical for different input/output.
419  next_stub_.clear();
420  next_stub_.resize(delay_);
421  if (delay_ > 0)
422  std::copy(BufferBegin(state_stub_) + 1, BufferEnd(state_stub_),
423  next_stub_.begin());
424 
425  if (ilabel == 0) {
426  // Epsilon transition for flushing out the next observed input
427  if (!IsEmptyBuffer(BufferBegin(state_stub_), BufferEnd(state_stub_)))
428  AppendArcs(s, state_stub_, LinearFstData<A>::kEndOfSentence, &next_stub_,
429  arcs);
430  } else {
431  // Non-epsilon input when we haven't flushed
432  if (delay_ == 0 ||
433  *(BufferEnd(state_stub_) - 1) != LinearFstData<A>::kEndOfSentence)
434  AppendArcs(s, state_stub_, ilabel, &next_stub_, arcs);
435  }
436 }
437 
438 template <class A>
440  std::istream &strm, const FstReadOptions &opts) {
441  std::unique_ptr<LinearTaggerFstImpl<A>> impl(new LinearTaggerFstImpl<A>());
442  FstHeader header;
443  if (!impl->ReadHeader(strm, opts, kMinFileVersion, &header)) {
444  return nullptr;
445  }
446  impl->data_ = std::shared_ptr<LinearFstData<A>>(LinearFstData<A>::Read(strm));
447  if (!impl->data_) {
448  return nullptr;
449  }
450  impl->delay_ = impl->data_->MaxFutureSize();
451  impl->ReserveStubSpace();
452  return impl.release();
453 }
454 
455 } // namespace internal
456 
457 // This class attaches interface to implementation and handles
458 // reference counting, delegating most methods to ImplToFst.
459 template <class A>
460 class LinearTaggerFst : public ImplToFst<internal::LinearTaggerFstImpl<A>> {
461  public:
462  friend class ArcIterator<LinearTaggerFst<A>>;
463  friend class StateIterator<LinearTaggerFst<A>>;
465 
466  typedef A Arc;
467  typedef typename A::Label Label;
468  typedef typename A::Weight Weight;
469  typedef typename A::StateId StateId;
471  typedef typename Store::State State;
473 
474  LinearTaggerFst() : ImplToFst<Impl>(std::make_shared<Impl>()) {}
475 
477  const SymbolTable *isyms = nullptr,
478  const SymbolTable *osyms = nullptr,
479  CacheOptions opts = CacheOptions())
480  : ImplToFst<Impl>(std::make_shared<Impl>(data, isyms, osyms, opts)) {}
481 
482  explicit LinearTaggerFst(const Fst<A> &fst)
483  : ImplToFst<Impl>(std::make_shared<Impl>()) {
484  LOG(FATAL) << "LinearTaggerFst: no constructor from arbitrary FST.";
485  }
486 
487  // See Fst<>::Copy() for doc.
488  LinearTaggerFst(const LinearTaggerFst<A> &fst, bool safe = false)
489  : ImplToFst<Impl>(fst, safe) {}
490 
491  // Get a copy of this LinearTaggerFst. See Fst<>::Copy() for further doc.
492  LinearTaggerFst<A> *Copy(bool safe = false) const override {
493  return new LinearTaggerFst<A>(*this, safe);
494  }
495 
496  inline void InitStateIterator(StateIteratorData<A> *data) const override;
497 
498  void InitArcIterator(StateId s, ArcIteratorData<A> *data) const override {
499  GetMutableImpl()->InitArcIterator(s, data);
500  }
501 
502  MatcherBase<A> *InitMatcher(MatchType match_type) const override {
503  return new LinearFstMatcherTpl<LinearTaggerFst<A>>(this, match_type);
504  }
505 
506  static LinearTaggerFst<A> *Read(const std::string &source) {
507  if (!source.empty()) {
508  std::ifstream strm(source,
509  std::ios_base::in | std::ios_base::binary);
510  if (!strm) {
511  LOG(ERROR) << "LinearTaggerFst::Read: Can't open file: " << source;
512  return nullptr;
513  }
514  return Read(strm, FstReadOptions(source));
515  } else {
516  return Read(std::cin, FstReadOptions("standard input"));
517  }
518  }
519 
520  static LinearTaggerFst<A> *Read(std::istream &in,
521  const FstReadOptions &opts) {
522  auto *impl = Impl::Read(in, opts);
523  return impl ? new LinearTaggerFst<A>(std::shared_ptr<Impl>(impl)) : nullptr;
524  }
525 
526  bool Write(const std::string &source) const override {
527  if (!source.empty()) {
528  std::ofstream strm(source,
529  std::ios_base::out | std::ios_base::binary);
530  if (!strm) {
531  LOG(ERROR) << "LinearTaggerFst::Write: Can't open file: " << source;
532  return false;
533  }
534  return Write(strm, FstWriteOptions(source));
535  } else {
536  return Write(std::cout, FstWriteOptions("standard output"));
537  }
538  }
539 
540  bool Write(std::ostream &strm, const FstWriteOptions &opts) const override {
541  return GetImpl()->Write(strm, opts);
542  }
543 
544  private:
547 
548  explicit LinearTaggerFst(std::shared_ptr<Impl> impl)
549  : ImplToFst<Impl>(impl) {}
550 
551  void operator=(const LinearTaggerFst<A> &fst) = delete;
552 };
553 
554 // Specialization for LinearTaggerFst.
555 template <class Arc>
557  : public CacheStateIterator<LinearTaggerFst<Arc>> {
558  public:
560  : CacheStateIterator<LinearTaggerFst<Arc>>(fst, fst.GetMutableImpl()) {}
561 };
562 
563 // Specialization for LinearTaggerFst.
564 template <class Arc>
566  : public CacheArcIterator<LinearTaggerFst<Arc>> {
567  public:
568  using StateId = typename Arc::StateId;
569 
571  : CacheArcIterator<LinearTaggerFst<Arc>>(fst.GetMutableImpl(), s) {
572  if (!fst.GetImpl()->HasArcs(s)) fst.GetMutableImpl()->Expand(s);
573  }
574 };
575 
576 template <class Arc>
578  StateIteratorData<Arc> *data) const {
579  data->base = std::make_unique<StateIterator<LinearTaggerFst<Arc>>>(*this);
580 }
581 
582 namespace internal {
583 
584 // Implementation class for on-the-fly generated LinearClassifierFst with
585 // special optimization in matching.
586 template <class A>
588  public:
589  using FstImpl<A>::SetType;
594 
602 
603  typedef A Arc;
604  typedef typename A::Label Label;
605  typedef typename A::Weight Weight;
606  typedef typename A::StateId StateId;
608 
609  // Constructs an empty FST by default.
611  : CacheImpl<A>(CacheOptions()),
612  data_(std::make_shared<LinearFstData<A>>()) {
613  SetType("linear-classifier");
614  num_classes_ = 0;
615  num_groups_ = 0;
616  }
617 
618  // Constructs the FST with given data storage, number of classes and
619  // symbol tables.
620  LinearClassifierFstImpl(const LinearFstData<Arc> *data, size_t num_classes,
621  const SymbolTable *isyms, const SymbolTable *osyms,
622  CacheOptions opts)
623  : CacheImpl<A>(opts),
624  data_(data),
625  num_classes_(num_classes),
626  num_groups_(data_->NumGroups() / num_classes_) {
627  SetType("linear-classifier");
629  SetInputSymbols(isyms);
630  SetOutputSymbols(osyms);
631  ReserveStubSpace();
632  }
633 
634  // Copy by sharing the underlying data storage.
636  : CacheImpl<A>(impl),
637  data_(impl.data_),
638  num_classes_(impl.num_classes_),
639  num_groups_(impl.num_groups_) {
640  SetType("linear-classifier");
644  ReserveStubSpace();
645  }
646 
647  StateId Start() {
648  if (!HasStart()) {
649  StateId start = FindStartState();
650  SetStart(start);
651  }
652  return CacheImpl<A>::Start();
653  }
654 
655  Weight Final(StateId s) {
656  if (!HasFinal(s)) {
657  state_stub_.clear();
658  FillState(s, &state_stub_);
659  SetFinal(s, FinalWeight(state_stub_));
660  }
661  return CacheImpl<A>::Final(s);
662  }
663 
664  size_t NumArcs(StateId s) {
665  if (!HasArcs(s)) Expand(s);
666  return CacheImpl<A>::NumArcs(s);
667  }
668 
669  size_t NumInputEpsilons(StateId s) {
670  if (!HasArcs(s)) Expand(s);
672  }
673 
674  size_t NumOutputEpsilons(StateId s) {
675  if (!HasArcs(s)) Expand(s);
677  }
678 
679  void InitArcIterator(StateId s, ArcIteratorData<A> *data) {
680  if (!HasArcs(s)) Expand(s);
682  }
683 
684  // Computes the outgoing transitions from a state, creating new
685  // destination states as needed.
686  void Expand(StateId s);
687 
688  // Appends to `arcs` all out-going arcs from state `s` that matches
689  // `label` as the input label.
690  void MatchInput(StateId s, Label ilabel, std::vector<Arc> *arcs);
691 
692  static LinearClassifierFstImpl<A> *Read(std::istream &strm,
693  const FstReadOptions &opts);
694 
695  bool Write(std::ostream &strm, const FstWriteOptions &opts) const {
696  FstHeader header;
697  header.SetStart(kNoStateId);
698  WriteHeader(strm, opts, kFileVersion, &header);
699  data_->Write(strm);
700  WriteType(strm, num_classes_);
701  if (!strm) {
702  LOG(ERROR) << "LinearClassifierFst::Write: Write failed: " << opts.source;
703  return false;
704  }
705  return true;
706  }
707 
708  private:
709  static constexpr int kMinFileVersion = 0;
710  static constexpr int kFileVersion = 0;
711 
712  // A collection of functions to access parts of the state tuple. A
713  // state tuple is a vector of `Label`s with two parts:
714  // [prediction] [internal].
715  //
716  // - [prediction] is a single label of the predicted class. A state
717  // must have a positive class label, unless it is the start state.
718  //
719  // - [internal] is the internal state tuple for `LinearFstData` of
720  // the given class; or kNoTrieNodeId's if in start state.
721  Label &Prediction(std::vector<Label> &state) { return state[0]; }
722  Label Prediction(const std::vector<Label> &state) const { return state[0]; }
723 
724  Label &InternalAt(std::vector<Label> &state, int index) {
725  return state[index + 1];
726  }
727  Label InternalAt(const std::vector<Label> &state, int index) const {
728  return state[index + 1];
729  }
730 
731  // The size of state tuples are fixed, reserve them in stubs
732  void ReserveStubSpace() {
733  size_t size = 1 + num_groups_;
734  state_stub_.reserve(size);
735  next_stub_.reserve(size);
736  }
737 
738  // Computes the start state tuple and maps it to the start state id.
739  StateId FindStartState() {
740  // A start state tuple has no prediction
741  state_stub_.clear();
742  state_stub_.push_back(kNoLabel);
743  // For a start state, we don't yet know where we are in the tries.
744  for (size_t i = 0; i < num_groups_; ++i)
745  state_stub_.push_back(kNoTrieNodeId);
746  return FindState(state_stub_);
747  }
748 
749  // Tests if the state tuple represents the start state.
750  bool IsStartState(const std::vector<Label> &state) const {
751  return state[0] == kNoLabel;
752  }
753 
754  // Computes the actual group id in the data storage.
755  int GroupId(Label pred, int group) const {
756  return group * num_classes_ + pred - 1;
757  }
758 
759  // Finds out the final weight of the given state. A state is final
760  // iff it is not the start.
761  Weight FinalWeight(const std::vector<Label> &state) const {
762  if (IsStartState(state)) {
763  return Weight::Zero();
764  }
765  Label pred = Prediction(state);
766  DCHECK_GT(pred, 0);
767  DCHECK_LE(pred, num_classes_);
768  Weight final_weight = Weight::One();
769  for (size_t group = 0; group < num_groups_; ++group) {
770  int group_id = GroupId(pred, group);
771  int trie_state = InternalAt(state, group);
772  final_weight =
773  Times(final_weight, data_->GroupFinalWeight(group_id, trie_state));
774  }
775  return final_weight;
776  }
777 
778  // Finds state corresponding to an n-gram. Creates new state if n-gram not
779  // found.
780  StateId FindState(const std::vector<Label> &ngram) {
781  StateId sparse = ngrams_.FindId(ngram, true);
782  StateId dense = condensed_.FindId(sparse, true);
783  return dense;
784  }
785 
786  // Appends after `output` the state tuple corresponding to the state id. The
787  // state id must exist.
788  void FillState(StateId s, std::vector<Label> *output) {
789  s = condensed_.FindEntry(s);
790  for (NGramIterator it = ngrams_.FindSet(s); !it.Done(); it.Next()) {
791  output->emplace_back(it.Element());
792  }
793  }
794 
795  std::shared_ptr<const LinearFstData<A>> data_;
796  // Division of groups in `data_`; num_classes_ * num_groups_ ==
797  // data_->NumGroups().
798  size_t num_classes_;
799  size_t num_groups_;
800  // Mapping from internal state tuple to *non-consecutive* IDs.
802  // Mapping from non-consecutive id to actual state ID.
804  // Two frequently used vectors, reuse to avoid repeated heap allocation.
805  std::vector<Label> state_stub_;
806  std::vector<Label> next_stub_;
807 
808  void operator=(const LinearClassifierFstImpl<A> &) = delete;
809 };
810 
811 template <class A>
813  VLOG(3) << "Expand " << s;
814  state_stub_.clear();
815  FillState(s, &state_stub_);
816  next_stub_.clear();
817  next_stub_.resize(1 + num_groups_);
818 
819  if (IsStartState(state_stub_)) {
820  // Make prediction
821  for (Label pred = 1; pred <= num_classes_; ++pred) {
822  Prediction(next_stub_) = pred;
823  for (int i = 0; i < num_groups_; ++i)
824  InternalAt(next_stub_, i) = data_->GroupStartState(GroupId(pred, i));
825  PushArc(s, A(0, pred, Weight::One(), FindState(next_stub_)));
826  }
827  } else {
828  Label pred = Prediction(state_stub_);
829  DCHECK_GT(pred, 0);
830  DCHECK_LE(pred, num_classes_);
831  for (Label ilabel = data_->MinInputLabel();
832  ilabel <= data_->MaxInputLabel(); ++ilabel) {
833  Prediction(next_stub_) = pred;
834  Weight weight = Weight::One();
835  for (int i = 0; i < num_groups_; ++i)
836  InternalAt(next_stub_, i) =
837  data_->GroupTransition(GroupId(pred, i), InternalAt(state_stub_, i),
838  ilabel, pred, &weight);
839  PushArc(s, A(ilabel, 0, weight, FindState(next_stub_)));
840  }
841  }
842 
843  SetArcs(s);
844 }
845 
846 template <class A>
847 void LinearClassifierFstImpl<A>::MatchInput(StateId s, Label ilabel,
848  std::vector<Arc> *arcs) {
849  state_stub_.clear();
850  FillState(s, &state_stub_);
851  next_stub_.clear();
852  next_stub_.resize(1 + num_groups_);
853 
854  if (IsStartState(state_stub_)) {
855  // Make prediction if `ilabel` is epsilon.
856  if (ilabel == 0) {
857  for (Label pred = 1; pred <= num_classes_; ++pred) {
858  Prediction(next_stub_) = pred;
859  for (int i = 0; i < num_groups_; ++i)
860  InternalAt(next_stub_, i) = data_->GroupStartState(GroupId(pred, i));
861  arcs->push_back(A(0, pred, Weight::One(), FindState(next_stub_)));
862  }
863  }
864  } else if (ilabel != 0) {
865  Label pred = Prediction(state_stub_);
866  Weight weight = Weight::One();
867  Prediction(next_stub_) = pred;
868  for (int i = 0; i < num_groups_; ++i)
869  InternalAt(next_stub_, i) = data_->GroupTransition(
870  GroupId(pred, i), InternalAt(state_stub_, i), ilabel, pred, &weight);
871  arcs->push_back(A(ilabel, 0, weight, FindState(next_stub_)));
872  }
873 }
874 
875 template <class A>
877  std::istream &strm, const FstReadOptions &opts) {
878  std::unique_ptr<LinearClassifierFstImpl<A>> impl(
880  FstHeader header;
881  if (!impl->ReadHeader(strm, opts, kMinFileVersion, &header)) {
882  return nullptr;
883  }
884  impl->data_ = std::shared_ptr<LinearFstData<A>>(LinearFstData<A>::Read(strm));
885  if (!impl->data_) {
886  return nullptr;
887  }
888  ReadType(strm, &impl->num_classes_);
889  if (!strm) {
890  return nullptr;
891  }
892  impl->num_groups_ = impl->data_->NumGroups() / impl->num_classes_;
893  if (impl->num_groups_ * impl->num_classes_ != impl->data_->NumGroups()) {
894  FSTERROR() << "Total number of feature groups is not a multiple of the "
895  "number of classes: num groups = "
896  << impl->data_->NumGroups()
897  << ", num classes = " << impl->num_classes_;
898  return nullptr;
899  }
900  impl->ReserveStubSpace();
901  return impl.release();
902 }
903 
904 } // namespace internal
905 
906 // This class attaches interface to implementation and handles
907 // reference counting, delegating most methods to ImplToFst.
908 template <class A>
910  : public ImplToFst<internal::LinearClassifierFstImpl<A>> {
911  public:
915 
916  typedef A Arc;
917  typedef typename A::Label Label;
918  typedef typename A::Weight Weight;
919  typedef typename A::StateId StateId;
921  typedef typename Store::State State;
923 
924  LinearClassifierFst() : ImplToFst<Impl>(std::make_shared<Impl>()) {}
925 
926  explicit LinearClassifierFst(LinearFstData<A> *data, size_t num_classes,
927  const SymbolTable *isyms = nullptr,
928  const SymbolTable *osyms = nullptr,
929  CacheOptions opts = CacheOptions())
930  : ImplToFst<Impl>(
931  std::make_shared<Impl>(data, num_classes, isyms, osyms, opts)) {}
932 
933  explicit LinearClassifierFst(const Fst<A> &fst)
934  : ImplToFst<Impl>(std::make_shared<Impl>()) {
935  LOG(FATAL) << "LinearClassifierFst: no constructor from arbitrary FST.";
936  }
937 
938  // See Fst<>::Copy() for doc.
939  LinearClassifierFst(const LinearClassifierFst<A> &fst, bool safe = false)
940  : ImplToFst<Impl>(fst, safe) {}
941 
942  // Get a copy of this LinearClassifierFst. See Fst<>::Copy() for further doc.
943  LinearClassifierFst<A> *Copy(bool safe = false) const override {
944  return new LinearClassifierFst<A>(*this, safe);
945  }
946 
947  inline void InitStateIterator(StateIteratorData<A> *data) const override;
948 
949  void InitArcIterator(StateId s, ArcIteratorData<A> *data) const override {
950  GetMutableImpl()->InitArcIterator(s, data);
951  }
952 
953  MatcherBase<A> *InitMatcher(MatchType match_type) const override {
954  return new LinearFstMatcherTpl<LinearClassifierFst<A>>(this, match_type);
955  }
956 
957  static LinearClassifierFst<A> *Read(const std::string &source) {
958  if (!source.empty()) {
959  std::ifstream strm(source,
960  std::ios_base::in | std::ios_base::binary);
961  if (!strm) {
962  LOG(ERROR) << "LinearClassifierFst::Read: Can't open file: " << source;
963  return nullptr;
964  }
965  return Read(strm, FstReadOptions(source));
966  } else {
967  return Read(std::cin, FstReadOptions("standard input"));
968  }
969  }
970 
971  static LinearClassifierFst<A> *Read(std::istream &in,
972  const FstReadOptions &opts) {
973  auto *impl = Impl::Read(in, opts);
974  return impl ? new LinearClassifierFst<A>(std::shared_ptr<Impl>(impl))
975  : nullptr;
976  }
977 
978  bool Write(const std::string &source) const override {
979  if (!source.empty()) {
980  std::ofstream strm(source,
981  std::ios_base::out | std::ios_base::binary);
982  if (!strm) {
983  LOG(ERROR) << "ProdLmFst::Write: Can't open file: " << source;
984  return false;
985  }
986  return Write(strm, FstWriteOptions(source));
987  } else {
988  return Write(std::cout, FstWriteOptions("standard output"));
989  }
990  }
991 
992  bool Write(std::ostream &strm, const FstWriteOptions &opts) const override {
993  return GetImpl()->Write(strm, opts);
994  }
995 
996  private:
999 
1000  explicit LinearClassifierFst(std::shared_ptr<Impl> impl)
1001  : ImplToFst<Impl>(impl) {}
1002 
1003  void operator=(const LinearClassifierFst<A> &fst) = delete;
1004 };
1005 
1006 // Specialization for LinearClassifierFst.
1007 template <class Arc>
1009  : public CacheStateIterator<LinearClassifierFst<Arc>> {
1010  public:
1013  fst.GetMutableImpl()) {}
1014 };
1015 
1016 // Specialization for LinearClassifierFst.
1017 template <class Arc>
1019  : public CacheArcIterator<LinearClassifierFst<Arc>> {
1020  public:
1021  using StateId = typename Arc::StateId;
1022 
1024  : CacheArcIterator<LinearClassifierFst<Arc>>(fst.GetMutableImpl(), s) {
1025  if (!fst.GetImpl()->HasArcs(s)) fst.GetMutableImpl()->Expand(s);
1026  }
1027 };
1028 
1029 template <class Arc>
1031  StateIteratorData<Arc> *data) const {
1032  data->base =
1033  std::make_unique<StateIterator<LinearClassifierFst<Arc>>>(*this);
1034 }
1035 
1036 // Specialized Matcher for LinearFsts. This matcher only supports
1037 // matching from the input side. This is intentional because comparing
1038 // the scores of different input sequences with the same output
1039 // sequence is meaningless in a discriminative model.
1040 template <class F>
1041 class LinearFstMatcherTpl : public MatcherBase<typename F::Arc> {
1042  public:
1043  typedef typename F::Arc Arc;
1044  typedef typename Arc::Label Label;
1045  typedef typename Arc::Weight Weight;
1046  typedef typename Arc::StateId StateId;
1047  typedef F FST;
1048 
1049  // This makes a copy of the FST.
1050  LinearFstMatcherTpl(const FST &fst, MatchType match_type)
1051  : owned_fst_(fst.Copy()),
1052  fst_(*owned_fst_),
1053  match_type_(match_type),
1054  s_(kNoStateId),
1055  current_loop_(false),
1056  loop_(kNoLabel, 0, Weight::One(), kNoStateId),
1057  cur_arc_(0),
1058  error_(false) {
1059  switch (match_type_) {
1060  case MATCH_INPUT:
1061  case MATCH_OUTPUT:
1062  case MATCH_NONE:
1063  break;
1064  default:
1065  FSTERROR() << "LinearFstMatcherTpl: Bad match type";
1066  match_type_ = MATCH_NONE;
1067  error_ = true;
1068  }
1069  }
1070 
1071  // This doesn't copy the FST.
1072  LinearFstMatcherTpl(const FST *fst, MatchType match_type)
1073  : fst_(*fst),
1074  match_type_(match_type),
1075  s_(kNoStateId),
1076  current_loop_(false),
1077  loop_(kNoLabel, 0, Weight::One(), kNoStateId),
1078  cur_arc_(0),
1079  error_(false) {
1080  switch (match_type_) {
1081  case MATCH_INPUT:
1082  case MATCH_OUTPUT:
1083  case MATCH_NONE:
1084  break;
1085  default:
1086  FSTERROR() << "LinearFstMatcherTpl: Bad match type";
1087  match_type_ = MATCH_NONE;
1088  error_ = true;
1089  }
1090  }
1091 
1092  // This makes a copy of the FST.
1093  LinearFstMatcherTpl(const LinearFstMatcherTpl<F> &matcher, bool safe = false)
1094  : owned_fst_(matcher.fst_.Copy(safe)),
1095  fst_(*owned_fst_),
1096  match_type_(matcher.match_type_),
1097  s_(kNoStateId),
1098  current_loop_(false),
1099  loop_(matcher.loop_),
1100  cur_arc_(0),
1101  error_(matcher.error_) {}
1102 
1103  LinearFstMatcherTpl<F> *Copy(bool safe = false) const override {
1104  return new LinearFstMatcherTpl<F>(*this, safe);
1105  }
1106 
1107  MatchType Type(bool /*test*/) const override {
1108  // `MATCH_INPUT` is the only valid type
1109  return match_type_ == MATCH_INPUT ? match_type_ : MATCH_NONE;
1110  }
1111 
1112  void SetState(StateId s) final {
1113  if (s_ == s) return;
1114  s_ = s;
1115  // `MATCH_INPUT` is the only valid type
1116  if (match_type_ != MATCH_INPUT) {
1117  FSTERROR() << "LinearFstMatcherTpl: Bad match type";
1118  error_ = true;
1119  }
1120  loop_.nextstate = s;
1121  }
1122 
1123  bool Find(Label label) final {
1124  if (error_) {
1125  current_loop_ = false;
1126  return false;
1127  }
1128  current_loop_ = label == 0;
1129  if (label == kNoLabel) label = 0;
1130  arcs_.clear();
1131  cur_arc_ = 0;
1132  fst_.GetMutableImpl()->MatchInput(s_, label, &arcs_);
1133  return current_loop_ || !arcs_.empty();
1134  }
1135 
1136  bool Done() const final {
1137  return !(current_loop_ || cur_arc_ < arcs_.size());
1138  }
1139 
1140  const Arc &Value() const final {
1141  return current_loop_ ? loop_ : arcs_[cur_arc_];
1142  }
1143 
1144  void Next() final {
1145  if (current_loop_)
1146  current_loop_ = false;
1147  else
1148  ++cur_arc_;
1149  }
1150 
1151  ssize_t Priority(StateId s) final { return kRequirePriority; }
1152 
1153  const FST &GetFst() const override { return fst_; }
1154 
1155  uint64_t Properties(uint64_t props) const override {
1156  if (error_) props |= kError;
1157  return props;
1158  }
1159 
1160  uint32_t Flags() const override { return kRequireMatch; }
1161 
1162  private:
1163  std::unique_ptr<const FST> owned_fst_;
1164  const FST &fst_;
1165  MatchType match_type_; // Type of match to perform.
1166  StateId s_; // Current state.
1167  bool current_loop_; // Current arc is the implicit loop.
1168  Arc loop_; // For non-consuming symbols.
1169  // All out-going arcs matching the label in last Find() call.
1170  std::vector<Arc> arcs_;
1171  size_t cur_arc_; // Index to the arc that `Value()` should return.
1172  bool error_; // Error encountered.
1173 };
1174 
1175 } // namespace fst
1176 
1177 #endif // FST_EXTENSIONS_LINEAR_LINEAR_FST_H_
void InitStateIterator(StateIteratorData< A > *data) const override
Definition: linear-fst.h:577
void InitArcIterator(StateId s, ArcIteratorData< A > *data) const override
Definition: linear-fst.h:949
LinearClassifierFst(const Fst< A > &fst)
Definition: linear-fst.h:933
Store::State State
Definition: linear-fst.h:471
constexpr ssize_t kRequirePriority
Definition: matcher.h:128
LinearTaggerFstImpl(const LinearFstData< Arc > *data, const SymbolTable *isyms, const SymbolTable *osyms, CacheOptions opts)
Definition: linear-fst.h:88
constexpr int kNoLabel
Definition: fst.h:201
I FindId(const std::vector< T > &set, bool insert=true)
Definition: collection.h:84
SetIterator FindSet(I id)
Definition: collection.h:96
bool Write(std::ostream &strm, const FstWriteOptions &opts) const
Definition: linear-fst.h:695
DefaultCacheStore< A > Store
Definition: linear-fst.h:920
DefaultCacheStore< A > Store
Definition: linear-fst.h:470
void SetFinal(StateId s, Weight weight=Weight::One())
Definition: cache.h:923
LinearFstMatcherTpl(const FST *fst, MatchType match_type)
Definition: linear-fst.h:1072
uint64_t Properties(uint64_t props) const override
Definition: linear-fst.h:1155
const SymbolTable * OutputSymbols() const
Definition: fst.h:762
MatchType
Definition: fst.h:193
ErrorWeight Times(const ErrorWeight &, const ErrorWeight &)
Definition: error-weight.h:63
constexpr uint64_t kError
Definition: properties.h:51
const T & FindEntry(I s) const
Definition: bi-table.h:177
bool Find(Label label) final
Definition: linear-fst.h:1123
static LinearClassifierFst< A > * Read(std::istream &in, const FstReadOptions &opts)
Definition: linear-fst.h:971
LinearClassifierFstImpl(const LinearFstData< Arc > *data, size_t num_classes, const SymbolTable *isyms, const SymbolTable *osyms, CacheOptions opts)
Definition: linear-fst.h:620
LinearFstMatcherTpl(const LinearFstMatcherTpl< F > &matcher, bool safe=false)
Definition: linear-fst.h:1093
#define LOG(type)
Definition: log.h:49
uint32_t Flags() const override
Definition: linear-fst.h:1160
void SetState(StateId s) final
Definition: linear-fst.h:1112
void MatchInput(StateId s, Label ilabel, std::vector< Arc > *arcs)
Definition: linear-fst.h:412
void InitArcIterator(StateId s, ArcIteratorData< A > *data) const override
Definition: linear-fst.h:498
void SetOutputSymbols(const SymbolTable *osyms)
Definition: fst.h:772
LinearClassifierFst(LinearFstData< A > *data, size_t num_classes, const SymbolTable *isyms=nullptr, const SymbolTable *osyms=nullptr, CacheOptions opts=CacheOptions())
Definition: linear-fst.h:926
Collection< StateId, Label >::SetIterator NGramIterator
Definition: linear-fst.h:607
#define DCHECK_GT(x, y)
Definition: log.h:73
LinearTaggerFst(LinearFstData< A > *data, const SymbolTable *isyms=nullptr, const SymbolTable *osyms=nullptr, CacheOptions opts=CacheOptions())
Definition: linear-fst.h:476
constexpr int kNoStateId
Definition: fst.h:202
MatcherBase< A > * InitMatcher(MatchType match_type) const override
Definition: linear-fst.h:953
LinearClassifierFst(const LinearClassifierFst< A > &fst, bool safe=false)
Definition: linear-fst.h:939
bool Done() const final
Definition: linear-fst.h:1136
static LinearTaggerFstImpl * Read(std::istream &strm, const FstReadOptions &opts)
Definition: linear-fst.h:439
std::ostream & WriteType(std::ostream &strm, const T t)
Definition: util.h:214
std::string source
Definition: fst.h:102
#define FSTERROR()
Definition: util.h:53
ssize_t Priority(StateId s) final
Definition: linear-fst.h:1151
static LinearClassifierFst< A > * Read(const std::string &source)
Definition: linear-fst.h:957
StateIterator(const LinearTaggerFst< Arc > &fst)
Definition: linear-fst.h:559
size_t NumOutputEpsilons(StateId s)
Definition: linear-fst.h:139
virtual uint64_t Properties() const
Definition: fst.h:702
LinearTaggerFst(const LinearTaggerFst< A > &fst, bool safe=false)
Definition: linear-fst.h:488
const FST & GetFst() const override
Definition: linear-fst.h:1153
LinearTaggerFst(const Fst< A > &fst)
Definition: linear-fst.h:482
constexpr uint64_t kCopyProperties
Definition: properties.h:162
MatchType Type(bool) const override
Definition: linear-fst.h:1107
typename FirstCacheStore< VectorCacheStore< CacheState< Arc > > >::State State
Definition: cache.h:666
bool Write(const std::string &source) const override
Definition: linear-fst.h:526
LinearClassifierFst< A > * Copy(bool safe=false) const override
Definition: linear-fst.h:943
StateIterator(const LinearClassifierFst< Arc > &fst)
Definition: linear-fst.h:1011
ArcIterator(const LinearClassifierFst< Arc > &fst, StateId s)
Definition: linear-fst.h:1023
MatcherBase< A > * InitMatcher(MatchType match_type) const override
Definition: linear-fst.h:502
#define VLOG(level)
Definition: log.h:50
constexpr int kNoTrieNodeId
Definition: trie.h:31
static LinearTaggerFst< A > * Read(const std::string &source)
Definition: linear-fst.h:506
void WriteHeader(std::ostream &strm, const FstWriteOptions &opts, int version, FstHeader *hdr) const
Definition: fst.h:786
bool Write(std::ostream &strm, const FstWriteOptions &opts) const
Definition: linear-fst.h:160
void InitArcIterator(StateId s, ArcIteratorData< A > *data)
Definition: linear-fst.h:679
ArcIterator(const LinearTaggerFst< Arc > &fst, StateId s)
Definition: linear-fst.h:570
std::unique_ptr< StateIteratorBase< Arc > > base
Definition: fst.h:382
void InitArcIterator(StateId s, ArcIteratorData< Arc > *data) const
Definition: cache.h:1042
LinearFstMatcherTpl(const FST &fst, MatchType match_type)
Definition: linear-fst.h:1050
static LinearFstData< A > * Read(std::istream &strm)
void SetInputSymbols(const SymbolTable *isyms)
Definition: fst.h:768
A::StateId StateId
Definition: linear-fst.h:469
bool Write(std::ostream &strm, const FstWriteOptions &opts) const override
Definition: linear-fst.h:992
constexpr uint64_t kILabelSorted
Definition: properties.h:93
constexpr uint64_t kFstProperties
Definition: properties.h:325
LinearClassifierFstImpl(const LinearClassifierFstImpl &impl)
Definition: linear-fst.h:635
#define DCHECK_LE(x, y)
Definition: log.h:74
void PushArc(StateId s, const Arc &arc)
Definition: cache.h:933
const SymbolTable * InputSymbols() const
Definition: fst.h:760
void InitArcIterator(StateId s, ArcIteratorData< A > *data)
Definition: linear-fst.h:144
void SetType(std::string_view type)
Definition: fst.h:700
Collection< StateId, Label >::SetIterator NGramIterator
Definition: linear-fst.h:73
void SetStart(int64_t start)
Definition: fst.h:168
void MatchInput(StateId s, Label ilabel, std::vector< Arc > *arcs)
Definition: linear-fst.h:847
LinearTaggerFstImpl(const LinearTaggerFstImpl &impl)
Definition: linear-fst.h:99
LinearTaggerFst< A > * Copy(bool safe=false) const override
Definition: linear-fst.h:492
std::istream & ReadType(std::istream &strm, T *t)
Definition: util.h:68
size_t NumInputEpsilons(StateId s)
Definition: linear-fst.h:134
#define DCHECK(x)
Definition: log.h:70
Impl * GetMutableImpl() const
Definition: fst.h:1028
I FindId(const T &entry, bool insert=true)
Definition: bi-table.h:161
LinearFstMatcherTpl< F > * Copy(bool safe=false) const override
Definition: linear-fst.h:1103
static LinearClassifierFstImpl< A > * Read(std::istream &strm, const FstReadOptions &opts)
Definition: linear-fst.h:876
void InitStateIterator(StateIteratorData< A > *data) const override
Definition: linear-fst.h:1030
const Arc & Value() const final
Definition: linear-fst.h:1140
bool Write(const std::string &source) const override
Definition: linear-fst.h:978
static LinearTaggerFst< A > * Read(std::istream &in, const FstReadOptions &opts)
Definition: linear-fst.h:520
const Impl * GetImpl() const
Definition: fst.h:1026
constexpr uint32_t kRequireMatch
Definition: matcher.h:122
bool Write(std::ostream &strm, const FstWriteOptions &opts) const override
Definition: linear-fst.h:540