FST  openfst-1.8.2
OpenFst Library
compact-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 // FST Class for memory-efficient representation of common types of
19 // FSTs: linear automata, acceptors, unweighted FSTs, ...
20 
21 #ifndef FST_COMPACT_FST_H_
22 #define FST_COMPACT_FST_H_
23 
24 #include <climits>
25 #include <cstdint>
26 #include <iterator>
27 #include <memory>
28 #include <tuple>
29 #include <utility>
30 #include <vector>
31 
32 #include <fst/log.h>
33 
34 #include <fst/cache.h>
35 #include <fst/expanded-fst.h>
36 #include <fst/fst-decl.h> // For optional argument declarations
37 #include <fst/mapped-file.h>
38 #include <fst/matcher.h>
39 #include <fst/test-properties.h>
40 #include <fst/util.h>
41 
42 namespace fst {
43 
45  // The default caching behaviour is to do no caching. Most compactors are
46  // cheap and therefore we save memory by not doing caching.
48 
49  explicit CompactFstOptions(const CacheOptions &opts) : CacheOptions(opts) {}
50 };
51 
52 // New (Fst) Compactor interface - used by CompactFst. This interface
53 // allows complete flexibility in how the compaction is accomplished.
54 //
55 // class Compactor {
56 // public:
57 // // Constructor from the Fst to be compacted. If compactor is present,
58 // // only optional state should be copied from it. Examples of this
59 // // optional state include compression level or ArcCompactors.
60 // explicit Compactor(const Fst<Arc> &fst,
61 // shared_ptr<Compactor> compactor = nullptr);
62 // // Copy constructor. Must make a thread-safe copy suitable for use by
63 // // by Fst::Copy(/*safe=*/true). Only thread-unsafe data structures
64 // // need to be deeply copied. Ideally, this constructor is O(1) and any
65 // // large structures are thread-safe and shared, while small ones may
66 // // need to be copied.
67 // Compactor(const Compactor &compactor);
68 // // Default constructor (optional, see comment below).
69 // Compactor();
70 //
71 // // Returns the start state, number of states, and total number of arcs
72 // // of the compacted Fst
73 // StateId Start() const;
74 // StateId NumStates() const;
75 // size_t NumArcs() const;
76 //
77 // // Accessor class for state attributes.
78 // class State {
79 // public:
80 // State(); // Required, corresponds to kNoStateId.
81 // // This constructor may, of course, also take a const Compactor *
82 // // for the first argument. It is recommended to use const Compactor *
83 // // if possible, but this can be Compactor * if necessary.
84 // State(Compactor *c, StateId s); // Accessor for StateId 's'.
85 // StateId GetStateId() const;
86 // Weight Final() const;
87 // size_t NumArcs() const;
88 // // Gets the 'i'th arc for the state. Requires i < NumArcs().
89 // // Flags are a bitmask of the kArc*Value flags that ArcIterator uses.
90 // Arc GetArc(size_t i, uint8_t flags) const;
91 // };
92 //
93 // // Modifies 'state' accessor to provide access to state id 's'.
94 // void SetState(StateId s, State *state);
95 //
96 // // Tests whether 'fst' can be compacted by this compactor.
97 // template <typename A>
98 // bool IsCompatible(const Fst<A> &fst) const;
99 //
100 // // Returns the properties that are always when an FST with the
101 // // specified properties is compacted using this compactor.
102 // // This function should clear bits for properties that no longer
103 // // hold and set those for properties that are known to hold.
104 // uint64_t Properties(uint64_t props) const;
105 //
106 // // Returns a string identifying the type of compactor.
107 // static const std::string &Type();
108 //
109 // // Returns true if an error has occurred.
110 // bool Error() const;
111 //
112 // // Writes a compactor to a file.
113 // bool Write(std::ostream &strm, const FstWriteOptions &opts) const;
114 //
115 // // Reads a compactor from a file.
116 // static Compactor *Read(std::istream &strm, const FstReadOptions &opts,
117 // const FstHeader &hdr);
118 // };
119 //
120 
121 // Old ArcCompactor Interface:
122 //
123 // This interface is not deprecated; it, along with CompactArcStore and
124 // other Stores that implement its interface, is simply more constrained
125 // by essentially forcing the implementation to use an index array
126 // and an arc array, but giving flexibility in how those are implemented.
127 // This interface may still be useful and more convenient if that is the
128 // desired representation.
129 //
130 // The ArcCompactor class determines how arcs and final weights are compacted
131 // and expanded.
132 //
133 // Final weights are treated as transitions to the superfinal state, i.e.,
134 // ilabel = olabel = kNoLabel and nextstate = kNoStateId.
135 //
136 // There are two types of compactors:
137 //
138 // * Fixed out-degree compactors: 'compactor.Size()' returns a positive integer
139 // 's'. An FST can be compacted by this compactor only if each state has
140 // exactly 's' outgoing transitions (counting a non-Zero() final weight as a
141 // transition). A typical example is a compactor for string FSTs, i.e.,
142 // 's == 1'.
143 //
144 // * Variable out-degree compactors: 'compactor.Size() == -1'. There are no
145 // out-degree restrictions for these compactors.
146 //
147 // Interface:
148 //
149 // class ArcCompactor {
150 // public:
151 // // Default constructor (optional, see comment below).
152 // ArcCompactor();
153 //
154 // // Copy constructor. Must make a thread-safe copy suitable for use by
155 // // by Fst::Copy(/*safe=*/true). Only thread-unsafe data structures
156 // // need to be deeply copied.
157 // ArcCompactor(const ArcCompactor &);
158 //
159 // // Element is the type of the compacted transitions.
160 // using Element = ...
161 //
162 // // Returns the compacted representation of a transition 'arc'
163 // // at a state 's'.
164 // Element Compact(StateId s, const Arc &arc);
165 //
166 // // Returns the transition at state 's' represented by the compacted
167 // // transition 'e'.
168 // Arc Expand(StateId s, const Element &e) const;
169 //
170 // // Returns -1 for variable out-degree compactors, and the mandatory
171 // // out-degree otherwise.
172 // ssize_t Size() const;
173 //
174 // // Tests whether an FST can be compacted by this compactor.
175 // bool Compatible(const Fst<A> &fst) const;
176 //
177 // // Returns the properties that are always true for an FST compacted using
178 // // this compactor. Any Fst with the inverse of these properties should
179 // // be incompatible.
180 // uint64_t Properties() const;
181 //
182 // // Returns a string identifying the type of compactor.
183 // static const std::string &Type();
184 //
185 // // Writes a compactor to a file.
186 // bool Write(std::ostream &strm) const;
187 //
188 // // Reads a compactor from a file.
189 // static ArcCompactor *Read(std::istream &strm);
190 // };
191 //
192 // The default constructor is only required for FST_REGISTER to work (i.e.,
193 // enabling Convert() and the command-line utilities to work with this new
194 // compactor). However, a default constructor always needs to be specified for
195 // this code to compile, but one can have it simply raise an error when called,
196 // like so:
197 //
198 // Compactor::Compactor() {
199 // FSTERROR() << "Compactor: No default constructor";
200 // }
201 
202 // Default implementation data for CompactArcCompactor. Only old-style
203 // ArcCompactors are supported because the CompactArcStore constructors
204 // use the old API.
205 //
206 // DefaultCompact store is thread-compatible, but not thread-safe.
207 // The copy constructor makes a thread-safe copy.
208 //
209 // The implementation contains two arrays: 'states_' and 'compacts_'.
210 //
211 // For fixed out-degree compactors, the 'states_' array is unallocated. The
212 // 'compacts_' array contains the compacted transitions. Its size is
213 // 'ncompacts_'. The outgoing transitions at a given state are stored
214 // consecutively. For a given state 's', its 'compactor.Size()' outgoing
215 // transitions (including a superfinal transition when 's' is final), are stored
216 // in positions ['s*compactor.Size()', '(s+1)*compactor.Size()').
217 //
218 // For variable out-degree compactors, the states_ array has size
219 // 'nstates_ + 1' and contains positions in the 'compacts_' array. For a
220 // given state 's', the compacted transitions of 's' are stored in positions
221 // ['states_[s]', 'states_[s + 1]') in 'compacts_'. By convention,
222 // 'states_[nstates_] == ncompacts_'.
223 //
224 // In both cases, the superfinal transitions (when 's' is final, i.e.,
225 // 'Final(s) != Weight::Zero()') are stored first.
226 //
227 // The unsigned type U is used to represent indices into the compacts_ array.
228 template <class Element, class Unsigned>
230  public:
231  CompactArcStore() = default;
232 
233  // Makes a thread-safe copy. O(1).
234  CompactArcStore(const CompactArcStore &) = default;
235 
236  template <class Arc, class ArcCompactor>
237  CompactArcStore(const Fst<Arc> &fst, const ArcCompactor &arc_compactor);
238 
239  template <class Iterator, class ArcCompactor>
240  CompactArcStore(const Iterator begin, const Iterator end,
241  const ArcCompactor &arc_compactor);
242 
243  ~CompactArcStore() = default;
244 
245  template <class ArcCompactor>
246  static CompactArcStore *Read(std::istream &strm, const FstReadOptions &opts,
247  const FstHeader &hdr,
248  const ArcCompactor &arc_compactor);
249 
250  bool Write(std::ostream &strm, const FstWriteOptions &opts) const;
251 
252  // Returns the starting index in 'compacts_' of the transitions
253  // for state 'i'. See class-level comment for further details.
254  // Requires that the CompactArcStore was constructed with a
255  // variable out-degree compactor. Requires 0 <= i <= NumStates().
256  // By convention, States(NumStates()) == NumCompacts().
257  Unsigned States(ssize_t i) const { return states_[i]; }
258 
259  // Returns the compacted Element at position i. See class-level comment
260  // for further details. Requires 0 <= i < NumCompacts().
261  const Element &Compacts(size_t i) const { return compacts_[i]; }
262 
263  size_t NumStates() const { return nstates_; }
264 
265  size_t NumCompacts() const { return ncompacts_; }
266 
267  size_t NumArcs() const { return narcs_; }
268 
269  ssize_t Start() const { return start_; }
270 
271  bool Error() const { return error_; }
272 
273  // Returns a string identifying the type of data storage container.
274  static const std::string &Type();
275 
276  private:
277  std::shared_ptr<MappedFile> states_region_;
278  std::shared_ptr<MappedFile> compacts_region_;
279  // Unowned pointer into states_region_.
280  Unsigned *states_ = nullptr;
281  // Unowned pointer into compacts_region_.
282  Element *compacts_ = nullptr;
283  size_t nstates_ = 0;
284  size_t ncompacts_ = 0;
285  size_t narcs_ = 0;
286  ssize_t start_ = kNoStateId;
287  bool error_ = false;
288 };
289 
290 template <class Element, class Unsigned>
291 template <class Arc, class ArcCompactor>
293  const Fst<Arc> &fst, const ArcCompactor &arc_compactor) {
294  using StateId = typename Arc::StateId;
295  using Weight = typename Arc::Weight;
296  start_ = fst.Start();
297  // Counts # of states and arcs.
298  StateId nfinals = 0;
299  for (StateIterator<Fst<Arc>> siter(fst); !siter.Done(); siter.Next()) {
300  ++nstates_;
301  const auto s = siter.Value();
302  narcs_ += fst.NumArcs(s);
303  if (fst.Final(s) != Weight::Zero()) ++nfinals;
304  }
305  if (arc_compactor.Size() == -1) {
306  states_region_ = fst::WrapUnique(MappedFile::Allocate(
307  sizeof(states_[0]) * (nstates_ + 1), alignof(decltype(states_[0]))));
308  states_ = static_cast<Unsigned *>(states_region_->mutable_data());
309  ncompacts_ = narcs_ + nfinals;
310  compacts_region_ = fst::WrapUnique(MappedFile::Allocate(
311  sizeof(compacts_[0]) * ncompacts_, alignof(decltype(compacts_[0]))));
312  compacts_ = static_cast<Element *>(compacts_region_->mutable_data());
313  states_[nstates_] = ncompacts_;
314  } else {
315  states_ = nullptr;
316  ncompacts_ = nstates_ * arc_compactor.Size();
317  if ((narcs_ + nfinals) != ncompacts_) {
318  FSTERROR() << "CompactArcStore: ArcCompactor incompatible with FST";
319  error_ = true;
320  return;
321  }
322  compacts_region_ = fst::WrapUnique(MappedFile::Allocate(
323  sizeof(compacts_[0]) * ncompacts_, alignof(decltype(compacts_[0]))));
324  compacts_ = static_cast<Element *>(compacts_region_->mutable_data());
325  }
326  size_t pos = 0;
327  size_t fpos = 0;
328  for (size_t s = 0; s < nstates_; ++s) {
329  fpos = pos;
330  if (arc_compactor.Size() == -1) states_[s] = pos;
331  if (fst.Final(s) != Weight::Zero()) {
332  compacts_[pos++] = arc_compactor.Compact(
333  s, Arc(kNoLabel, kNoLabel, fst.Final(s), kNoStateId));
334  }
335  for (ArcIterator<Fst<Arc>> aiter(fst, s); !aiter.Done(); aiter.Next()) {
336  compacts_[pos++] = arc_compactor.Compact(s, aiter.Value());
337  }
338  if ((arc_compactor.Size() != -1) && (pos != fpos + arc_compactor.Size())) {
339  FSTERROR() << "CompactArcStore: ArcCompactor incompatible with FST";
340  error_ = true;
341  return;
342  }
343  }
344  if (pos != ncompacts_) {
345  FSTERROR() << "CompactArcStore: ArcCompactor incompatible with FST";
346  error_ = true;
347  return;
348  }
349 }
350 
351 template <class Element, class Unsigned>
352 template <class Iterator, class ArcCompactor>
354  const Iterator begin, const Iterator end,
355  const ArcCompactor &arc_compactor) {
356  using Arc = typename ArcCompactor::Arc;
357  using Weight = typename Arc::Weight;
358  if (arc_compactor.Size() != -1) {
359  ncompacts_ = std::distance(begin, end);
360  if (arc_compactor.Size() == 1) {
361  // For strings, allows implicit final weight. Empty input is the empty
362  // string.
363  if (ncompacts_ == 0) {
364  ++ncompacts_;
365  } else {
366  const auto arc =
367  arc_compactor.Expand(ncompacts_ - 1, *(begin + (ncompacts_ - 1)));
368  if (arc.ilabel != kNoLabel) ++ncompacts_;
369  }
370  }
371  if (ncompacts_ % arc_compactor.Size()) {
372  FSTERROR() << "CompactArcStore: Size of input container incompatible"
373  << " with arc compactor";
374  error_ = true;
375  return;
376  }
377  if (ncompacts_ == 0) return;
378  start_ = 0;
379  nstates_ = ncompacts_ / arc_compactor.Size();
380  compacts_region_ = fst::WrapUnique(MappedFile::Allocate(
381  sizeof(compacts_[0]) * ncompacts_, alignof(decltype(compacts_[0]))));
382  compacts_ = static_cast<Element *>(compacts_region_->mutable_data());
383  size_t i = 0;
384  Iterator it = begin;
385  for (; it != end; ++it, ++i) {
386  compacts_[i] = *it;
387  if (arc_compactor.Expand(i, *it).ilabel != kNoLabel) ++narcs_;
388  }
389  if (i < ncompacts_) {
390  compacts_[i] = arc_compactor.Compact(
391  i, Arc(kNoLabel, kNoLabel, Weight::One(), kNoStateId));
392  }
393  } else {
394  if (std::distance(begin, end) == 0) return;
395  // Count # of states, arcs and compacts.
396  auto it = begin;
397  for (size_t i = 0; it != end; ++it, ++i) {
398  const auto arc = arc_compactor.Expand(i, *it);
399  if (arc.ilabel != kNoLabel) {
400  ++narcs_;
401  ++ncompacts_;
402  } else {
403  ++nstates_;
404  if (arc.weight != Weight::Zero()) ++ncompacts_;
405  }
406  }
407  start_ = 0;
408  compacts_region_ = fst::WrapUnique(MappedFile::Allocate(
409  sizeof(compacts_[0]) * ncompacts_, alignof(decltype(compacts_[0]))));
410  compacts_ = static_cast<Element *>(compacts_region_->mutable_data());
411  states_region_ = fst::WrapUnique(MappedFile::Allocate(
412  sizeof(states_[0]) * (nstates_ + 1), alignof(decltype(states_[0]))));
413  states_ = static_cast<Unsigned *>(states_region_->mutable_data());
414  states_[nstates_] = ncompacts_;
415  size_t i = 0;
416  size_t s = 0;
417  for (it = begin; it != end; ++it) {
418  const auto arc = arc_compactor.Expand(i, *it);
419  if (arc.ilabel != kNoLabel) {
420  compacts_[i++] = *it;
421  } else {
422  states_[s++] = i;
423  if (arc.weight != Weight::Zero()) compacts_[i++] = *it;
424  }
425  }
426  if ((s != nstates_) || (i != ncompacts_)) {
427  FSTERROR() << "CompactArcStore: Ill-formed input container";
428  error_ = true;
429  return;
430  }
431  }
432 }
433 
434 template <class Element, class Unsigned>
435 template <class ArcCompactor>
437  std::istream &strm, const FstReadOptions &opts, const FstHeader &hdr,
438  const ArcCompactor &arc_compactor) {
439  auto data = std::make_unique<CompactArcStore>();
440  data->start_ = hdr.Start();
441  data->nstates_ = hdr.NumStates();
442  data->narcs_ = hdr.NumArcs();
443  if (arc_compactor.Size() == -1) {
444  if ((hdr.GetFlags() & FstHeader::IS_ALIGNED) && !AlignInput(strm)) {
445  LOG(ERROR) << "CompactArcStore::Read: Alignment failed: " << opts.source;
446  return nullptr;
447  }
448  auto b = (data->nstates_ + 1) * sizeof(Unsigned);
449  data->states_region_.reset(MappedFile::Map(
450  strm, opts.mode == FstReadOptions::MAP, opts.source, b));
451  if (!strm || !data->states_region_) {
452  LOG(ERROR) << "CompactArcStore::Read: Read failed: " << opts.source;
453  return nullptr;
454  }
455  data->states_ =
456  static_cast<Unsigned *>(data->states_region_->mutable_data());
457  } else {
458  data->states_ = nullptr;
459  }
460  data->ncompacts_ = arc_compactor.Size() == -1
461  ? data->states_[data->nstates_]
462  : data->nstates_ * arc_compactor.Size();
463  if ((hdr.GetFlags() & FstHeader::IS_ALIGNED) && !AlignInput(strm)) {
464  LOG(ERROR) << "CompactArcStore::Read: Alignment failed: " << opts.source;
465  return nullptr;
466  }
467  size_t b = data->ncompacts_ * sizeof(Element);
468  data->compacts_region_.reset(
469  MappedFile::Map(strm, opts.mode == FstReadOptions::MAP, opts.source, b));
470  if (!strm || !data->compacts_region_) {
471  LOG(ERROR) << "CompactArcStore::Read: Read failed: " << opts.source;
472  return nullptr;
473  }
474  data->compacts_ =
475  static_cast<Element *>(data->compacts_region_->mutable_data());
476  return data.release();
477 }
478 
479 template <class Element, class Unsigned>
481  std::ostream &strm, const FstWriteOptions &opts) const {
482  if (states_) {
483  if (opts.align && !AlignOutput(strm)) {
484  LOG(ERROR) << "CompactArcStore::Write: Alignment failed: " << opts.source;
485  return false;
486  }
487  strm.write(reinterpret_cast<const char *>(states_),
488  (nstates_ + 1) * sizeof(Unsigned));
489  }
490  if (opts.align && !AlignOutput(strm)) {
491  LOG(ERROR) << "CompactArcStore::Write: Alignment failed: " << opts.source;
492  return false;
493  }
494  strm.write(reinterpret_cast<const char *>(compacts_),
495  ncompacts_ * sizeof(Element));
496  strm.flush();
497  if (!strm) {
498  LOG(ERROR) << "CompactArcStore::Write: Write failed: " << opts.source;
499  return false;
500  }
501  return true;
502 }
503 
504 template <class Element, class Unsigned>
506  static const std::string *const type = new std::string("compact");
507  return *type;
508 }
509 
510 template <class C, class U, class S>
512 
513 // Wraps an old-style arc compactor and a compact store as a new Fst compactor.
514 // The copy constructors of AC and S must make thread-safe copies and should
515 // be O(1).
516 template <class AC, class U,
517  class S /*= CompactArcStore<typename AC::Element, U>*/>
519  public:
520  using ArcCompactor = AC;
521  using Unsigned = U;
522  using CompactStore = S;
523  using Element = typename AC::Element;
524  using Arc = typename AC::Arc;
525  using StateId = typename Arc::StateId;
526  using Weight = typename Arc::Weight;
528  friend State;
529 
530  CompactArcCompactor() : arc_compactor_(nullptr), compact_store_(nullptr) {}
531 
532  // Constructs from Fst.
534  ArcCompactor &&arc_compactor = ArcCompactor())
536  fst, std::make_shared<ArcCompactor>(std::move(arc_compactor))) {}
537 
539  std::shared_ptr<ArcCompactor> arc_compactor)
540  : arc_compactor_(std::move(arc_compactor)),
541  compact_store_(std::make_shared<S>(fst, *arc_compactor_)) {}
542 
544  std::shared_ptr<CompactArcCompactor> compactor)
545  : arc_compactor_(compactor->arc_compactor_),
546  compact_store_(compactor->compact_store_ == nullptr
547  ? std::make_shared<S>(fst, *arc_compactor_)
548  : compactor->compact_store_) {}
549 
550  // Constructs from CompactStore.
551  CompactArcCompactor(std::shared_ptr<ArcCompactor> arc_compactor,
552  std::shared_ptr<CompactStore> compact_store)
553  : arc_compactor_(std::move(arc_compactor)),
554  compact_store_(std::move(compact_store)) {}
555 
556  // The following 2 constructors take as input two iterators delimiting a set
557  // of (already) compacted transitions, starting with the transitions out of
558  // the initial state. The format of the input differs for fixed out-degree
559  // and variable out-degree arc compactors.
560  //
561  // - For fixed out-degree arc compactors, the final weight (encoded as a
562  // compacted transition) needs to be given only for final states. All strings
563  // (arc compactor of size 1) will be assume to be terminated by a final state
564  // even when the final state is not implicitely given.
565  //
566  // - For variable out-degree arc compactors, the final weight (encoded as a
567  // compacted transition) needs to be given for all states and must appeared
568  // first in the list (for state s, final weight of s, followed by outgoing
569  // transitons in s).
570  //
571  // These 2 constructors allows the direct construction of a CompactArcFst
572  // without first creating a more memory-hungry regular FST. This is useful
573  // when memory usage is severely constrained.
574  //
575  // Usage:
576  // CompactArcFst<...> fst(
577  // std::make_shared<CompactArcFst<...>::Compactor>(b, e));
578  template <class Iterator>
579  CompactArcCompactor(const Iterator b, const Iterator e,
580  std::shared_ptr<ArcCompactor> arc_compactor)
581  : arc_compactor_(std::move(arc_compactor)),
582  compact_store_(std::make_shared<S>(b, e, *arc_compactor_)) {}
583 
584  template <class Iterator>
585  CompactArcCompactor(const Iterator b, const Iterator e)
586  : CompactArcCompactor(b, e, std::make_shared<ArcCompactor>()) {}
587 
588  // Copy constructor. This makes a thread-safe copy, so requires that
589  // The ArcCompactor and CompactStore copy constructors make thread-safe
590  // copies.
592  : arc_compactor_(
593  compactor.GetArcCompactor() == nullptr
594  ? nullptr
595  : std::make_shared<ArcCompactor>(*compactor.GetArcCompactor())),
596  compact_store_(compactor.GetCompactStore() == nullptr
597  ? nullptr
598  : std::make_shared<CompactStore>(
599  *compactor.GetCompactStore())) {}
600 
601  template <class OtherC>
603  const CompactArcCompactor<OtherC, U, S> &compactor)
604  : arc_compactor_(
605  compactor.GetArcCompactor() == nullptr
606  ? nullptr
607  : std::make_shared<ArcCompactor>(*compactor.GetArcCompactor())),
608  compact_store_(compactor.GetCompactStore() == nullptr
609  ? nullptr
610  : std::make_shared<CompactStore>(
611  *compactor.GetCompactStore())) {}
612 
613  StateId Start() const { return compact_store_->Start(); }
614  StateId NumStates() const { return compact_store_->NumStates(); }
615  size_t NumArcs() const { return compact_store_->NumArcs(); }
616 
617  void SetState(StateId s, State *state) const {
618  if (state->GetStateId() != s) state->Set(this, s);
619  }
620 
621  static CompactArcCompactor *Read(std::istream &strm,
622  const FstReadOptions &opts,
623  const FstHeader &hdr) {
624  std::shared_ptr<ArcCompactor> arc_compactor(ArcCompactor::Read(strm));
625  if (arc_compactor == nullptr) return nullptr;
626  std::shared_ptr<S> compact_store(S::Read(strm, opts, hdr, *arc_compactor));
627  if (compact_store == nullptr) return nullptr;
628  return new CompactArcCompactor(arc_compactor, compact_store);
629  }
630 
631  bool Write(std::ostream &strm, const FstWriteOptions &opts) const {
632  return arc_compactor_->Write(strm) && compact_store_->Write(strm, opts);
633  }
634 
635  uint64_t Properties(uint64_t props) const {
636  // ArcCompactor properties can just be or-ed in since it is assumed that
637  // if the ArcCompactor sets a property, any FST with the inverse
638  // property is incompatible.
639  return arc_compactor_->Properties() | props;
640  }
641 
642  bool IsCompatible(const Fst<Arc> &fst) const {
643  return arc_compactor_->Compatible(fst);
644  }
645 
646  bool Error() const { return compact_store_->Error(); }
647 
648  bool HasFixedOutdegree() const { return arc_compactor_->Size() != -1; }
649 
650  static const std::string &Type() {
651  static const std::string *const type = [] {
652  std::string type = "compact";
653  if (sizeof(U) != sizeof(uint32_t)) type += std::to_string(8 * sizeof(U));
654  type += "_";
655  type += ArcCompactor::Type();
656  if (CompactStore::Type() != "compact") {
657  type += "_";
658  type += CompactStore::Type();
659  }
660  return new std::string(type);
661  }();
662  return *type;
663  }
664 
665  const ArcCompactor *GetArcCompactor() const { return arc_compactor_.get(); }
666  const CompactStore *GetCompactStore() const { return compact_store_.get(); }
667 
668  ArcCompactor *MutableArcCompactor() { return arc_compactor_.get(); }
669  CompactStore *MutableCompactStore() { return compact_store_.get(); }
670 
671  std::shared_ptr<ArcCompactor> SharedArcCompactor() { return arc_compactor_; }
672  std::shared_ptr<CompactStore> SharedCompactStore() { return compact_store_; }
673 
674  // TODO(allauzen): remove dependencies on this method and make private.
675  Arc ComputeArc(StateId s, Unsigned i, uint8_t flags) const {
676  return arc_compactor_->Expand(s, compact_store_->Compacts(i), flags);
677  }
678 
679  private:
680  std::pair<Unsigned, Unsigned> CompactsRange(StateId s) const {
681  std::pair<size_t, size_t> range;
682  if (HasFixedOutdegree()) {
683  range.first = s * arc_compactor_->Size();
684  range.second = arc_compactor_->Size();
685  } else {
686  range.first = compact_store_->States(s);
687  range.second = compact_store_->States(s + 1) - range.first;
688  }
689  return range;
690  }
691 
692  private:
693  std::shared_ptr<ArcCompactor> arc_compactor_;
694  std::shared_ptr<CompactStore> compact_store_;
695 };
696 
697 // Default implementation of state attributes accessor class for
698 // CompactArcCompactor. Use of efficient specialization strongly encouraged.
699 template <class ArcCompactor, class U, class S>
700 class CompactArcState {
701  public:
702  using Arc = typename ArcCompactor::Arc;
703  using StateId = typename Arc::StateId;
704  using Weight = typename Arc::Weight;
706 
707  CompactArcState() = default;
708 
709  CompactArcState(const Compactor *compactor, StateId s)
710  : compactor_(compactor),
711  s_(s),
712  range_(compactor->CompactsRange(s)),
713  has_final_(
714  range_.second != 0 &&
715  compactor->ComputeArc(s, range_.first, kArcILabelValue).ilabel ==
716  kNoLabel) {
717  if (has_final_) {
718  ++range_.first;
719  --range_.second;
720  }
721  }
722 
723  void Set(const Compactor *compactor, StateId s) {
724  compactor_ = compactor;
725  s_ = s;
726  range_ = compactor->CompactsRange(s);
727  if (range_.second != 0 &&
728  compactor->ComputeArc(s, range_.first, kArcILabelValue).ilabel ==
729  kNoLabel) {
730  has_final_ = true;
731  ++range_.first;
732  --range_.second;
733  } else {
734  has_final_ = false;
735  }
736  }
737 
738  StateId GetStateId() const { return s_; }
739 
740  Weight Final() const {
741  if (!has_final_) return Weight::Zero();
742  return compactor_->ComputeArc(s_, range_.first - 1, kArcWeightValue).weight;
743  }
744 
745  size_t NumArcs() const { return range_.second; }
746 
747  Arc GetArc(size_t i, uint8_t flags) const {
748  return compactor_->ComputeArc(s_, range_.first + i, flags);
749  }
750 
751  private:
752  const Compactor *compactor_ = nullptr; // borrowed ref.
753  StateId s_ = kNoStateId;
754  std::pair<U, U> range_ = {0, 0};
755  bool has_final_ = false;
756 };
757 
758 // Specialization for CompactArcStore.
759 template <class ArcCompactor, class U>
760 class CompactArcState<ArcCompactor, U,
761  CompactArcStore<typename ArcCompactor::Element, U>> {
762  public:
763  using Arc = typename ArcCompactor::Arc;
764  using StateId = typename Arc::StateId;
765  using Weight = typename Arc::Weight;
768 
769  CompactArcState() = default;
770 
771  CompactArcState(const Compactor *compactor, StateId s)
772  : arc_compactor_(compactor->GetArcCompactor()), s_(s) {
773  Init(compactor);
774  }
775 
776  void Set(const Compactor *compactor, StateId s) {
777  arc_compactor_ = compactor->GetArcCompactor();
778  s_ = s;
779  has_final_ = false;
780  Init(compactor);
781  }
782 
783  StateId GetStateId() const { return s_; }
784 
785  Weight Final() const {
786  if (!has_final_) return Weight::Zero();
787  return arc_compactor_->Expand(s_, *(compacts_ - 1), kArcWeightValue).weight;
788  }
789 
790  size_t NumArcs() const { return num_arcs_; }
791 
792  Arc GetArc(size_t i, uint8_t flags) const {
793  return arc_compactor_->Expand(s_, compacts_[i], flags);
794  }
795 
796  private:
797  void Init(const Compactor *compactor) {
798  const auto *store = compactor->GetCompactStore();
799  U offset;
800  if (!compactor->HasFixedOutdegree()) { // Variable out-degree compactor.
801  offset = store->States(s_);
802  num_arcs_ = store->States(s_ + 1) - offset;
803  } else { // Fixed out-degree compactor.
804  offset = s_ * arc_compactor_->Size();
805  num_arcs_ = arc_compactor_->Size();
806  }
807  if (num_arcs_ > 0) {
808  compacts_ = &(store->Compacts(offset));
809  if (arc_compactor_->Expand(s_, *compacts_, kArcILabelValue).ilabel ==
810  kNoStateId) {
811  ++compacts_;
812  --num_arcs_;
813  has_final_ = true;
814  }
815  }
816  }
817 
818  private:
819  const ArcCompactor *arc_compactor_ = nullptr; // Borrowed reference.
820  const typename ArcCompactor::Element *compacts_ =
821  nullptr; // Borrowed reference.
822  StateId s_ = kNoStateId;
823  U num_arcs_ = 0;
824  bool has_final_ = false;
825 };
826 
827 template <class F, class G>
828 void Cast(const F &, G *);
829 
830 template <class CompactArcFST, class FST>
831 bool WriteCompactArcFst(
832  const FST &fst,
833  const typename CompactArcFST::Compactor::ArcCompactor &arc_compactor,
834  std::ostream &strm, const FstWriteOptions &opts);
835 
836 namespace internal {
837 
838 // Implementation class for CompactFst, which contains parametrizeable
839 // Fst data storage (CompactArcStore by default) and Fst cache.
840 // C's copy constructor must make a thread-safe copy.
841 template <class Arc, class C, class CacheStore = DefaultCacheStore<Arc>>
843  : public CacheBaseImpl<typename CacheStore::State, CacheStore> {
844  public:
845  using Weight = typename Arc::Weight;
846  using StateId = typename Arc::StateId;
847  using Compactor = C;
848 
849  using FstImpl<Arc>::SetType;
855 
857  using ImplBase::HasArcs;
858  using ImplBase::HasFinal;
859  using ImplBase::HasStart;
860  using ImplBase::PushArc;
861  using ImplBase::SetArcs;
862  using ImplBase::SetFinal;
863  using ImplBase::SetStart;
864 
867  compactor_(std::make_shared<Compactor>()) {
868  SetType(Compactor::Type());
869  SetProperties(kNullProperties | kStaticProperties);
870  }
871 
872  // Constructs a CompactFstImpl, creating a new Compactor using
873  // Compactor(fst, compactor); this uses the compactor arg only for optional
874  // information, such as compression level. See the Compactor interface
875  // description.
876  CompactFstImpl(const Fst<Arc> &fst, std::shared_ptr<Compactor> compactor,
877  const CompactFstOptions &opts)
878  : ImplBase(opts),
879  compactor_(std::make_shared<Compactor>(fst, std::move(compactor))) {
880  SetType(Compactor::Type());
881  SetInputSymbols(fst.InputSymbols());
882  SetOutputSymbols(fst.OutputSymbols());
883  if (compactor_->Error()) SetProperties(kError, kError);
884  uint64_t copy_properties =
885  fst.Properties(kMutable, false)
886  ? fst.Properties(kCopyProperties, true)
887  : CheckProperties(
890  if ((copy_properties & kError) || !compactor_->IsCompatible(fst)) {
891  FSTERROR() << "CompactFstImpl: Input Fst incompatible with compactor";
892  SetProperties(kError, kError);
893  return;
894  }
895  SetProperties(compactor_->Properties(copy_properties) | kStaticProperties);
896  }
897 
898  CompactFstImpl(std::shared_ptr<Compactor> compactor,
899  const CompactFstOptions &opts)
900  : ImplBase(opts), compactor_(std::move(compactor)) {
901  SetType(Compactor::Type());
902  SetProperties(kStaticProperties | compactor_->Properties(0));
903  if (compactor_->Error()) SetProperties(kError, kError);
904  }
905 
906  // Makes a thread-safe copy; requires that Compactor's copy constructor
907  // does so as well.
909  : ImplBase(impl),
910  compactor_(impl.compactor_ == nullptr
911  ? std::make_shared<Compactor>()
912  : std::make_shared<Compactor>(*impl.compactor_)) {
913  SetType(impl.Type());
914  SetProperties(impl.Properties());
915  SetInputSymbols(impl.InputSymbols());
916  SetOutputSymbols(impl.OutputSymbols());
917  }
918 
919  // Allows to change the cache store from OtherCacheStore to CacheStore.
920  template <class OtherCacheStore>
921  explicit CompactFstImpl(
923  : ImplBase(CacheOptions(impl.GetCacheGc(), impl.GetCacheLimit())),
924  compactor_(impl.compactor_ == nullptr
925  ? std::make_shared<Compactor>()
926  : std::make_shared<Compactor>(*impl.compactor_)) {
927  SetType(impl.Type());
928  SetProperties(impl.Properties());
929  SetInputSymbols(impl.InputSymbols());
930  SetOutputSymbols(impl.OutputSymbols());
931  }
932 
934  if (!HasStart()) SetStart(compactor_->Start());
935  return ImplBase::Start();
936  }
937 
939  if (HasFinal(s)) return ImplBase::Final(s);
940  compactor_->SetState(s, &state_);
941  return state_.Final();
942  }
943 
944  StateId NumStates() const {
945  if (Properties(kError)) return 0;
946  return compactor_->NumStates();
947  }
948 
949  size_t NumArcs(StateId s) {
950  if (HasArcs(s)) return ImplBase::NumArcs(s);
951  compactor_->SetState(s, &state_);
952  return state_.NumArcs();
953  }
954 
956  if (!HasArcs(s) && !Properties(kILabelSorted)) Expand(s);
957  if (HasArcs(s)) return ImplBase::NumInputEpsilons(s);
958  return CountEpsilons(s, false);
959  }
960 
962  if (!HasArcs(s) && !Properties(kOLabelSorted)) Expand(s);
963  if (HasArcs(s)) return ImplBase::NumOutputEpsilons(s);
964  return CountEpsilons(s, true);
965  }
966 
967  size_t CountEpsilons(StateId s, bool output_epsilons) {
968  compactor_->SetState(s, &state_);
969  const uint8_t flags = output_epsilons ? kArcOLabelValue : kArcILabelValue;
970  size_t num_eps = 0;
971  const size_t num_arcs = state_.NumArcs();
972  for (size_t i = 0; i < num_arcs; ++i) {
973  const auto &arc = state_.GetArc(i, flags);
974  const auto label = output_epsilons ? arc.olabel : arc.ilabel;
975  if (label == 0) {
976  ++num_eps;
977  } else if (label > 0) {
978  break;
979  }
980  }
981  return num_eps;
982  }
983 
984  static CompactFstImpl *Read(std::istream &strm, const FstReadOptions &opts) {
985  auto impl = std::make_unique<CompactFstImpl>();
986  FstHeader hdr;
987  if (!impl->ReadHeader(strm, opts, kMinFileVersion, &hdr)) {
988  return nullptr;
989  }
990  // Ensures compatibility.
991  if (hdr.Version() == kAlignedFileVersion) {
992  hdr.SetFlags(hdr.GetFlags() | FstHeader::IS_ALIGNED);
993  }
994  impl->compactor_ =
995  std::shared_ptr<Compactor>(Compactor::Read(strm, opts, hdr));
996  if (!impl->compactor_) {
997  return nullptr;
998  }
999  return impl.release();
1000  }
1001 
1002  bool Write(std::ostream &strm, const FstWriteOptions &opts) const {
1003  FstHeader hdr;
1004  hdr.SetStart(compactor_->Start());
1005  hdr.SetNumStates(compactor_->NumStates());
1006  hdr.SetNumArcs(compactor_->NumArcs());
1007  // Ensures compatibility.
1008  const auto file_version = opts.align ? kAlignedFileVersion : kFileVersion;
1009  WriteHeader(strm, opts, file_version, &hdr);
1010  return compactor_->Write(strm, opts);
1011  }
1012 
1013  // Provides information needed for generic state iterator.
1015  data->base = nullptr;
1016  data->nstates = compactor_->NumStates();
1017  }
1018 
1020  if (!HasArcs(s)) Expand(s);
1021  ImplBase::InitArcIterator(s, data);
1022  }
1023 
1024  void Expand(StateId s) {
1025  compactor_->SetState(s, &state_);
1026  const size_t num_arcs = state_.NumArcs();
1027  for (size_t i = 0; i < num_arcs; ++i)
1028  PushArc(s, state_.GetArc(i, kArcValueFlags));
1029  SetArcs(s);
1030  if (!HasFinal(s)) SetFinal(s, state_.Final());
1031  }
1032 
1033  const Compactor *GetCompactor() const { return compactor_.get(); }
1034  Compactor *MutableCompactor() { return compactor_.get(); }
1035  std::shared_ptr<Compactor> SharedCompactor() { return compactor_; }
1036  void SetCompactor(std::shared_ptr<Compactor> compactor) {
1037  // TODO(allauzen): is this correct? is this needed?
1038  // TODO(allauzen): consider removing and forcing this through direct calls
1039  // to compactor.
1040  compactor_ = std::move(compactor);
1041  }
1042 
1043  // Properties always true of this FST class.
1044  static constexpr uint64_t kStaticProperties = kExpanded;
1045 
1046  protected:
1047  template <class OtherArc, class OtherCompactor, class OtherCacheStore>
1048  explicit CompactFstImpl(
1050  : compactor_(std::make_shared<Compactor>(*impl.GetCompactor())) {
1051  SetType(impl.Type());
1052  SetProperties(impl.Properties());
1053  SetInputSymbols(impl.InputSymbols());
1054  SetOutputSymbols(impl.OutputSymbols());
1055  }
1056 
1057  private:
1058  // For k*Version constants.
1059  template <class CompactArcFST, class FST>
1061  const FST &fst,
1062  const typename CompactArcFST::Compactor::ArcCompactor &arc_compactor,
1063  std::ostream &strm, const FstWriteOptions &opts);
1064 
1065  // Current unaligned file format version.
1066  static constexpr int kFileVersion = 2;
1067  // Current aligned file format version.
1068  static constexpr int kAlignedFileVersion = 1;
1069  // Minimum file format version supported.
1070  static constexpr int kMinFileVersion = 1;
1071 
1072  std::shared_ptr<Compactor> compactor_;
1073  typename Compactor::State state_;
1074 };
1075 
1076 // Returns the compactor for the CompactFst; intended to be called as
1077 // GetCompactor<CompactorType>(fst), which returns the compactor only if it
1078 // is of the specified type and otherwise nullptr (via the overload below).
1079 template <class Compactor, class Arc>
1080 const Compactor *GetCompactor(const CompactFst<Arc, Compactor> &fst) {
1081  return fst.GetCompactor();
1082 }
1083 
1084 template <class Compactor, class Arc>
1085 const Compactor *GetCompactor(const Fst<Arc> &fst) {
1086  return nullptr;
1087 }
1088 
1089 } // namespace internal
1090 
1091 // This class attaches interface to implementation and handles reference
1092 // counting, delegating most methods to ImplToExpandedFst.
1093 // (Template argument defaults are declared in fst-decl.h.)
1094 template <class A, class C, class CacheStore>
1096  : public ImplToExpandedFst<internal::CompactFstImpl<A, C, CacheStore>> {
1097  public:
1098  template <class F, class G>
1099  void friend Cast(const F &, G *);
1100 
1101  using Arc = A;
1102  using StateId = typename Arc::StateId;
1103  using Compactor = C;
1105  using Store = CacheStore; // for CacheArcIterator
1106 
1107  friend class StateIterator<CompactFst>;
1108  friend class ArcIterator<CompactFst>;
1109 
1110  CompactFst() : ImplToExpandedFst<Impl>(std::make_shared<Impl>()) {}
1111 
1112  explicit CompactFst(const Fst<Arc> &fst,
1113  const CompactFstOptions &opts = CompactFstOptions())
1114  : CompactFst(fst, std::make_shared<Compactor>(fst), opts) {}
1115 
1116  // Constructs a CompactFst, creating a new Compactor using
1117  // Compactor(fst, compactor); this uses the compactor arg only for optional
1118  // information, such as compression level. See the Compactor interface
1119  // description.
1120  CompactFst(const Fst<Arc> &fst, std::shared_ptr<Compactor> compactor,
1121  const CompactFstOptions &opts = CompactFstOptions())
1123  std::make_shared<Impl>(fst, std::move(compactor), opts)) {}
1124 
1125  // Convenience constructor taking a Compactor rvalue ref. Avoids
1126  // clutter of make_shared<Compactor> at call site.
1127  // Constructs a CompactFst, creating a new Compactor using
1128  // Compactor(fst, compactor); this uses the compactor arg only for optional
1129  // information, such as compression level. See the Compactor interface
1130  // description.
1131  CompactFst(const Fst<Arc> &fst, Compactor &&compactor,
1132  const CompactFstOptions &opts = CompactFstOptions())
1133  : CompactFst(fst, std::make_shared<Compactor>(std::move(compactor)),
1134  opts) {}
1135 
1136  explicit CompactFst(std::shared_ptr<Compactor> compactor,
1137  const CompactFstOptions &opts = CompactFstOptions())
1139  std::make_shared<Impl>(std::move(compactor), opts)) {}
1140 
1141  // See Fst<>::Copy() for doc.
1142  CompactFst(const CompactFst &fst, bool safe = false)
1143  : ImplToExpandedFst<Impl>(fst, safe) {}
1144 
1145  // Get a copy of this CompactFst. See Fst<>::Copy() for further doc.
1146  CompactFst *Copy(bool safe = false) const override {
1147  return new CompactFst(*this, safe);
1148  }
1149 
1150  // Read a CompactFst from an input stream; return nullptr on error
1151  static CompactFst *Read(std::istream &strm, const FstReadOptions &opts) {
1152  auto *impl = Impl::Read(strm, opts);
1153  return impl ? new CompactFst(std::shared_ptr<Impl>(impl)) : nullptr;
1154  }
1155 
1156  // Read a CompactFst from a file; return nullptr on error
1157  // Empty source reads from standard input
1158  static CompactFst *Read(const std::string &source) {
1159  auto *impl = ImplToExpandedFst<Impl>::Read(source);
1160  return impl ? new CompactFst(std::shared_ptr<Impl>(impl)) : nullptr;
1161  }
1162 
1163  bool Write(std::ostream &strm, const FstWriteOptions &opts) const override {
1164  return GetImpl()->Write(strm, opts);
1165  }
1166 
1167  bool Write(const std::string &source) const override {
1168  return Fst<Arc>::WriteFile(source);
1169  }
1170 
1171  void InitStateIterator(StateIteratorData<Arc> *data) const override {
1172  GetImpl()->InitStateIterator(data);
1173  }
1174 
1175  void InitArcIterator(StateId s, ArcIteratorData<Arc> *data) const override {
1176  GetMutableImpl()->InitArcIterator(s, data);
1177  }
1178 
1179  MatcherBase<Arc> *InitMatcher(MatchType match_type) const override {
1180  return new SortedMatcher<CompactFst>(*this, match_type);
1181  }
1182 
1183  const Compactor *GetCompactor() const { return GetImpl()->GetCompactor(); }
1184 
1185  void SetCompactor(std::shared_ptr<Compactor> compactor) {
1186  GetMutableImpl()->SetCompactor(std::move(compactor));
1187  }
1188 
1189  private:
1190  using ImplToFst<Impl, ExpandedFst<Arc>>::GetImpl;
1191  using ImplToFst<Impl, ExpandedFst<Arc>>::GetMutableImpl;
1192 
1193  explicit CompactFst(std::shared_ptr<Impl> impl)
1194  : ImplToExpandedFst<Impl>(std::move(impl)) {}
1195 
1196  CompactFst &operator=(const CompactFst &fst) = delete;
1197 };
1198 
1199 // Writes FST in ArcCompacted format, with a possible pass over the machine
1200 // before writing to compute the number of states and arcs.
1201 template <class CompactArcFST, class FST>
1203  const FST &fst,
1204  const typename CompactArcFST::Compactor::ArcCompactor &arc_compactor,
1205  std::ostream &strm, const FstWriteOptions &opts) {
1206  using Arc = typename CompactArcFST::Arc;
1207  using Compactor = typename CompactArcFST::Compactor;
1208  using ArcCompactor = typename Compactor::ArcCompactor;
1209  using CompactStore = typename Compactor::CompactStore;
1210  using Element = typename ArcCompactor::Element;
1211  using Impl = typename CompactArcFST::Impl;
1212  using Unsigned = typename Compactor::Unsigned;
1213  using Weight = typename Arc::Weight;
1214  const auto file_version =
1215  opts.align ? Impl::kAlignedFileVersion : Impl::kFileVersion;
1216  size_t num_arcs = -1;
1217  size_t num_states = -1;
1218  auto first_pass_arc_compactor = arc_compactor;
1219  // Note that GetCompactor will only return non-null if the compactor has the
1220  // exact type Compactor == CompactArcFst::Compactor. This is what we want;
1221  // other types must do an extra pass to set the arc compactor state.
1222  if (const Compactor *const compactor =
1223  internal::GetCompactor<Compactor>(fst)) {
1224  num_arcs = compactor->NumArcs();
1225  num_states = compactor->NumStates();
1226  first_pass_arc_compactor = *compactor->GetArcCompactor();
1227  } else {
1228  // A first pass is needed to compute the state of the compactor, which
1229  // is saved ahead of the rest of the data structures. This unfortunately
1230  // means forcing a complete double compaction when writing in this format.
1231  // TODO(allauzen): eliminate mutable state from compactors.
1232  num_arcs = 0;
1233  num_states = 0;
1234  for (StateIterator<FST> siter(fst); !siter.Done(); siter.Next()) {
1235  const auto s = siter.Value();
1236  ++num_states;
1237  if (fst.Final(s) != Weight::Zero()) {
1238  first_pass_arc_compactor.Compact(
1239  s, Arc(kNoLabel, kNoLabel, fst.Final(s), kNoStateId));
1240  }
1241  for (ArcIterator<FST> aiter(fst, s); !aiter.Done(); aiter.Next()) {
1242  ++num_arcs;
1243  first_pass_arc_compactor.Compact(s, aiter.Value());
1244  }
1245  }
1246  }
1247  FstHeader hdr;
1248  hdr.SetStart(fst.Start());
1249  hdr.SetNumStates(num_states);
1250  hdr.SetNumArcs(num_arcs);
1251  std::string type = "compact";
1252  if (sizeof(Unsigned) != sizeof(uint32_t)) {
1253  type += std::to_string(CHAR_BIT * sizeof(Unsigned));
1254  }
1255  type += "_";
1256  type += ArcCompactor::Type();
1257  if (CompactStore::Type() != "compact") {
1258  type += "_";
1259  type += CompactStore::Type();
1260  }
1261  const auto copy_properties = fst.Properties(kCopyProperties, true);
1262  if ((copy_properties & kError) || !arc_compactor.Compatible(fst)) {
1263  FSTERROR() << "Fst incompatible with compactor";
1264  return false;
1265  }
1266  uint64_t properties = copy_properties | Impl::kStaticProperties;
1267  internal::FstImpl<Arc>::WriteFstHeader(fst, strm, opts, file_version, type,
1268  properties, &hdr);
1269  first_pass_arc_compactor.Write(strm);
1270  if (first_pass_arc_compactor.Size() == -1) {
1271  if (opts.align && !AlignOutput(strm)) {
1272  LOG(ERROR) << "WriteCompactArcFst: Alignment failed: " << opts.source;
1273  return false;
1274  }
1275  Unsigned compacts = 0;
1276  for (StateIterator<FST> siter(fst); !siter.Done(); siter.Next()) {
1277  const auto s = siter.Value();
1278  strm.write(reinterpret_cast<const char *>(&compacts), sizeof(compacts));
1279  if (fst.Final(s) != Weight::Zero()) {
1280  ++compacts;
1281  }
1282  compacts += fst.NumArcs(s);
1283  }
1284  strm.write(reinterpret_cast<const char *>(&compacts), sizeof(compacts));
1285  }
1286  if (opts.align && !AlignOutput(strm)) {
1287  LOG(ERROR) << "Could not align file during write after writing states";
1288  }
1289  const auto &second_pass_arc_compactor = arc_compactor;
1290  Element element;
1291  for (StateIterator<FST> siter(fst); !siter.Done(); siter.Next()) {
1292  const auto s = siter.Value();
1293  if (fst.Final(s) != Weight::Zero()) {
1294  element = second_pass_arc_compactor.Compact(
1295  s, Arc(kNoLabel, kNoLabel, fst.Final(s), kNoStateId));
1296  strm.write(reinterpret_cast<const char *>(&element), sizeof(element));
1297  }
1298  for (ArcIterator<FST> aiter(fst, s); !aiter.Done(); aiter.Next()) {
1299  element = second_pass_arc_compactor.Compact(s, aiter.Value());
1300  strm.write(reinterpret_cast<const char *>(&element), sizeof(element));
1301  }
1302  }
1303  strm.flush();
1304  if (!strm) {
1305  LOG(ERROR) << "WriteCompactArcFst: Write failed: " << opts.source;
1306  return false;
1307  }
1308  return true;
1309 }
1310 
1311 // Specialization for CompactFst; see generic version in fst.h for sample
1312 // usage (but use the CompactFst type!). This version should inline.
1313 template <class Arc, class Compactor, class CacheStore>
1314 class StateIterator<CompactFst<Arc, Compactor, CacheStore>> {
1315  public:
1316  using StateId = typename Arc::StateId;
1317 
1319  : nstates_(fst.NumStates()), s_(0) {}
1320 
1321  bool Done() const { return s_ >= nstates_; }
1322 
1323  StateId Value() const { return s_; }
1324 
1325  void Next() { ++s_; }
1326 
1327  void Reset() { s_ = 0; }
1328 
1329  private:
1330  StateId nstates_;
1331  StateId s_;
1332 };
1333 
1334 // Specialization for CompactFst. Never caches,
1335 // always iterates over the underlying compact elements.
1336 template <class Arc, class Compactor, class CacheStore>
1337 class ArcIterator<CompactFst<Arc, Compactor, CacheStore>> {
1338  public:
1339  using StateId = typename Arc::StateId;
1340  using State = typename Compactor::State;
1341 
1343  : state_(fst.GetMutableImpl()->MutableCompactor(), s),
1344  pos_(0),
1345  num_arcs_(state_.NumArcs()),
1346  flags_(kArcValueFlags) {}
1347 
1348  bool Done() const { return pos_ >= num_arcs_; }
1349 
1350  const Arc &Value() const {
1351  arc_ = state_.GetArc(pos_, flags_);
1352  return arc_;
1353  }
1354 
1355  void Next() { ++pos_; }
1356 
1357  size_t Position() const { return pos_; }
1358 
1359  void Reset() { pos_ = 0; }
1360 
1361  void Seek(size_t pos) { pos_ = pos; }
1362 
1363  uint8_t Flags() const { return flags_; }
1364 
1365  void SetFlags(uint8_t flags, uint8_t mask) {
1366  flags_ &= ~mask;
1367  flags_ |= (flags & kArcValueFlags);
1368  }
1369 
1370  private:
1371  State state_;
1372  size_t pos_;
1373  // Cache the value of NumArcs(), since it is used in Done() and may be slow.
1374  size_t num_arcs_;
1375  mutable Arc arc_;
1376  uint8_t flags_;
1377 };
1378 
1379 // ArcCompactor for unweighted string FSTs.
1380 template <class A>
1382  public:
1383  using Arc = A;
1384  using Label = typename Arc::Label;
1385  using StateId = typename Arc::StateId;
1386  using Weight = typename Arc::Weight;
1387 
1388  using Element = Label;
1389 
1390  Element Compact(StateId s, const Arc &arc) const { return arc.ilabel; }
1391 
1392  Arc Expand(StateId s, const Element &p,
1393  uint8_t flags = kArcValueFlags) const {
1394  return Arc(p, p, Weight::One(), p != kNoLabel ? s + 1 : kNoStateId);
1395  }
1396 
1397  constexpr ssize_t Size() const { return 1; }
1398 
1399  constexpr uint64_t Properties() const { return kCompiledStringProperties; }
1400 
1401  bool Compatible(const Fst<Arc> &fst) const {
1402  const auto props = Properties();
1403  return fst.Properties(props, true) == props;
1404  }
1405 
1406  static const std::string &Type() {
1407  static const std::string *const type = new std::string("string");
1408  return *type;
1409  }
1410 
1411  bool Write(std::ostream &strm) const { return true; }
1412 
1413  static StringCompactor *Read(std::istream &strm) {
1414  return new StringCompactor;
1415  }
1416 };
1417 
1418 // ArcCompactor for weighted string FSTs.
1419 template <class A>
1421  public:
1422  using Arc = A;
1423  using Label = typename Arc::Label;
1424  using StateId = typename Arc::StateId;
1425  using Weight = typename Arc::Weight;
1426 
1427  using Element = std::pair<Label, Weight>;
1428 
1429  Element Compact(StateId s, const Arc &arc) const {
1430  return std::make_pair(arc.ilabel, arc.weight);
1431  }
1432 
1433  Arc Expand(StateId s, const Element &p,
1434  uint8_t flags = kArcValueFlags) const {
1435  return Arc(p.first, p.first, p.second,
1436  p.first != kNoLabel ? s + 1 : kNoStateId);
1437  }
1438 
1439  constexpr ssize_t Size() const { return 1; }
1440 
1441  constexpr uint64_t Properties() const { return kString | kAcceptor; }
1442 
1443  bool Compatible(const Fst<Arc> &fst) const {
1444  const auto props = Properties();
1445  return fst.Properties(props, true) == props;
1446  }
1447 
1448  static const std::string &Type() {
1449  static const std::string *const type = new std::string("weighted_string");
1450  return *type;
1451  }
1452 
1453  bool Write(std::ostream &strm) const { return true; }
1454 
1455  static WeightedStringCompactor *Read(std::istream &strm) {
1456  return new WeightedStringCompactor;
1457  }
1458 };
1459 
1460 // ArcCompactor for unweighted acceptor FSTs.
1461 template <class A>
1463  public:
1464  using Arc = A;
1465  using Label = typename Arc::Label;
1466  using StateId = typename Arc::StateId;
1467  using Weight = typename Arc::Weight;
1468 
1469  using Element = std::pair<Label, StateId>;
1470 
1471  Element Compact(StateId s, const Arc &arc) const {
1472  return std::make_pair(arc.ilabel, arc.nextstate);
1473  }
1474 
1475  Arc Expand(StateId s, const Element &p,
1476  uint8_t flags = kArcValueFlags) const {
1477  return Arc(p.first, p.first, Weight::One(), p.second);
1478  }
1479 
1480  constexpr ssize_t Size() const { return -1; }
1481 
1482  constexpr uint64_t Properties() const { return kAcceptor | kUnweighted; }
1483 
1484  bool Compatible(const Fst<Arc> &fst) const {
1485  const auto props = Properties();
1486  return fst.Properties(props, true) == props;
1487  }
1488 
1489  static const std::string &Type() {
1490  static const std::string *const type =
1491  new std::string("unweighted_acceptor");
1492  return *type;
1493  }
1494 
1495  bool Write(std::ostream &strm) const { return true; }
1496 
1497  static UnweightedAcceptorCompactor *Read(std::istream &istrm) {
1498  return new UnweightedAcceptorCompactor;
1499  }
1500 };
1501 
1502 // ArcCompactor for weighted acceptor FSTs.
1503 template <class A>
1505  public:
1506  using Arc = A;
1507  using Label = typename Arc::Label;
1508  using StateId = typename Arc::StateId;
1509  using Weight = typename Arc::Weight;
1510 
1511  using Element = std::pair<std::pair<Label, Weight>, StateId>;
1512 
1513  Element Compact(StateId s, const Arc &arc) const {
1514  return std::make_pair(std::make_pair(arc.ilabel, arc.weight),
1515  arc.nextstate);
1516  }
1517 
1518  Arc Expand(StateId s, const Element &p,
1519  uint8_t flags = kArcValueFlags) const {
1520  return Arc(p.first.first, p.first.first, p.first.second, p.second);
1521  }
1522 
1523  constexpr ssize_t Size() const { return -1; }
1524 
1525  constexpr uint64_t Properties() const { return kAcceptor; }
1526 
1527  bool Compatible(const Fst<Arc> &fst) const {
1528  const auto props = Properties();
1529  return fst.Properties(props, true) == props;
1530  }
1531 
1532  static const std::string &Type() {
1533  static const std::string *const type = new std::string("acceptor");
1534  return *type;
1535  }
1536 
1537  bool Write(std::ostream &strm) const { return true; }
1538 
1539  static AcceptorCompactor *Read(std::istream &strm) {
1540  return new AcceptorCompactor;
1541  }
1542 };
1543 
1544 // ArcCompactor for unweighted FSTs.
1545 template <class A>
1547  public:
1548  using Arc = A;
1549  using Label = typename Arc::Label;
1550  using StateId = typename Arc::StateId;
1551  using Weight = typename Arc::Weight;
1552 
1553  using Element = std::pair<std::pair<Label, Label>, StateId>;
1554 
1555  Element Compact(StateId s, const Arc &arc) const {
1556  return std::make_pair(std::make_pair(arc.ilabel, arc.olabel),
1557  arc.nextstate);
1558  }
1559 
1560  Arc Expand(StateId s, const Element &p,
1561  uint8_t flags = kArcValueFlags) const {
1562  return Arc(p.first.first, p.first.second, Weight::One(), p.second);
1563  }
1564 
1565  constexpr ssize_t Size() const { return -1; }
1566 
1567  constexpr uint64_t Properties() const { return kUnweighted; }
1568 
1569  bool Compatible(const Fst<Arc> &fst) const {
1570  const auto props = Properties();
1571  return fst.Properties(props, true) == props;
1572  }
1573 
1574  static const std::string &Type() {
1575  static const std::string *const type = new std::string("unweighted");
1576  return *type;
1577  }
1578 
1579  bool Write(std::ostream &strm) const { return true; }
1580 
1581  static UnweightedCompactor *Read(std::istream &strm) {
1582  return new UnweightedCompactor;
1583  }
1584 };
1585 
1586 template <class Arc, class Unsigned /* = uint32_t */>
1588 
1589 template <class Arc, class Unsigned /* = uint32_t */>
1592 
1593 template <class Arc, class Unsigned /* = uint32_t */>
1595 
1596 template <class Arc, class Unsigned /* = uint32_t */>
1597 using CompactUnweightedFst =
1599 
1600 template <class Arc, class Unsigned /* = uint32_t */>
1603 
1605 
1607 
1609 
1611 
1614 
1615 // Convenience function to make a CompactStringFst from a sequence
1616 // of Arc::Labels. LabelIterator must be an input iterator.
1617 template <class Arc, class Unsigned = uint32_t, class LabelIterator>
1619  const LabelIterator begin, const LabelIterator end) {
1621  using Compactor = typename CompactStringFst::Compactor;
1622  return CompactStringFst(std::make_shared<Compactor>(begin, end));
1623 }
1624 
1625 template <class LabelIterator>
1626 inline StdCompactStringFst MakeStdCompactStringFst(const LabelIterator begin,
1627  const LabelIterator end) {
1628  return MakeCompactStringFst<StdArc>(begin, end);
1629 }
1630 
1631 } // namespace fst
1632 
1633 #endif // FST_COMPACT_FST_H_
static Impl * Read(std::istream &strm, const FstReadOptions &opts)
Definition: expanded-fst.h:145
ssize_t NumOutputEpsilons(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
Definition: expanded-fst.h:114
Weight Final() const
Definition: compact-fst.h:740
CompactFstImpl(const Fst< Arc > &fst, std::shared_ptr< Compactor > compactor, const CompactFstOptions &opts)
Definition: compact-fst.h:876
constexpr uint64_t Properties() const
Definition: compact-fst.h:1441
CompactArcCompactor(const Fst< Arc > &fst, std::shared_ptr< ArcCompactor > arc_compactor)
Definition: compact-fst.h:538
bool AlignInput(std::istream &strm, size_t align=MappedFile::kArchAlignment)
Definition: util.cc:81
void InitArcIterator(StateId s, ArcIteratorData< Arc > *data) const override
Definition: compact-fst.h:1175
const Element & Compacts(size_t i) const
Definition: compact-fst.h:261
constexpr uint64_t kMutable
Definition: properties.h:48
StdCompactStringFst MakeStdCompactStringFst(const LabelIterator begin, const LabelIterator end)
Definition: compact-fst.h:1626
constexpr ssize_t Size() const
Definition: compact-fst.h:1397
constexpr uint64_t kWeightedCycles
Definition: properties.h:141
constexpr uint64_t Properties() const
Definition: compact-fst.h:1525
std::pair< std::pair< Label, Label >, StateId > Element
Definition: compact-fst.h:1553
constexpr uint8_t kArcValueFlags
Definition: fst.h:453
CompactFst(const CompactFst &fst, bool safe=false)
Definition: compact-fst.h:1142
static const std::string & Type()
Definition: compact-fst.h:1574
typename Arc::Weight Weight
Definition: compact-fst.h:1551
constexpr int kNoLabel
Definition: fst.h:201
static UnweightedCompactor * Read(std::istream &strm)
Definition: compact-fst.h:1581
Arc GetArc(size_t i, uint8_t flags) const
Definition: compact-fst.h:747
CompactStore * MutableCompactStore()
Definition: compact-fst.h:669
void Cast(const F &, G *)
bool IsCompatible(const Fst< Arc > &fst) const
Definition: compact-fst.h:642
bool Compatible(const Fst< Arc > &fst) const
Definition: compact-fst.h:1484
virtual uint64_t Properties(uint64_t mask, bool test) const =0
const Compactor * GetCompactor() const
Definition: compact-fst.h:1033
typename Arc::StateId StateId
Definition: compact-fst.h:703
typename Arc::Label Label
Definition: compact-fst.h:1549
Arc Expand(StateId s, const Element &p, uint8_t flags=kArcValueFlags) const
Definition: compact-fst.h:1433
static const std::string & Type()
Definition: compact-fst.h:1448
CompactFst(const Fst< Arc > &fst, const CompactFstOptions &opts=CompactFstOptions())
Definition: compact-fst.h:1112
std::shared_ptr< CompactStore > SharedCompactStore()
Definition: compact-fst.h:672
CompactFstOptions(const CacheOptions &opts)
Definition: compact-fst.h:49
virtual size_t NumArcs(StateId) const =0
Element Compact(StateId s, const Arc &arc) const
Definition: compact-fst.h:1555
CompactFstImpl(std::shared_ptr< Compactor > compactor, const CompactFstOptions &opts)
Definition: compact-fst.h:898
void Set(const Compactor *compactor, StateId s)
Definition: compact-fst.h:723
Arc Expand(StateId s, const Element &p, uint8_t flags=kArcValueFlags) const
Definition: compact-fst.h:1392
bool Write(std::ostream &strm) const
Definition: compact-fst.h:1579
Element Compact(StateId s, const Arc &arc) const
Definition: compact-fst.h:1390
bool Write(std::ostream &strm) const
Definition: compact-fst.h:1453
std::string source
Definition: fst.h:74
CompactArcCompactor(const CompactArcCompactor &compactor)
Definition: compact-fst.h:591
CompactStringFst< Arc, Unsigned > MakeCompactStringFst(const LabelIterator begin, const LabelIterator end)
Definition: compact-fst.h:1618
Arc::Weight Final(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
Definition: expanded-fst.h:97
CompactArcFst< Arc, StringCompactor< Arc >, Unsigned > CompactStringFst
Definition: compact-fst.h:1587
const SymbolTable * OutputSymbols() const
Definition: fst.h:762
bool Write(std::ostream &strm) const
Definition: compact-fst.h:1411
MatchType
Definition: fst.h:193
constexpr uint64_t Properties() const
Definition: compact-fst.h:1399
StateId GetStateId() const
Definition: compact-fst.h:738
constexpr uint64_t kError
Definition: properties.h:51
void InitArcIterator(StateId s, ArcIteratorData< Arc > *data)
Definition: compact-fst.h:1019
static CompactFst * Read(const std::string &source)
Definition: compact-fst.h:1158
CompactFst(std::shared_ptr< Compactor > compactor, const CompactFstOptions &opts=CompactFstOptions())
Definition: compact-fst.h:1136
static MappedFile * Map(std::istream &istrm, bool memorymap, const std::string &source, size_t size)
Definition: mapped-file.cc:74
#define LOG(type)
Definition: log.h:49
constexpr uint64_t kCompiledStringProperties
Definition: properties.h:156
virtual Weight Final(StateId) const =0
StateIterator(const CompactFst< Arc, Compactor, CacheStore > &fst)
Definition: compact-fst.h:1318
CompactFst(const Fst< Arc > &fst, Compactor &&compactor, const CompactFstOptions &opts=CompactFstOptions())
Definition: compact-fst.h:1131
size_t NumArcs() const
Definition: compact-fst.h:267
SetType
Definition: set-weight.h:52
typename Arc::StateId StateId
Definition: compact-fst.h:1550
void SetNumArcs(int64_t numarcs)
Definition: fst.h:172
constexpr uint64_t kUnweightedCycles
Definition: properties.h:144
CompactArcCompactor(const Fst< Arc > &fst, ArcCompactor &&arc_compactor=ArcCompactor())
Definition: compact-fst.h:533
bool AlignOutput(std::ostream &strm, size_t align=MappedFile::kArchAlignment)
Definition: util.cc:97
CompactArcStore()=default
static AcceptorCompactor * Read(std::istream &strm)
Definition: compact-fst.h:1539
static WeightedStringCompactor * Read(std::istream &strm)
Definition: compact-fst.h:1455
constexpr uint8_t kArcILabelValue
Definition: fst.h:444
ssize_t NumArcs(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
Definition: expanded-fst.h:103
CompactFstImpl(const CompactFstImpl &impl)
Definition: compact-fst.h:908
Arc Expand(StateId s, const Element &p, uint8_t flags=kArcValueFlags) const
Definition: compact-fst.h:1560
bool Error() const
Definition: compact-fst.h:271
std::shared_ptr< ArcCompactor > SharedArcCompactor()
Definition: compact-fst.h:671
std::unique_ptr< T > WrapUnique(T *ptr)
Definition: compat.h:125
static CompactFst * Read(std::istream &strm, const FstReadOptions &opts)
Definition: compact-fst.h:1151
MatcherBase< Arc > * InitMatcher(MatchType match_type) const override
Definition: compact-fst.h:1179
size_t NumStates() const
Definition: compact-fst.h:263
typename Arc::Weight Weight
Definition: compact-fst.h:845
CompactFstImpl(const CompactFstImpl< OtherArc, OtherCompactor, OtherCacheStore > &impl)
Definition: compact-fst.h:1048
constexpr int kNoStateId
Definition: fst.h:202
ArcCompactor * MutableArcCompactor()
Definition: compact-fst.h:668
typename Arc::Weight Weight
Definition: compact-fst.h:1509
typename ArcCompactor::Arc Arc
Definition: compact-fst.h:702
void SetState(StateId s, State *state) const
Definition: compact-fst.h:617
static MappedFile * Allocate(size_t size, size_t align=kArchAlignment)
Definition: mapped-file.cc:190
std::pair< Label, StateId > Element
Definition: compact-fst.h:1469
CompactArcCompactor(std::shared_ptr< ArcCompactor > arc_compactor, std::shared_ptr< CompactStore > compact_store)
Definition: compact-fst.h:551
uint32_t GetFlags() const
Definition: fst.h:148
typename AC::Arc Arc
Definition: compact-fst.h:524
static const std::string & Type()
Definition: compact-fst.h:1406
std::string source
Definition: fst.h:102
size_t NumOutputEpsilons(StateId s)
Definition: compact-fst.h:961
#define FSTERROR()
Definition: util.h:53
constexpr uint64_t Properties() const
Definition: compact-fst.h:1567
static void WriteFstHeader(const Fst< Arc > &fst, std::ostream &strm, const FstWriteOptions &opts, int version, std::string_view type, uint64_t properties, FstHeader *hdr)
Definition: fst.h:812
static UnweightedAcceptorCompactor * Read(std::istream &istrm)
Definition: compact-fst.h:1497
Unsigned States(ssize_t i) const
Definition: compact-fst.h:257
size_t NumArcs() const
Definition: compact-fst.h:615
CompactFst(const Fst< Arc > &fst, std::shared_ptr< Compactor > compactor, const CompactFstOptions &opts=CompactFstOptions())
Definition: compact-fst.h:1120
ssize_t NumInputEpsilons(const ExpandedFst< Arc > &fst, typename Arc::StateId s)
Definition: expanded-fst.h:108
std::pair< Label, Weight > Element
Definition: compact-fst.h:1427
virtual uint64_t Properties() const
Definition: fst.h:702
typename Arc::Label Label
Definition: compact-fst.h:1423
bool Compatible(const Fst< Arc > &fst) const
Definition: compact-fst.h:1443
size_t NumCompacts() const
Definition: compact-fst.h:265
typename Arc::Weight Weight
Definition: compact-fst.h:1386
constexpr uint64_t kOLabelSorted
Definition: properties.h:98
constexpr uint64_t kCopyProperties
Definition: properties.h:162
CompactArcCompactor(const Iterator b, const Iterator e, std::shared_ptr< ArcCompactor > arc_compactor)
Definition: compact-fst.h:579
CompactArcCompactor(const CompactArcCompactor< OtherC, U, S > &compactor)
Definition: compact-fst.h:602
Arc Expand(StateId s, const Element &p, uint8_t flags=kArcValueFlags) const
Definition: compact-fst.h:1518
uint64_t CheckProperties(const Fst< Arc > &fst, uint64_t check_mask, uint64_t test_mask)
bool Compatible(const Fst< Arc > &fst) const
Definition: compact-fst.h:1527
StateId nstates
Definition: fst.h:384
constexpr ssize_t Size() const
Definition: compact-fst.h:1439
Arc Expand(StateId s, const Element &p, uint8_t flags=kArcValueFlags) const
Definition: compact-fst.h:1475
constexpr uint8_t kArcOLabelValue
Definition: fst.h:446
virtual StateId Start() const =0
typename Arc::StateId StateId
Definition: compact-fst.h:846
bool Done() const
Definition: fst.h:533
constexpr ssize_t Size() const
Definition: compact-fst.h:1523
static StringCompactor * Read(std::istream &strm)
Definition: compact-fst.h:1413
std::unique_ptr< StateIteratorBase< Arc > > base
Definition: fst.h:382
ArcIterator(const CompactFst< Arc, Compactor, CacheStore > &fst, StateId s)
Definition: compact-fst.h:1342
StateId NumStates() const
Definition: compact-fst.h:614
ssize_t Start() const
Definition: compact-fst.h:269
typename Arc::Weight Weight
Definition: compact-fst.h:1425
typename Arc::StateId StateId
Definition: compact-fst.h:1102
typename Arc::StateId StateId
Definition: compact-fst.h:525
bool WriteCompactArcFst(const FST &fst, const typename CompactArcFST::Compactor::ArcCompactor &arc_compactor, std::ostream &strm, const FstWriteOptions &opts)
Definition: compact-fst.h:1202
typename Arc::Label Label
Definition: compact-fst.h:1507
size_t NumInputEpsilons(StateId s)
Definition: compact-fst.h:955
bool Write(std::ostream &strm, const FstWriteOptions &opts) const
Definition: compact-fst.h:1002
constexpr uint64_t kNullProperties
Definition: properties.h:149
Element Compact(StateId s, const Arc &arc) const
Definition: compact-fst.h:1429
typename Arc::Weight Weight
Definition: compact-fst.h:1467
const std::string & Type() const
Definition: fst.h:698
CompactArcCompactor(const Fst< Arc > &fst, std::shared_ptr< CompactArcCompactor > compactor)
Definition: compact-fst.h:543
CompactFstImpl(const CompactFstImpl< Arc, Compactor, OtherCacheStore > &impl)
Definition: compact-fst.h:921
bool HasFixedOutdegree() const
Definition: compact-fst.h:648
std::pair< std::pair< Label, Weight >, StateId > Element
Definition: compact-fst.h:1511
bool WriteFile(const std::string &source) const
Definition: fst.h:332
constexpr uint8_t kArcWeightValue
Definition: fst.h:448
constexpr uint64_t kILabelSorted
Definition: properties.h:93
int64_t NumArcs() const
Definition: fst.h:156
CompactFst * Copy(bool safe=false) const override
Definition: compact-fst.h:1146
static CompactFstImpl * Read(std::istream &strm, const FstReadOptions &opts)
Definition: compact-fst.h:984
constexpr uint64_t kUnweighted
Definition: properties.h:105
typename Arc::Weight Weight
Definition: compact-fst.h:526
void SetNumStates(int64_t numstates)
Definition: fst.h:170
virtual const SymbolTable * InputSymbols() const =0
const SymbolTable * InputSymbols() const
Definition: fst.h:760
void SetCompactor(std::shared_ptr< Compactor > compactor)
Definition: compact-fst.h:1185
int64_t NumStates() const
Definition: fst.h:154
bool Write(std::ostream &strm, const FstWriteOptions &opts) const override
Definition: compact-fst.h:1163
bool Done() const
Definition: fst.h:415
Element Compact(StateId s, const Arc &arc) const
Definition: compact-fst.h:1471
typename Arc::Weight Weight
Definition: compact-fst.h:704
CompactArcCompactor(const Iterator b, const Iterator e)
Definition: compact-fst.h:585
const ArcCompactor * GetArcCompactor() const
Definition: compact-fst.h:665
void SetStart(int64_t start)
Definition: fst.h:168
static CompactArcStore * Read(std::istream &strm, const FstReadOptions &opts, const FstHeader &hdr, const ArcCompactor &arc_compactor)
CacheStore Store
Definition: compact-fst.h:1105
void SetCompactor(std::shared_ptr< Compactor > compactor)
Definition: compact-fst.h:1036
typename Arc::StateId StateId
Definition: compact-fst.h:1508
std::shared_ptr< Compactor > SharedCompactor()
Definition: compact-fst.h:1035
typename AC::Element Element
Definition: compact-fst.h:523
FileReadMode mode
Definition: fst.h:81
int64_t Start() const
Definition: fst.h:152
constexpr uint64_t kString
Definition: properties.h:135
uint64_t Properties(uint64_t props) const
Definition: compact-fst.h:635
typename Arc::StateId StateId
Definition: compact-fst.h:1385
size_t NumArcs(StateId s)
Definition: compact-fst.h:949
void Expand(const Fst< Arc > &ifst, const std::vector< std::pair< typename Arc::Label, typename Arc::Label >> &parens, const std::vector< typename Arc::Label > &assignments, MutableFst< Arc > *ofst, const MPdtExpandOptions &opts)
Definition: expand.h:316
const Compactor * GetCompactor() const
Definition: compact-fst.h:1183
void InitStateIterator(StateIteratorData< Arc > *data) const
Definition: compact-fst.h:1014
bool Write(std::ostream &strm, const FstWriteOptions &opts) const
Definition: compact-fst.h:480
static const std::string & Type()
Definition: compact-fst.h:505
bool Write(std::ostream &strm) const
Definition: compact-fst.h:1537
typename Arc::StateId StateId
Definition: compact-fst.h:1466
CompactArcState(const Compactor *compactor, StateId s)
Definition: compact-fst.h:709
size_t NumArcs() const
Definition: compact-fst.h:745
Element Compact(StateId s, const Arc &arc) const
Definition: compact-fst.h:1513
constexpr ssize_t Size() const
Definition: compact-fst.h:1565
constexpr uint64_t kExpanded
Definition: properties.h:45
static CompactArcCompactor * Read(std::istream &strm, const FstReadOptions &opts, const FstHeader &hdr)
Definition: compact-fst.h:621
bool Compatible(const Fst< Arc > &fst) const
Definition: compact-fst.h:1569
Arc ComputeArc(StateId s, Unsigned i, uint8_t flags) const
Definition: compact-fst.h:675
void InitStateIterator(StateIteratorData< Arc > *data) const override
Definition: compact-fst.h:1171
void SetFlags(uint32_t flags)
Definition: fst.h:164
constexpr ssize_t Size() const
Definition: compact-fst.h:1480
StateId NumStates() const
Definition: compact-fst.h:944
typename Arc::Label Label
Definition: compact-fst.h:1384
bool Write(std::ostream &strm, const FstWriteOptions &opts) const
Definition: compact-fst.h:631
const CompactStore * GetCompactStore() const
Definition: compact-fst.h:666
bool Write(std::ostream &strm) const
Definition: compact-fst.h:1495
const Compactor * GetCompactor(const Fst< Arc > &fst)
Definition: compact-fst.h:1085
static const std::string & Type()
Definition: compact-fst.h:1489
static const std::string & Type()
Definition: compact-fst.h:650
StateId Start() const
Definition: compact-fst.h:613
size_t CountEpsilons(StateId s, bool output_epsilons)
Definition: compact-fst.h:967
constexpr uint64_t Properties() const
Definition: compact-fst.h:1482
bool Compatible(const Fst< Arc > &fst) const
Definition: compact-fst.h:1401
constexpr uint64_t kAcceptor
Definition: properties.h:63
typename Arc::StateId StateId
Definition: compact-fst.h:1424
static const std::string & Type()
Definition: compact-fst.h:1532
bool Write(const std::string &source) const override
Definition: compact-fst.h:1167
virtual const SymbolTable * OutputSymbols() const =0