FST  openfst-1.8.4
OpenFst Library
ngram-fst.h
Go to the documentation of this file.
1 // Copyright 2005-2024 Google LLC
2 //
3 // Licensed under the Apache License, Version 2.0 (the 'License');
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an 'AS IS' BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 //
15 // See www.openfst.org for extensive documentation on this weighted
16 // finite-state transducer library.
17 //
18 // NgramFst implements a n-gram language model based upon the LOUDS data
19 // structure. Please refer to "Unary Data Structures for Language Models"
20 // http://research.google.com/pubs/archive/37218.pdf
21 
22 #ifndef FST_EXTENSIONS_NGRAM_NGRAM_FST_H_
23 #define FST_EXTENSIONS_NGRAM_NGRAM_FST_H_
24 
25 #include <sys/types.h>
26 
27 #include <algorithm>
28 #include <cstddef>
29 #include <cstdint>
30 #include <cstring>
31 #include <ios>
32 #include <iostream>
33 #include <istream>
34 #include <memory>
35 #include <ostream>
36 #include <queue>
37 #include <string>
38 #include <utility>
39 #include <vector>
40 
41 #include <fst/compat.h>
42 #include <fst/log.h>
44 #include <fst/arcsort.h>
45 #include <fst/expanded-fst.h>
46 #include <fstream>
47 #include <fst/fst.h>
48 #include <fst/fstlib.h>
49 #include <fst/mapped-file.h>
50 #include <fst/matcher.h>
51 #include <fst/properties.h>
52 #include <fst/util.h>
53 #include <fst/vector-fst.h>
54 
55 namespace fst {
56 template <class A>
57 class NGramFst;
58 template <class A>
60 
61 // Instance data containing mutable state for bookkeeping repeated access to
62 // the same state.
63 template <class A>
64 struct NGramFstInst {
65  typedef typename A::Label Label;
66  typedef typename A::StateId StateId;
67  typedef typename A::Weight Weight;
68  StateId state_;
69  size_t num_futures_;
70  size_t offset_;
71  size_t node_;
72  StateId node_state_;
73  std::vector<Label> context_;
74  StateId context_state_;
76  : state_(kNoStateId),
77  node_state_(kNoStateId),
78  context_state_(kNoStateId) {}
79 };
80 
81 namespace internal {
82 
83 // Implementation class for LOUDS based NgramFst interface.
84 template <class A>
85 class NGramFstImpl : public FstImpl<A> {
88  using FstImpl<A>::SetType;
90 
91  friend class ArcIterator<NGramFst<A>>;
92  friend class NGramFstMatcher<A>;
93 
94  public:
98 
99  typedef A Arc;
100  typedef typename A::Label Label;
101  typedef typename A::StateId StateId;
102  typedef typename A::Weight Weight;
103 
105  SetType("ngram");
106  SetInputSymbols(nullptr);
107  SetOutputSymbols(nullptr);
108  SetProperties(kStaticProperties);
109  }
110 
111  NGramFstImpl(const Fst<A> &fst, std::vector<StateId> *order_out);
112 
113  explicit NGramFstImpl(const Fst<A> &fst) : NGramFstImpl(fst, nullptr) {}
114 
115  NGramFstImpl(const NGramFstImpl &other) {
116  FSTERROR() << "Copying NGramFst Impls is not supported, use safe = false.";
117  SetProperties(kError, kError);
118  }
119 
120  static NGramFstImpl<A> *Read(std::istream &strm, const FstReadOptions &opts) {
121  auto impl = std::make_unique<NGramFstImpl<A>>();
122  FstHeader hdr;
123  if (!impl->ReadHeader(strm, opts, kMinFileVersion, &hdr)) return nullptr;
124  uint64_t num_states, num_futures, num_final;
125  const size_t offset =
126  sizeof(num_states) + sizeof(num_futures) + sizeof(num_final);
127  // Peek at num_states and num_futures to see how much more needs to be read.
128  strm.read(reinterpret_cast<char *>(&num_states), sizeof(num_states));
129  strm.read(reinterpret_cast<char *>(&num_futures), sizeof(num_futures));
130  strm.read(reinterpret_cast<char *>(&num_final), sizeof(num_final));
131  size_t size = Storage(num_states, num_futures, num_final);
132  std::unique_ptr<MappedFile> data_region(MappedFile::Allocate(size));
133  char *data = static_cast<char *>(data_region->mutable_data());
134  // Copy num_states, num_futures and num_final back into data.
135  memcpy(data, reinterpret_cast<char *>(&num_states), sizeof(num_states));
136  memcpy(data + sizeof(num_states), reinterpret_cast<char *>(&num_futures),
137  sizeof(num_futures));
138  memcpy(data + sizeof(num_states) + sizeof(num_futures),
139  reinterpret_cast<char *>(&num_final), sizeof(num_final));
140  strm.read(data + offset, size - offset);
141  if (strm.fail()) return nullptr;
142  impl->Init(data, std::move(data_region));
143  return impl.release();
144  }
145 
146  bool Write(std::ostream &strm, const FstWriteOptions &opts) const {
147  FstHeader hdr;
148  hdr.SetStart(Start());
149  hdr.SetNumStates(num_states_);
150  WriteHeader(strm, opts, kFileVersion, &hdr);
151  strm.write(data_, StorageSize());
152  return !strm.fail();
153  }
154 
155  StateId Start() const { return start_; }
156 
157  Weight Final(StateId state) const {
158  if (final_index_.Get(state)) {
159  return final_probs_[final_index_.Rank1(state)];
160  } else {
161  return Weight::Zero();
162  }
163  }
164 
165  size_t NumArcs(StateId state, NGramFstInst<A> *inst = nullptr) const {
166  if (inst == nullptr) {
167  const std::pair<size_t, size_t> zeros =
168  (state == 0) ? select_root_ : future_index_.Select0s(state);
169  return zeros.second - zeros.first - 1;
170  }
171  SetInstFuture(state, inst);
172  return inst->num_futures_ + ((state == 0) ? 0 : 1);
173  }
174 
175  size_t NumInputEpsilons(StateId state) const {
176  // State 0 has no parent, thus no backoff.
177  if (state == 0) return 0;
178  return 1;
179  }
180 
181  size_t NumOutputEpsilons(StateId state) const {
182  return NumInputEpsilons(state);
183  }
184 
185  StateId NumStates() const { return num_states_; }
186 
188  data->base = nullptr;
189  data->nstates = num_states_;
190  }
191 
192  static size_t Storage(uint64_t num_states, uint64_t num_futures,
193  uint64_t num_final) {
194  uint64_t b64;
195  Weight weight;
196  Label label;
197  size_t offset =
198  sizeof(num_states) + sizeof(num_futures) + sizeof(num_final);
199  offset +=
200  sizeof(b64) * (BitmapIndex::StorageSize(num_states * 2 + 1) +
201  BitmapIndex::StorageSize(num_futures + num_states + 1) +
202  BitmapIndex::StorageSize(num_states));
203  offset += (num_states + 1) * sizeof(label) + num_futures * sizeof(label);
204  // Pad for alignemnt, see
205  // http://en.wikipedia.org/wiki/Data_structure_alignment#Computing_padding
206  offset = (offset + sizeof(weight) - 1) & ~(sizeof(weight) - 1);
207  offset += (num_states + 1) * sizeof(weight) + num_final * sizeof(weight) +
208  (num_futures + 1) * sizeof(weight);
209  return offset;
210  }
211 
212  void SetInstFuture(StateId state, NGramFstInst<A> *inst) const {
213  if (inst->state_ != state) {
214  inst->state_ = state;
215  const std::pair<size_t, size_t> zeros = future_index_.Select0s(state);
216  inst->num_futures_ = zeros.second - zeros.first - 1;
217  inst->offset_ = future_index_.Rank1(zeros.first + 1);
218  }
219  }
220 
221  void SetInstNode(NGramFstInst<A> *inst) const {
222  if (inst->node_state_ != inst->state_) {
223  inst->node_state_ = inst->state_;
224  inst->node_ = context_index_.Select1(inst->state_);
225  }
226  }
227 
228  void SetInstContext(NGramFstInst<A> *inst) const {
229  SetInstNode(inst);
230  if (inst->context_state_ != inst->state_) {
231  inst->context_state_ = inst->state_;
232  inst->context_.clear();
233  size_t node = inst->node_;
234  while (node != 0) {
235  const size_t rank1 = context_index_.Rank1(node);
236  const size_t rank0 = node - rank1;
237  inst->context_.push_back(context_words_[rank1]);
238  node = context_index_.Select1(rank0 - 1);
239  }
240  }
241  }
242 
243  // Access to the underlying representation
244  const char *GetData(size_t *data_size) const {
245  *data_size = StorageSize();
246  return data_;
247  }
248 
249  void Init(const char *data,
250  std::unique_ptr<MappedFile> data_region);
251 
252  const std::vector<Label> &GetContext(StateId s, NGramFstInst<A> *inst) const {
253  SetInstFuture(s, inst);
254  SetInstContext(inst);
255  return inst->context_;
256  }
257 
258  size_t StorageSize() const {
259  return Storage(num_states_, num_futures_, num_final_);
260  }
261 
262  void GetStates(const std::vector<Label> &context,
263  std::vector<StateId> *states) const;
264 
265  private:
266  StateId Transition(const std::vector<Label> &context, Label future) const;
267 
268  // Properties always true for this Fst class.
269  static constexpr uint64_t kStaticProperties =
274  // Current file format version.
275  static constexpr int kFileVersion = 4;
276  // Minimum file format version supported.
277  static constexpr int kMinFileVersion = 4;
278 
279  std::unique_ptr<MappedFile> data_region_;
280  const char *data_ = nullptr; // Not owned.
281  StateId start_ = fst::kNoStateId;
282  uint64_t num_states_ = 0;
283  uint64_t num_futures_ = 0;
284  uint64_t num_final_ = 0;
285  std::pair<size_t, size_t> select_root_;
286  const Label *root_children_ = nullptr;
287  // borrowed references
288  const uint64_t *context_ = nullptr;
289  const uint64_t *future_ = nullptr;
290  const uint64_t *final_ = nullptr;
291  const Label *context_words_ = nullptr;
292  const Label *future_words_ = nullptr;
293  const Weight *backoff_ = nullptr;
294  const Weight *final_probs_ = nullptr;
295  const Weight *future_probs_ = nullptr;
296  // Uses all operations.
297  BitmapIndex context_index_;
298  // Uses Select0 and Rank1.
299  BitmapIndex future_index_;
300  // Uses Get and Rank1. This wastes space if there are no or few final
301  // states, but it's also small. TODO(jrosenstock): Look at EliasFanoArray.
302  BitmapIndex final_index_;
303 };
304 
305 template <typename A>
307  const std::vector<Label> &context,
308  std::vector<typename A::StateId> *states) const {
309  states->clear();
310  states->push_back(0);
311  typename std::vector<Label>::const_reverse_iterator cit = context.rbegin();
312  const Label *children = root_children_;
313  size_t num_children = select_root_.second - 2;
314  const Label *loc = std::lower_bound(children, children + num_children, *cit);
315  if (loc == children + num_children || *loc != *cit) return;
316  size_t node = 2 + loc - children;
317  size_t node_rank = context_index_.Rank1(node);
318  states->push_back(node_rank);
319  if (context.size() == 1) return;
320  std::pair<size_t, size_t> zeros =
321  node_rank == 0 ? select_root_ : context_index_.Select0s(node_rank);
322  size_t first_child = zeros.first + 1;
323  ++cit;
324  if (context_index_.Get(first_child) != false) {
325  size_t last_child = zeros.second - 1;
326  while (cit != context.rend()) {
327  children = context_words_ + context_index_.Rank1(first_child);
328  loc = std::lower_bound(children, children + last_child - first_child + 1,
329  *cit);
330  if (loc == children + last_child - first_child + 1 || *loc != *cit) {
331  break;
332  }
333  ++cit;
334  node = first_child + loc - children;
335  node_rank = context_index_.Rank1(node);
336  states->push_back(node_rank);
337  zeros =
338  node_rank == 0 ? select_root_ : context_index_.Select0s(node_rank);
339  first_child = zeros.first + 1;
340  if (context_index_.Get(first_child) == false) break;
341  last_child = zeros.second - 1;
342  }
343  }
344 }
345 
346 } // namespace internal
347 
348 /*****************************************************************************/
349 template <class A>
350 class NGramFst : public ImplToExpandedFst<internal::NGramFstImpl<A>> {
352  friend class ArcIterator<NGramFst<A>>;
353  friend class NGramFstMatcher<A>;
354 
355  public:
356  typedef A Arc;
357  typedef typename A::StateId StateId;
358  typedef typename A::Label Label;
359  typedef typename A::Weight Weight;
360  using typename Base::Impl;
361 
362  explicit NGramFst(const Fst<A> &dst)
363  : Base(std::make_shared<Impl>(dst, nullptr)) {}
364 
365  NGramFst(const Fst<A> &fst, std::vector<StateId> *order_out)
366  : Base(std::make_shared<Impl>(fst, order_out)) {}
367 
368  // Because the NGramFstImpl is a const stateless data structure, there
369  // is never a need to do anything beside copy the reference.
370  NGramFst(const NGramFst<A> &fst, bool safe = false) : Base(fst, false) {}
371 
372  NGramFst() : Base(std::make_shared<Impl>()) {}
373 
374  // Non-standard constructor to initialize NGramFst directly from data. Caller
375  // maintains ownership of data, which must outlive the NGramFst.
376  explicit NGramFst(const char *data) : Base(std::make_shared<Impl>()) {
377  GetMutableImpl()->Init(data, /*data_region=*/nullptr);
378  }
379 
380  // Get method that gets the data associated with Init().
381  const char *GetData(size_t *data_size) const {
382  return GetImpl()->GetData(data_size);
383  }
384 
385  const std::vector<Label> GetContext(StateId s) const {
386  return GetImpl()->GetContext(s, &inst_);
387  }
388 
389  // Consumes as much as possible of context from right to left, returns the
390  // the states corresponding to the increasingly conditioned input sequence.
391  void GetStates(const std::vector<Label> &context,
392  std::vector<StateId> *state) const {
393  return GetImpl()->GetStates(context, state);
394  }
395 
396  size_t NumArcs(StateId s) const override {
397  return GetImpl()->NumArcs(s, &inst_);
398  }
399 
400  NGramFst<A> *Copy(bool safe = false) const override {
401  return new NGramFst(*this, safe);
402  }
403 
404  static NGramFst<A> *Read(std::istream &strm, const FstReadOptions &opts) {
405  Impl *impl = Impl::Read(strm, opts);
406  return impl ? new NGramFst<A>(std::shared_ptr<Impl>(impl)) : nullptr;
407  }
408 
409  static NGramFst<A> *Read(const std::string &source) {
410  if (!source.empty()) {
411  std::ifstream strm(source,
412  std::ios_base::in | std::ios_base::binary);
413  if (!strm.good()) {
414  LOG(ERROR) << "NGramFst::Read: Can't open file: " << source;
415  return nullptr;
416  }
417  return Read(strm, FstReadOptions(source));
418  } else {
419  return Read(std::cin, FstReadOptions("standard input"));
420  }
421  }
422 
423  bool Write(std::ostream &strm, const FstWriteOptions &opts) const override {
424  return GetImpl()->Write(strm, opts);
425  }
426 
427  bool Write(const std::string &source) const override {
428  return Fst<A>::WriteFile(source);
429  }
430 
431  inline void InitStateIterator(StateIteratorData<A> *data) const override {
432  GetImpl()->InitStateIterator(data);
433  }
434 
435  inline void InitArcIterator(StateId s,
436  ArcIteratorData<A> *data) const override;
437 
438  MatcherBase<A> *InitMatcher(MatchType match_type) const override {
439  return new NGramFstMatcher<A>(this, match_type);
440  }
441 
442  size_t StorageSize() const { return GetImpl()->StorageSize(); }
443 
444  static bool HasRequiredProps(const Fst<A> &fst) {
445  static const auto props =
447  return fst.Properties(props, true) == props;
448  }
449 
450  static bool HasRequiredStructure(const Fst<A> &fst) {
451  if (!HasRequiredProps(fst)) {
452  return false;
453  }
454  typename A::StateId unigram = fst.Start();
455  while (true) { // Follows epsilon arc chain to find unigram state.
456  if (unigram == fst::kNoStateId) return false; // No unigram state.
457  typename fst::ArcIterator<Fst<A>> aiter(fst, unigram);
458  if (aiter.Done() || aiter.Value().ilabel != 0) break;
459  unigram = aiter.Value().nextstate;
460  aiter.Next();
461  }
462  // Other requirement: all states other than unigram an epsilon arc.
463  for (fst::StateIterator<Fst<A>> siter(fst); !siter.Done();
464  siter.Next()) {
465  const typename A::StateId &state = siter.Value();
466  fst::ArcIterator<Fst<A>> aiter(fst, state);
467  if (state != unigram) {
468  if (aiter.Done()) return false;
469  if (aiter.Value().ilabel != 0) return false;
470  aiter.Next();
471  if (!aiter.Done() && aiter.Value().ilabel == 0) return false;
472  }
473  }
474  return true;
475  }
476 
477  private:
478  using Base::GetImpl;
479  using Base::GetMutableImpl;
480 
481  explicit NGramFst(std::shared_ptr<Impl> impl) : Base(impl) {}
482 
483  mutable NGramFstInst<A> inst_;
484 };
485 
486 template <class A>
488  ArcIteratorData<A> *data) const {
489  GetImpl()->SetInstFuture(s, &inst_);
490  GetImpl()->SetInstNode(&inst_);
491  data->base = std::make_unique<ArcIterator<NGramFst<A>>>(*this, s);
492 }
493 
494 namespace internal {
495 
496 template <typename A>
498  std::vector<StateId> *order_out) {
499  typedef A Arc;
500  typedef typename Arc::Label Label;
501  typedef typename Arc::Weight Weight;
502  typedef typename Arc::StateId StateId;
503  SetType("ngram");
504  SetInputSymbols(fst.InputSymbols());
505  SetOutputSymbols(fst.OutputSymbols());
506  SetProperties(kStaticProperties);
507 
508  // Check basic requirements for an OpenGrm language model Fst.
509  if (!NGramFst<A>::HasRequiredProps(fst)) {
510  FSTERROR() << "NGramFst only accepts OpenGrm language models as input";
511  SetProperties(kError, kError);
512  return;
513  }
514 
515  int64_t num_states = CountStates(fst);
516  std::vector<Label> context(num_states, 0);
517 
518  // Find the unigram state by starting from the start state, following
519  // epsilons.
520  StateId unigram = fst.Start();
521  while (true) {
522  if (unigram == kNoStateId) {
523  FSTERROR() << "Could not identify unigram state";
524  SetProperties(kError, kError);
525  return;
526  }
527  ArcIterator<Fst<A>> aiter(fst, unigram);
528  if (aiter.Done()) {
529  LOG(WARNING) << "Unigram state " << unigram << " has no arcs.";
530  break;
531  }
532  if (aiter.Value().ilabel != 0) break;
533  unigram = aiter.Value().nextstate;
534  }
535 
536  // Each state's context is determined by the subtree it is under from the
537  // unigram state.
538  std::queue<std::pair<StateId, Label>> label_queue;
539  std::vector<bool> visited(num_states);
540  // Force an epsilon link to the start state.
541  label_queue.push(std::make_pair(fst.Start(), 0));
542  for (ArcIterator<Fst<A>> aiter(fst, unigram); !aiter.Done(); aiter.Next()) {
543  label_queue.push(
544  std::make_pair(aiter.Value().nextstate, aiter.Value().ilabel));
545  }
546  // investigate states in breadth first fashion to assign context words.
547  while (!label_queue.empty()) {
548  std::pair<StateId, Label> &now = label_queue.front();
549  if (!visited[now.first]) {
550  context[now.first] = now.second;
551  visited[now.first] = true;
552  for (ArcIterator<Fst<A>> aiter(fst, now.first); !aiter.Done();
553  aiter.Next()) {
554  const Arc &arc = aiter.Value();
555  if (arc.ilabel != 0) {
556  label_queue.push(std::make_pair(arc.nextstate, now.second));
557  }
558  }
559  }
560  label_queue.pop();
561  }
562  visited.clear();
563 
564  // The arc from the start state should be assigned an epsilon to put it
565  // in front of the all other labels (which makes Start state 1 after
566  // unigram which is state 0).
567  context[fst.Start()] = 0;
568 
569  // Build the tree of contexts fst by reversing the epsilon arcs from fst.
570  VectorFst<Arc> context_fst;
571  uint64_t num_final = 0;
572  for (int i = 0; i < num_states; ++i) {
573  if (fst.Final(i) != Weight::Zero()) {
574  ++num_final;
575  }
576  context_fst.SetFinal(context_fst.AddState(), fst.Final(i));
577  }
578  context_fst.SetStart(unigram);
579  context_fst.SetInputSymbols(fst.InputSymbols());
580  context_fst.SetOutputSymbols(fst.OutputSymbols());
581  int64_t num_context_arcs = 0;
582  int64_t num_futures = 0;
583  for (StateIterator<Fst<A>> siter(fst); !siter.Done(); siter.Next()) {
584  const StateId &state = siter.Value();
585  num_futures += fst.NumArcs(state) - fst.NumInputEpsilons(state);
586  ArcIterator<Fst<A>> aiter(fst, state);
587  if (!aiter.Done()) {
588  const Arc &arc = aiter.Value();
589  // this arc goes from state to arc.nextstate, so create an arc from
590  // arc.nextstate to state to reverse it.
591  if (arc.ilabel == 0) {
592  context_fst.AddArc(arc.nextstate, Arc(context[state], context[state],
593  arc.weight, state));
594  num_context_arcs++;
595  }
596  }
597  }
598  if (num_context_arcs != context_fst.NumStates() - 1) {
599  FSTERROR() << "Number of contexts arcs != number of states - 1";
600  SetProperties(kError, kError);
601  return;
602  }
603  if (context_fst.NumStates() != num_states) {
604  FSTERROR() << "Number of contexts != number of states";
605  SetProperties(kError, kError);
606  return;
607  }
608  int64_t context_props =
609  context_fst.Properties(kIDeterministic | kILabelSorted, true);
610  if (!(context_props & kIDeterministic)) {
611  FSTERROR() << "Input Fst is not structured properly";
612  SetProperties(kError, kError);
613  return;
614  }
615  if (!(context_props & kILabelSorted)) {
616  ArcSort(&context_fst, ILabelCompare<Arc>());
617  }
618 
619  uint64_t b64;
620  Weight weight;
621  Label label = kNoLabel;
622  const size_t storage = Storage(num_states, num_futures, num_final);
623  std::unique_ptr<MappedFile> data_region(MappedFile::Allocate(storage));
624  char *data = static_cast<char *>(data_region->mutable_data());
625  memset(data, 0, storage);
626  size_t offset = 0;
627  memcpy(data + offset, reinterpret_cast<char *>(&num_states),
628  sizeof(num_states));
629  offset += sizeof(num_states);
630  memcpy(data + offset, reinterpret_cast<char *>(&num_futures),
631  sizeof(num_futures));
632  offset += sizeof(num_futures);
633  memcpy(data + offset, reinterpret_cast<char *>(&num_final),
634  sizeof(num_final));
635  offset += sizeof(num_final);
636  uint64_t *context_bits = reinterpret_cast<uint64_t *>(data + offset);
637  offset += BitmapIndex::StorageSize(num_states * 2 + 1) * sizeof(b64);
638  uint64_t *future_bits = reinterpret_cast<uint64_t *>(data + offset);
639  offset +=
640  BitmapIndex::StorageSize(num_futures + num_states + 1) * sizeof(b64);
641  uint64_t *final_bits = reinterpret_cast<uint64_t *>(data + offset);
642  offset += BitmapIndex::StorageSize(num_states) * sizeof(b64);
643  Label *context_words = reinterpret_cast<Label *>(data + offset);
644  offset += (num_states + 1) * sizeof(label);
645  Label *future_words = reinterpret_cast<Label *>(data + offset);
646  offset += num_futures * sizeof(label);
647  offset = (offset + sizeof(weight) - 1) & ~(sizeof(weight) - 1);
648  Weight *backoff = reinterpret_cast<Weight *>(data + offset);
649  offset += (num_states + 1) * sizeof(weight);
650  Weight *final_probs = reinterpret_cast<Weight *>(data + offset);
651  offset += num_final * sizeof(weight);
652  Weight *future_probs = reinterpret_cast<Weight *>(data + offset);
653  int64_t context_arc = 0, future_arc = 0, context_bit = 0, future_bit = 0,
654  final_bit = 0;
655 
656  // pseudo-root bits
657  BitmapIndex::Set(context_bits, context_bit++);
658  ++context_bit;
659  context_words[context_arc] = label;
660  backoff[context_arc] = Weight::Zero();
661  context_arc++;
662 
663  ++future_bit;
664  if (order_out) {
665  order_out->clear();
666  order_out->resize(num_states);
667  }
668 
669  std::queue<StateId> context_q;
670  context_q.push(context_fst.Start());
671  StateId state_number = 0;
672  while (!context_q.empty()) {
673  const StateId &state = context_q.front();
674  if (order_out) {
675  (*order_out)[state] = state_number;
676  }
677 
678  const Weight final_weight = context_fst.Final(state);
679  if (final_weight != Weight::Zero()) {
680  BitmapIndex::Set(final_bits, state_number);
681  final_probs[final_bit] = final_weight;
682  ++final_bit;
683  }
684 
685  for (ArcIterator<VectorFst<A>> aiter(context_fst, state); !aiter.Done();
686  aiter.Next()) {
687  const Arc &arc = aiter.Value();
688  context_words[context_arc] = arc.ilabel;
689  backoff[context_arc] = arc.weight;
690  ++context_arc;
691  BitmapIndex::Set(context_bits, context_bit++);
692  context_q.push(arc.nextstate);
693  }
694  ++context_bit;
695 
696  for (ArcIterator<Fst<A>> aiter(fst, state); !aiter.Done(); aiter.Next()) {
697  const Arc &arc = aiter.Value();
698  if (arc.ilabel != 0) {
699  future_words[future_arc] = arc.ilabel;
700  future_probs[future_arc] = arc.weight;
701  ++future_arc;
702  BitmapIndex::Set(future_bits, future_bit++);
703  }
704  }
705  ++future_bit;
706  ++state_number;
707  context_q.pop();
708  }
709 
710  if ((state_number != num_states) || (context_bit != num_states * 2 + 1) ||
711  (context_arc != num_states) || (future_arc != num_futures) ||
712  (future_bit != num_futures + num_states + 1) ||
713  (final_bit != num_final)) {
714  FSTERROR() << "Structure problems detected during construction";
715  SetProperties(kError, kError);
716  return;
717  }
718 
719  Init(data, std::move(data_region));
720 }
721 
722 template <typename A>
723 inline void NGramFstImpl<A>::Init(const char *data,
724  std::unique_ptr<MappedFile> data_region) {
725  data_region_ = std::move(data_region);
726  data_ = data;
727  size_t offset = 0;
728  num_states_ = *(reinterpret_cast<const uint64_t *>(data_ + offset));
729  offset += sizeof(num_states_);
730  num_futures_ = *(reinterpret_cast<const uint64_t *>(data_ + offset));
731  offset += sizeof(num_futures_);
732  num_final_ = *(reinterpret_cast<const uint64_t *>(data_ + offset));
733  offset += sizeof(num_final_);
734  uint64_t bits;
735  size_t context_bits = num_states_ * 2 + 1;
736  size_t future_bits = num_futures_ + num_states_ + 1;
737  context_ = reinterpret_cast<const uint64_t *>(data_ + offset);
738  offset += BitmapIndex::StorageSize(context_bits) * sizeof(bits);
739  future_ = reinterpret_cast<const uint64_t *>(data_ + offset);
740  offset += BitmapIndex::StorageSize(future_bits) * sizeof(bits);
741  final_ = reinterpret_cast<const uint64_t *>(data_ + offset);
742  offset += BitmapIndex::StorageSize(num_states_) * sizeof(bits);
743  context_words_ = reinterpret_cast<const Label *>(data_ + offset);
744  offset += (num_states_ + 1) * sizeof(*context_words_);
745  future_words_ = reinterpret_cast<const Label *>(data_ + offset);
746  offset += num_futures_ * sizeof(*future_words_);
747  offset = (offset + sizeof(*backoff_) - 1) & ~(sizeof(*backoff_) - 1);
748  backoff_ = reinterpret_cast<const Weight *>(data_ + offset);
749  offset += (num_states_ + 1) * sizeof(*backoff_);
750  final_probs_ = reinterpret_cast<const Weight *>(data_ + offset);
751  offset += num_final_ * sizeof(*final_probs_);
752  future_probs_ = reinterpret_cast<const Weight *>(data_ + offset);
753 
754  context_index_.BuildIndex(context_, context_bits,
755  /*enable_select_0_index=*/true,
756  /*enable_select_1_index=*/true);
757  future_index_.BuildIndex(future_, future_bits,
758  /*enable_select_0_index=*/true,
759  /*enable_select_1_index=*/false);
760  final_index_.BuildIndex(final_, num_states_);
761 
762  select_root_ = context_index_.Select0s(0);
763  if (context_index_.Rank1(0) != 0 || select_root_.first != 1 ||
764  context_index_.Get(2) == false) {
765  FSTERROR() << "Malformed file";
766  SetProperties(kError, kError);
767  return;
768  }
769  root_children_ = context_words_ + context_index_.Rank1(2);
770  start_ = 1;
771 }
772 
773 template <typename A>
774 inline typename A::StateId NGramFstImpl<A>::Transition(
775  const std::vector<Label> &context, Label future) const {
776  const Label *children = root_children_;
777  size_t num_children = select_root_.second - 2;
778  const Label *loc =
779  std::lower_bound(children, children + num_children, future);
780  if (loc == children + num_children || *loc != future) {
781  return context_index_.Rank1(0);
782  }
783  size_t node = 2 + loc - children;
784  size_t node_rank = context_index_.Rank1(node);
785  std::pair<size_t, size_t> zeros =
786  (node_rank == 0) ? select_root_ : context_index_.Select0s(node_rank);
787  size_t first_child = zeros.first + 1;
788  if (context_index_.Get(first_child) == false) {
789  return node_rank;
790  }
791  size_t last_child = zeros.second - 1;
792  for (int word = context.size() - 1; word >= 0; --word) {
793  children = context_words_ + context_index_.Rank1(first_child);
794  loc = std::lower_bound(children, children + last_child - first_child + 1,
795  context[word]);
796  if (loc == children + last_child - first_child + 1 ||
797  *loc != context[word]) {
798  break;
799  }
800  node = first_child + loc - children;
801  node_rank = context_index_.Rank1(node);
802  zeros =
803  (node_rank == 0) ? select_root_ : context_index_.Select0s(node_rank);
804  first_child = zeros.first + 1;
805  if (context_index_.Get(first_child) == false) break;
806  last_child = zeros.second - 1;
807  }
808  return node_rank;
809 }
810 
811 } // namespace internal
812 
813 /*****************************************************************************/
814 template <class A>
815 class NGramFstMatcher : public MatcherBase<A> {
816  public:
817  typedef A Arc;
818  typedef typename A::Label Label;
819  typedef typename A::StateId StateId;
820  typedef typename A::Weight Weight;
821 
822  // This makes a copy of the FST.
824  : owned_fst_(fst.Copy()),
825  fst_(*owned_fst_),
826  inst_(fst_.inst_),
827  match_type_(match_type),
828  current_loop_(false),
829  loop_(kNoLabel, 0, A::Weight::One(), kNoStateId) {
830  if (match_type_ == MATCH_OUTPUT) {
831  std::swap(loop_.ilabel, loop_.olabel);
832  }
833  }
834 
835  // This doesn't copy the FST.
837  : fst_(*fst),
838  inst_(fst_.inst_),
839  match_type_(match_type),
840  current_loop_(false),
841  loop_(kNoLabel, 0, A::Weight::One(), kNoStateId) {
842  if (match_type_ == MATCH_OUTPUT) {
843  std::swap(loop_.ilabel, loop_.olabel);
844  }
845  }
846 
847  // This makes a copy of the FST.
848  NGramFstMatcher(const NGramFstMatcher<A> &matcher, bool safe = false)
849  : owned_fst_(matcher.fst_.Copy(safe)),
850  fst_(*owned_fst_),
851  inst_(matcher.inst_),
852  match_type_(matcher.match_type_),
853  current_loop_(false),
854  loop_(kNoLabel, 0, A::Weight::One(), kNoStateId) {
855  if (match_type_ == MATCH_OUTPUT) {
856  std::swap(loop_.ilabel, loop_.olabel);
857  }
858  }
859 
860  NGramFstMatcher<A> *Copy(bool safe = false) const override {
861  return new NGramFstMatcher<A>(*this, safe);
862  }
863 
864  MatchType Type(bool test) const override { return match_type_; }
865 
866  const Fst<A> &GetFst() const override { return fst_; }
867 
868  uint64_t Properties(uint64_t props) const override { return props; }
869 
870  void SetState(StateId s) final {
871  fst_.GetImpl()->SetInstFuture(s, &inst_);
872  current_loop_ = false;
873  }
874 
875  bool Find(Label label) final {
876  const Label nolabel = kNoLabel;
877  done_ = true;
878  if (label == 0 || label == nolabel) {
879  if (label == 0) {
880  current_loop_ = true;
881  loop_.nextstate = inst_.state_;
882  }
883  // The unigram state has no epsilon arc.
884  if (inst_.state_ != 0) {
885  arc_.ilabel = arc_.olabel = 0;
886  fst_.GetImpl()->SetInstNode(&inst_);
887  arc_.nextstate = fst_.GetImpl()->context_index_.Rank1(
888  fst_.GetImpl()->context_index_.Select1(
889  fst_.GetImpl()->context_index_.Rank0(inst_.node_) - 1));
890  arc_.weight = fst_.GetImpl()->backoff_[inst_.state_];
891  done_ = false;
892  }
893  } else {
894  current_loop_ = false;
895  const Label *start = fst_.GetImpl()->future_words_ + inst_.offset_;
896  const Label *end = start + inst_.num_futures_;
897  const Label *search = std::lower_bound(start, end, label);
898  if (search != end && *search == label) {
899  size_t state = search - start;
900  arc_.ilabel = arc_.olabel = label;
901  arc_.weight = fst_.GetImpl()->future_probs_[inst_.offset_ + state];
902  fst_.GetImpl()->SetInstContext(&inst_);
903  arc_.nextstate = fst_.GetImpl()->Transition(inst_.context_, label);
904  done_ = false;
905  }
906  }
907  return !Done();
908  }
909 
910  bool Done() const final { return !current_loop_ && done_; }
911 
912  const Arc &Value() const final { return (current_loop_) ? loop_ : arc_; }
913 
914  void Next() final {
915  if (current_loop_) {
916  current_loop_ = false;
917  } else {
918  done_ = true;
919  }
920  }
921 
922  ssize_t Priority(StateId s) final { return fst_.NumArcs(s); }
923 
924  private:
925  std::unique_ptr<NGramFst<A>> owned_fst_;
926  const NGramFst<A> &fst_;
927  NGramFstInst<A> inst_;
928  MatchType match_type_; // Supplied by caller
929  bool done_;
930  Arc arc_;
931  bool current_loop_; // Current arc is the implicit loop
932  Arc loop_;
933 };
934 
935 /*****************************************************************************/
936 // Specialization for NGramFst; see generic version in fst.h
937 // for sample usage (but use the ProdLmFst type!). This version
938 // should inline.
939 template <class A>
940 class StateIterator<NGramFst<A>> : public StateIteratorBase<A> {
941  public:
942  typedef typename A::StateId StateId;
943 
944  explicit StateIterator(const NGramFst<A> &fst)
945  : s_(0), num_states_(fst.NumStates()) {}
946 
947  bool Done() const final { return s_ >= num_states_; }
948 
949  StateId Value() const final {
950  DCHECK(!Done());
951  return s_;
952  }
953 
954  void Next() final { ++s_; }
955 
956  void Reset() final { s_ = 0; }
957 
958  private:
959  StateId s_;
960  StateId num_states_;
961 };
962 
963 /*****************************************************************************/
964 template <class A>
965 class ArcIterator<NGramFst<A>> : public ArcIteratorBase<A> {
966  public:
967  typedef A Arc;
968  typedef typename A::Label Label;
969  typedef typename A::StateId StateId;
970  typedef typename A::Weight Weight;
971 
972  ArcIterator(const NGramFst<A> &fst, StateId state)
973  : lazy_(~0), impl_(fst.GetImpl()), i_(0), flags_(kArcValueFlags) {
974  inst_ = fst.inst_;
975  impl_->SetInstFuture(state, &inst_);
976  impl_->SetInstNode(&inst_);
977  }
978 
979  bool Done() const final {
980  return i_ >=
981  ((inst_.node_ == 0) ? inst_.num_futures_ : inst_.num_futures_ + 1);
982  }
983 
984  const Arc &Value() const final {
985  DCHECK(!Done());
986  bool eps = (inst_.node_ != 0 && i_ == 0);
987  StateId state = (inst_.node_ == 0) ? i_ : i_ - 1;
988  if (flags_ & lazy_ & (kArcILabelValue | kArcOLabelValue)) {
989  arc_.ilabel = arc_.olabel =
990  eps ? 0 : impl_->future_words_[inst_.offset_ + state];
991  lazy_ &= ~(kArcILabelValue | kArcOLabelValue);
992  }
993  if (flags_ & lazy_ & kArcNextStateValue) {
994  if (eps) {
995  arc_.nextstate =
996  impl_->context_index_.Rank1(impl_->context_index_.Select1(
997  impl_->context_index_.Rank0(inst_.node_) - 1));
998  } else {
999  if (lazy_ & kArcNextStateValue) {
1000  impl_->SetInstContext(&inst_); // first time only.
1001  }
1002  arc_.nextstate = impl_->Transition(
1003  inst_.context_, impl_->future_words_[inst_.offset_ + state]);
1004  }
1005  lazy_ &= ~kArcNextStateValue;
1006  }
1007  if (flags_ & lazy_ & kArcWeightValue) {
1008  arc_.weight = eps ? impl_->backoff_[inst_.state_]
1009  : impl_->future_probs_[inst_.offset_ + state];
1010  lazy_ &= ~kArcWeightValue;
1011  }
1012  return arc_;
1013  }
1014 
1015  void Next() final {
1016  ++i_;
1017  lazy_ = ~0;
1018  }
1019 
1020  size_t Position() const final { return i_; }
1021 
1022  void Reset() final {
1023  i_ = 0;
1024  lazy_ = ~0;
1025  }
1026 
1027  void Seek(size_t a) final {
1028  if (i_ != a) {
1029  i_ = a;
1030  lazy_ = ~0;
1031  }
1032  }
1033 
1034  uint8_t Flags() const final { return flags_; }
1035 
1036  void SetFlags(uint8_t flags, uint8_t mask) final {
1037  flags_ &= ~mask;
1038  flags_ |= (flags & kArcValueFlags);
1039  }
1040 
1041  private:
1042  mutable Arc arc_;
1043  mutable uint8_t lazy_;
1044  const internal::NGramFstImpl<A> *impl_; // Borrowed reference.
1045  mutable NGramFstInst<A> inst_;
1046 
1047  size_t i_;
1048  uint8_t flags_;
1049 };
1050 
1051 } // namespace fst
1052 #endif // FST_EXTENSIONS_NGRAM_NGRAM_FST_H_
constexpr uint64_t kCyclic
Definition: properties.h:109
void GetStates(const std::vector< Label > &context, std::vector< StateId > *state) const
Definition: ngram-fst.h:391
constexpr uint64_t kNotString
Definition: properties.h:139
NGramFst< A > * Copy(bool safe=false) const override
Definition: ngram-fst.h:400
constexpr uint8_t kArcValueFlags
Definition: fst.h:452
size_t num_futures_
Definition: ngram-fst.h:69
void Next() final
Definition: ngram-fst.h:914
constexpr int kNoLabel
Definition: fst.h:194
size_t NumInputEpsilons(StateId state) const
Definition: ngram-fst.h:175
virtual uint64_t Properties(uint64_t mask, bool test) const =0
constexpr uint64_t kOEpsilons
Definition: properties.h:89
const Arc & Value() const final
Definition: ngram-fst.h:912
virtual size_t NumArcs(StateId) const =0
static size_t Storage(uint64_t num_states, uint64_t num_futures, uint64_t num_final)
Definition: ngram-fst.h:192
constexpr uint64_t kCoAccessible
Definition: properties.h:129
void SetInputSymbols(const SymbolTable *isyms) override
Definition: mutable-fst.h:399
void SetInstContext(NGramFstInst< A > *inst) const
Definition: ngram-fst.h:228
uint8_t Flags() const final
Definition: ngram-fst.h:1034
static void Set(uint64_t *bits, size_t index)
Definition: bitmap-index.h:116
constexpr uint64_t kNotTopSorted
Definition: properties.h:121
MatchType
Definition: fst.h:186
StateId state_
Definition: ngram-fst.h:68
size_t Position() const final
Definition: ngram-fst.h:1020
constexpr uint64_t kError
Definition: properties.h:52
size_t StorageSize() const
Definition: ngram-fst.h:442
StateId Start() const override
Definition: impl-to-fst.h:48
constexpr uint64_t kInitialAcyclic
Definition: properties.h:116
static NGramFstImpl< A > * Read(std::istream &strm, const FstReadOptions &opts)
Definition: ngram-fst.h:120
#define LOG(type)
Definition: log.h:53
virtual Weight Final(StateId) const =0
SetType
Definition: set-weight.h:59
StateId node_state_
Definition: ngram-fst.h:72
uint64_t Properties(uint64_t props) const override
Definition: ngram-fst.h:868
constexpr uint8_t kArcILabelValue
Definition: fst.h:443
constexpr uint64_t kEpsilons
Definition: properties.h:79
Weight Final(StateId s) const override
Definition: impl-to-fst.h:50
constexpr uint64_t kODeterministic
Definition: properties.h:74
const Arc & Value() const final
Definition: ngram-fst.h:984
constexpr int kNoStateId
Definition: fst.h:195
NGramFstMatcher< A > * Copy(bool safe=false) const override
Definition: ngram-fst.h:860
const Arc & Value() const
Definition: fst.h:535
uint64_t Properties(uint64_t mask, bool test) const override
Definition: impl-to-fst.h:64
NGramFstMatcher(const NGramFstMatcher< A > &matcher, bool safe=false)
Definition: ngram-fst.h:848
static MappedFile * Allocate(size_t size, size_t align=kArchAlignment)
Definition: mapped-file.cc:199
void InitArcIterator(StateId s, ArcIteratorData< A > *data) const override
Definition: ngram-fst.h:487
NGramFst(const Fst< A > &fst, std::vector< StateId > *order_out)
Definition: ngram-fst.h:365
const Fst< A > & GetFst() const override
Definition: ngram-fst.h:866
virtual size_t NumInputEpsilons(StateId) const =0
#define FSTERROR()
Definition: util.h:57
NGramFst(const Fst< A > &dst)
Definition: ngram-fst.h:362
size_t NumArcs(StateId state, NGramFstInst< A > *inst=nullptr) const
Definition: ngram-fst.h:165
const std::vector< Label > & GetContext(StateId s, NGramFstInst< A > *inst) const
Definition: ngram-fst.h:252
static size_t StorageSize(size_t num_bits)
Definition: bitmap-index.h:94
NGramFst(const NGramFst< A > &fst, bool safe=false)
Definition: ngram-fst.h:370
A::Weight Weight
Definition: ngram-fst.h:67
ssize_t NumInputEpsilons(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
Definition: expanded-fst.h:118
const char * GetData(size_t *data_size) const
Definition: ngram-fst.h:381
A::StateId StateId
Definition: ngram-fst.h:66
void ArcSort(MutableFst< Arc > *fst, Compare comp)
Definition: arcsort.h:109
constexpr uint64_t kOLabelSorted
Definition: properties.h:99
void SetInstNode(NGramFstInst< A > *inst) const
Definition: ngram-fst.h:221
void SetFlags(uint8_t flags, uint8_t mask) final
Definition: ngram-fst.h:1036
static NGramFst< A > * Read(std::istream &strm, const FstReadOptions &opts)
Definition: ngram-fst.h:404
std::vector< Label > context_
Definition: ngram-fst.h:73
MatcherBase< A > * InitMatcher(MatchType match_type) const override
Definition: ngram-fst.h:438
bool Write(const std::string &source) const override
Definition: ngram-fst.h:427
StateId NumStates() const override
Definition: expanded-fst.h:147
StateId Value() const final
Definition: ngram-fst.h:949
NGramFstMatcher(const NGramFst< A > &fst, MatchType match_type)
Definition: ngram-fst.h:823
StateId nstates
Definition: fst.h:383
constexpr uint64_t kAccessible
Definition: properties.h:124
constexpr uint8_t kArcOLabelValue
Definition: fst.h:445
const char * GetData(size_t *data_size) const
Definition: ngram-fst.h:244
MatchType Type(bool test) const override
Definition: ngram-fst.h:864
size_t NumArcs(StateId s) const override
Definition: ngram-fst.h:396
void SetInstFuture(StateId state, NGramFstInst< A > *inst) const
Definition: ngram-fst.h:212
virtual StateId Start() const =0
bool Done() const
Definition: fst.h:531
std::unique_ptr< StateIteratorBase< Arc > > base
Definition: fst.h:381
A::StateId StateId
Definition: ngram-fst.h:819
constexpr uint64_t kIDeterministic
Definition: properties.h:69
void SetState(StateId s) final
Definition: ngram-fst.h:870
NGramFstImpl(const Fst< A > &fst)
Definition: ngram-fst.h:113
std::unique_ptr< ArcIteratorBase< Arc > > base
Definition: fst.h:493
const std::vector< Label > GetContext(StateId s) const
Definition: ngram-fst.h:385
constexpr uint64_t kIEpsilons
Definition: properties.h:84
void Seek(size_t a) final
Definition: ngram-fst.h:1027
StateId AddState() override
Definition: mutable-fst.h:324
void AddArc(StateId s, const Arc &arc) override
Definition: mutable-fst.h:334
void SetOutputSymbols(const SymbolTable *osyms) override
Definition: mutable-fst.h:404
bool WriteFile(const std::string &source) const
Definition: fst.h:331
StateId NumStates() const
Definition: ngram-fst.h:185
A::Label Label
Definition: ngram-fst.h:358
constexpr uint8_t kArcWeightValue
Definition: fst.h:447
size_t StorageSize() const
Definition: ngram-fst.h:258
constexpr uint64_t kILabelSorted
Definition: properties.h:94
void SetNumStates(int64_t numstates)
Definition: fst.h:163
void SetFinal(StateId s, Weight weight=Weight::One()) override
Definition: mutable-fst.h:311
bool Write(std::ostream &strm, const FstWriteOptions &opts) const override
Definition: ngram-fst.h:423
StateId context_state_
Definition: ngram-fst.h:74
virtual const SymbolTable * InputSymbols() const =0
Arc::StateId CountStates(const Fst< Arc > &fst)
Definition: expanded-fst.h:181
constexpr uint8_t kArcNextStateValue
Definition: fst.h:449
ssize_t Priority(StateId s) final
Definition: ngram-fst.h:922
ArcIterator(const NGramFst< A > &fst, StateId state)
Definition: ngram-fst.h:972
size_t NumOutputEpsilons(StateId state) const
Definition: ngram-fst.h:181
NGramFstImpl(const NGramFstImpl &other)
Definition: ngram-fst.h:115
void SetStart(int64_t start)
Definition: fst.h:161
bool Done() const final
Definition: ngram-fst.h:910
StateId Start() const
Definition: ngram-fst.h:155
NGramFstMatcher(const NGramFst< A > *fst, MatchType match_type)
Definition: ngram-fst.h:836
A::Label Label
Definition: ngram-fst.h:65
NGramFst(const char *data)
Definition: ngram-fst.h:376
A::Weight Weight
Definition: ngram-fst.h:359
void InitStateIterator(StateIteratorData< A > *data) const override
Definition: ngram-fst.h:431
Weight Final(StateId state) const
Definition: ngram-fst.h:157
void InitStateIterator(StateIteratorData< A > *data) const
Definition: ngram-fst.h:187
bool Write(std::ostream &strm, const FstWriteOptions &opts) const
Definition: ngram-fst.h:146
#define DCHECK(x)
Definition: log.h:74
A::StateId StateId
Definition: ngram-fst.h:357
constexpr uint64_t kWeighted
Definition: properties.h:104
bool Find(Label label) final
Definition: ngram-fst.h:875
constexpr uint64_t kExpanded
Definition: properties.h:46
static bool HasRequiredStructure(const Fst< A > &fst)
Definition: ngram-fst.h:450
StateIterator(const NGramFst< A > &fst)
Definition: ngram-fst.h:944
static NGramFst< A > * Read(const std::string &source)
Definition: ngram-fst.h:409
static bool HasRequiredProps(const Fst< A > &fst)
Definition: ngram-fst.h:444
void SetStart(StateId s) override
Definition: mutable-fst.h:306
constexpr uint64_t kAcceptor
Definition: properties.h:64
virtual const SymbolTable * OutputSymbols() const =0
void Next()
Definition: fst.h:539