// See www.openfst.org for extensive documentation on this weighted
|
// finite-state transducer library.
|
//
|
// FST Class for memory-efficient representation of common types of
|
// FSTs: linear automata, acceptors, unweighted FSTs, ...
|
|
#ifndef FST_COMPACT_FST_H_
|
#define FST_COMPACT_FST_H_
|
|
#include <climits>
|
#include <iterator>
|
#include <memory>
|
#include <tuple>
|
#include <utility>
|
#include <vector>
|
|
#include <fst/log.h>
|
|
#include <fst/cache.h>
|
#include <fst/expanded-fst.h>
|
#include <fst/fst-decl.h> // For optional argument declarations
|
#include <fst/mapped-file.h>
|
#include <fst/matcher.h>
|
#include <fst/test-properties.h>
|
#include <fst/util.h>
|
|
|
namespace fst {
|
|
struct CompactFstOptions : public CacheOptions {
|
// The default caching behaviour is to do no caching. Most compactors are
|
// cheap and therefore we save memory by not doing caching.
|
CompactFstOptions() : CacheOptions(true, 0) {}
|
|
explicit CompactFstOptions(const CacheOptions &opts) : CacheOptions(opts) {}
|
};
|
|
// New upcoming (Fst) Compactor interface - currently used internally
|
// by CompactFstImpl.
|
//
|
// class Compactor {
|
// public:
|
// // Constructor from the Fst to be compacted.
|
// Compactor(const Fst<Arc> &fst, ...);
|
// // Copy constructor
|
// Compactor(const Compactor &compactor, bool safe = false)
|
// // Default constructor (optional, see comment below).
|
// Compactor();
|
//
|
// // Returns the start state, number of states, and total number of arcs
|
// // of the compacted Fst
|
// StateId Start() const;
|
// StateId NumStates() const;
|
// size_t NumArcs() const;
|
//
|
// // Accessor class for state attributes.
|
// class State {
|
// public:
|
// State(); // Required, corresponds to kNoStateId.
|
// State(const Compactor *c, StateId); // Accessor for StateId 's'.
|
// StateId GetStateId() const;
|
// Weight Final() const;
|
// size_t NumArcs() const;
|
// Arc GetArc(size_t i, uint32 f) const;
|
// };
|
//
|
// // Modifies 'state' accessor to provide access to state id 's'.
|
// void SetState(StateId s, State *state);
|
// // Tests whether 'fst' can be compacted by this compactor.
|
// bool IsCompatible(const Fst<A> &fst) const;
|
// // Return the properties that are always true for an fst
|
// // compacted using this compactor
|
// uint64 Properties() const;
|
// // Return a string identifying the type of compactor.
|
// static const string &Type();
|
// // Return true if an error has occured.
|
// bool Error() const;
|
// // Writes a compactor to a file.
|
// bool Write(std::ostream &strm, const FstWriteOptions &opts) const;
|
// // Reads a compactor from a file.
|
// static Compactor*Read(std::istream &strm, const FstReadOptions &opts,
|
// const FstHeader &hdr);
|
// };
|
//
|
|
// Old (Arc) Compactor Interface:
|
//
|
// The ArcCompactor class determines how arcs and final weights are compacted
|
// and expanded.
|
//
|
// Final weights are treated as transitions to the superfinal state, i.e.,
|
// ilabel = olabel = kNoLabel and nextstate = kNoStateId.
|
//
|
// There are two types of compactors:
|
//
|
// * Fixed out-degree compactors: 'compactor.Size()' returns a positive integer
|
// 's'. An FST can be compacted by this compactor only if each state has
|
// exactly 's' outgoing transitions (counting a non-Zero() final weight as a
|
// transition). A typical example is a compactor for string FSTs, i.e.,
|
// 's == 1'.
|
//
|
// * Variable out-degree compactors: 'compactor.Size() == -1'. There are no
|
// out-degree restrictions for these compactors.
|
//
|
// Interface:
|
//
|
// class ArcCompactor {
|
// public:
|
// // Element is the type of the compacted transitions.
|
// using Element = ...
|
//
|
// // Returns the compacted representation of a transition 'arc'
|
// // at a state 's'.
|
// Element Compact(StateId s, const Arc &arc);
|
//
|
// // Returns the transition at state 's' represented by the compacted
|
// // transition 'e'.
|
// Arc Expand(StateId s, const Element &e) const;
|
//
|
// // Returns -1 for variable out-degree compactors, and the mandatory
|
// // out-degree otherwise.
|
// ssize_t Size() const;
|
//
|
// // Tests whether an FST can be compacted by this compactor.
|
// bool Compatible(const Fst<A> &fst) const;
|
//
|
// // Returns the properties that are always true for an FST compacted using
|
// // this compactor
|
// uint64 Properties() const;
|
//
|
// // Returns a string identifying the type of compactor.
|
// static const string &Type();
|
//
|
// // Writes a compactor to a file.
|
// bool Write(std::ostream &strm) const;
|
//
|
// // Reads a compactor from a file.
|
// static ArcCompactor *Read(std::istream &strm);
|
//
|
// // Default constructor (optional, see comment below).
|
// ArcCompactor();
|
// };
|
//
|
// The default constructor is only required for FST_REGISTER to work (i.e.,
|
// enabling Convert() and the command-line utilities to work with this new
|
// compactor). However, a default constructor always needs to be specified for
|
// this code to compile, but one can have it simply raise an error when called,
|
// like so:
|
//
|
// Compactor::Compactor() {
|
// FSTERROR() << "Compactor: No default constructor";
|
// }
|
|
// Default implementation data for CompactFst, which can shared between
|
// otherwise independent copies.
|
//
|
// The implementation contains two arrays: 'states_' and 'compacts_'.
|
//
|
// For fixed out-degree compactors, the 'states_' array is unallocated. The
|
// 'compacts_' contains the compacted transitions. Its size is 'ncompacts_'.
|
// The outgoing transitions at a given state are stored consecutively. For a
|
// given state 's', its 'compactor.Size()' outgoing transitions (including
|
// superfinal transition when 's' is final), are stored in position
|
// ['s*compactor.Size()', '(s+1)*compactor.Size()').
|
//
|
// For variable out-degree compactors, the states_ array has size
|
// 'nstates_ + 1' and contains pointers to positions into 'compacts_'. For a
|
// given state 's', the compacted transitions of 's' are stored in positions
|
// ['states_[s]', 'states_[s + 1]') in 'compacts_'. By convention,
|
// 'states_[nstates_] == ncompacts_'.
|
//
|
// In both cases, the superfinal transitions (when 's' is final, i.e.,
|
// 'Final(s) != Weight::Zero()') are stored first.
|
//
|
// The unsigned type U is used to represent indices into the compacts_ array.
|
template <class Element, class Unsigned>
|
class DefaultCompactStore {
|
public:
|
DefaultCompactStore()
|
: states_(nullptr),
|
compacts_(nullptr),
|
nstates_(0),
|
ncompacts_(0),
|
narcs_(0),
|
start_(kNoStateId),
|
error_(false) {}
|
|
template <class Arc, class Compactor>
|
DefaultCompactStore(const Fst<Arc> &fst, const Compactor &compactor);
|
|
template <class Iterator, class Compactor>
|
DefaultCompactStore(const Iterator &begin, const Iterator &end,
|
const Compactor &compactor);
|
|
~DefaultCompactStore() {
|
if (!states_region_) delete[] states_;
|
if (!compacts_region_) delete[] compacts_;
|
}
|
|
template <class Compactor>
|
static DefaultCompactStore<Element, Unsigned> *Read(
|
std::istream &strm, const FstReadOptions &opts, const FstHeader &hdr,
|
const Compactor &compactor);
|
|
bool Write(std::ostream &strm, const FstWriteOptions &opts) const;
|
|
Unsigned States(ssize_t i) const { return states_[i]; }
|
|
const Element &Compacts(size_t i) const { return compacts_[i]; }
|
|
size_t NumStates() const { return nstates_; }
|
|
size_t NumCompacts() const { return ncompacts_; }
|
|
size_t NumArcs() const { return narcs_; }
|
|
ssize_t Start() const { return start_; }
|
|
bool Error() const { return error_; }
|
|
// Returns a string identifying the type of data storage container.
|
static const string &Type();
|
|
private:
|
std::unique_ptr<MappedFile> states_region_;
|
std::unique_ptr<MappedFile> compacts_region_;
|
Unsigned *states_;
|
Element *compacts_;
|
size_t nstates_;
|
size_t ncompacts_;
|
size_t narcs_;
|
ssize_t start_;
|
bool error_;
|
};
|
|
template <class Element, class Unsigned>
|
template <class Arc, class Compactor>
|
DefaultCompactStore<Element, Unsigned>::DefaultCompactStore(
|
const Fst<Arc> &fst, const Compactor &compactor)
|
: states_(nullptr),
|
compacts_(nullptr),
|
nstates_(0),
|
ncompacts_(0),
|
narcs_(0),
|
start_(kNoStateId),
|
error_(false) {
|
using StateId = typename Arc::StateId;
|
using Weight = typename Arc::Weight;
|
start_ = fst.Start();
|
// Counts # of states and arcs.
|
StateId nfinals = 0;
|
for (StateIterator<Fst<Arc>> siter(fst); !siter.Done(); siter.Next()) {
|
++nstates_;
|
const auto s = siter.Value();
|
narcs_ += fst.NumArcs(s);
|
if (fst.Final(s) != Weight::Zero()) ++nfinals;
|
}
|
if (compactor.Size() == -1) {
|
states_ = new Unsigned[nstates_ + 1];
|
ncompacts_ = narcs_ + nfinals;
|
compacts_ = new Element[ncompacts_];
|
states_[nstates_] = ncompacts_;
|
} else {
|
states_ = nullptr;
|
ncompacts_ = nstates_ * compactor.Size();
|
if ((narcs_ + nfinals) != ncompacts_) {
|
FSTERROR() << "DefaultCompactStore: Compactor incompatible with FST";
|
error_ = true;
|
return;
|
}
|
compacts_ = new Element[ncompacts_];
|
}
|
size_t pos = 0;
|
size_t fpos = 0;
|
for (size_t s = 0; s < nstates_; ++s) {
|
fpos = pos;
|
if (compactor.Size() == -1) states_[s] = pos;
|
if (fst.Final(s) != Weight::Zero()) {
|
compacts_[pos++] = compactor.Compact(
|
s, Arc(kNoLabel, kNoLabel, fst.Final(s), kNoStateId));
|
}
|
for (ArcIterator<Fst<Arc>> aiter(fst, s); !aiter.Done(); aiter.Next()) {
|
compacts_[pos++] = compactor.Compact(s, aiter.Value());
|
}
|
if ((compactor.Size() != -1) && (pos != fpos + compactor.Size())) {
|
FSTERROR() << "DefaultCompactStore: Compactor incompatible with FST";
|
error_ = true;
|
return;
|
}
|
}
|
if (pos != ncompacts_) {
|
FSTERROR() << "DefaultCompactStore: Compactor incompatible with FST";
|
error_ = true;
|
return;
|
}
|
}
|
|
template <class Element, class Unsigned>
|
template <class Iterator, class Compactor>
|
DefaultCompactStore<Element, Unsigned>::DefaultCompactStore(
|
const Iterator &begin, const Iterator &end, const Compactor &compactor)
|
: states_(nullptr),
|
compacts_(nullptr),
|
nstates_(0),
|
ncompacts_(0),
|
narcs_(0),
|
start_(kNoStateId),
|
error_(false) {
|
using Arc = typename Compactor::Arc;
|
using Weight = typename Arc::Weight;
|
if (compactor.Size() != -1) {
|
ncompacts_ = std::distance(begin, end);
|
if (compactor.Size() == 1) {
|
// For strings, allows implicit final weight. Empty input is the empty
|
// string.
|
if (ncompacts_ == 0) {
|
++ncompacts_;
|
} else {
|
const auto arc =
|
compactor.Expand(ncompacts_ - 1, *(begin + (ncompacts_ - 1)));
|
if (arc.ilabel != kNoLabel) ++ncompacts_;
|
}
|
}
|
if (ncompacts_ % compactor.Size()) {
|
FSTERROR() << "DefaultCompactStore: Size of input container incompatible"
|
<< " with compactor";
|
error_ = true;
|
return;
|
}
|
if (ncompacts_ == 0) return;
|
start_ = 0;
|
nstates_ = ncompacts_ / compactor.Size();
|
compacts_ = new Element[ncompacts_];
|
size_t i = 0;
|
Iterator it = begin;
|
for (; it != end; ++it, ++i) {
|
compacts_[i] = *it;
|
if (compactor.Expand(i, *it).ilabel != kNoLabel) ++narcs_;
|
}
|
if (i < ncompacts_) {
|
compacts_[i] = compactor.Compact(
|
i, Arc(kNoLabel, kNoLabel, Weight::One(), kNoStateId));
|
}
|
} else {
|
if (std::distance(begin, end) == 0) return;
|
// Count # of states, arcs and compacts.
|
auto it = begin;
|
for (size_t i = 0; it != end; ++it, ++i) {
|
const auto arc = compactor.Expand(i, *it);
|
if (arc.ilabel != kNoLabel) {
|
++narcs_;
|
++ncompacts_;
|
} else {
|
++nstates_;
|
if (arc.weight != Weight::Zero()) ++ncompacts_;
|
}
|
}
|
start_ = 0;
|
compacts_ = new Element[ncompacts_];
|
states_ = new Unsigned[nstates_ + 1];
|
states_[nstates_] = ncompacts_;
|
size_t i = 0;
|
size_t s = 0;
|
for (it = begin; it != end; ++it) {
|
const auto arc = compactor.Expand(i, *it);
|
if (arc.ilabel != kNoLabel) {
|
compacts_[i++] = *it;
|
} else {
|
states_[s++] = i;
|
if (arc.weight != Weight::Zero()) compacts_[i++] = *it;
|
}
|
}
|
if ((s != nstates_) || (i != ncompacts_)) {
|
FSTERROR() << "DefaultCompactStore: Ill-formed input container";
|
error_ = true;
|
return;
|
}
|
}
|
}
|
|
template <class Element, class Unsigned>
|
template <class Compactor>
|
DefaultCompactStore<Element, Unsigned>
|
*DefaultCompactStore<Element, Unsigned>::Read(std::istream &strm,
|
const FstReadOptions &opts,
|
const FstHeader &hdr,
|
const Compactor &compactor) {
|
std::unique_ptr<DefaultCompactStore<Element, Unsigned>> data(
|
new DefaultCompactStore<Element, Unsigned>());
|
data->start_ = hdr.Start();
|
data->nstates_ = hdr.NumStates();
|
data->narcs_ = hdr.NumArcs();
|
if (compactor.Size() == -1) {
|
if ((hdr.GetFlags() & FstHeader::IS_ALIGNED) && !AlignInput(strm)) {
|
LOG(ERROR) << "DefaultCompactStore::Read: Alignment failed: "
|
<< opts.source;
|
return nullptr;
|
}
|
auto b = (data->nstates_ + 1) * sizeof(Unsigned);
|
data->states_region_.reset(MappedFile::Map(
|
&strm, opts.mode == FstReadOptions::MAP, opts.source, b));
|
if (!strm || !data->states_region_) {
|
LOG(ERROR) << "DefaultCompactStore::Read: Read failed: " << opts.source;
|
return nullptr;
|
}
|
data->states_ =
|
static_cast<Unsigned *>(data->states_region_->mutable_data());
|
} else {
|
data->states_ = nullptr;
|
}
|
data->ncompacts_ = compactor.Size() == -1 ? data->states_[data->nstates_]
|
: data->nstates_ * compactor.Size();
|
if ((hdr.GetFlags() & FstHeader::IS_ALIGNED) && !AlignInput(strm)) {
|
LOG(ERROR) << "DefaultCompactStore::Read: Alignment failed: "
|
<< opts.source;
|
return nullptr;
|
}
|
size_t b = data->ncompacts_ * sizeof(Element);
|
data->compacts_region_.reset(
|
MappedFile::Map(&strm, opts.mode == FstReadOptions::MAP, opts.source, b));
|
if (!strm || !data->compacts_region_) {
|
LOG(ERROR) << "DefaultCompactStore::Read: Read failed: " << opts.source;
|
return nullptr;
|
}
|
data->compacts_ =
|
static_cast<Element *>(data->compacts_region_->mutable_data());
|
return data.release();
|
}
|
|
template <class Element, class Unsigned>
|
bool DefaultCompactStore<Element, Unsigned>::Write(
|
std::ostream &strm, const FstWriteOptions &opts) const {
|
if (states_) {
|
if (opts.align && !AlignOutput(strm)) {
|
LOG(ERROR) << "DefaultCompactStore::Write: Alignment failed: "
|
<< opts.source;
|
return false;
|
}
|
strm.write(reinterpret_cast<char *>(states_),
|
(nstates_ + 1) * sizeof(Unsigned));
|
}
|
if (opts.align && !AlignOutput(strm)) {
|
LOG(ERROR) << "DefaultCompactStore::Write: Alignment failed: "
|
<< opts.source;
|
return false;
|
}
|
strm.write(reinterpret_cast<char *>(compacts_), ncompacts_ * sizeof(Element));
|
strm.flush();
|
if (!strm) {
|
LOG(ERROR) << "DefaultCompactStore::Write: Write failed: " << opts.source;
|
return false;
|
}
|
return true;
|
}
|
|
template <class Element, class Unsigned>
|
const string &DefaultCompactStore<Element, Unsigned>::Type() {
|
static const string *const type = new string("compact");
|
return *type;
|
}
|
|
template <class C, class U, class S> class DefaultCompactState;
|
|
// Wraps an arc compactor and a compact store as a new Fst compactor.
|
template <class C, class U,
|
class S = DefaultCompactStore<typename C::Element, U>>
|
class DefaultCompactor {
|
public:
|
using ArcCompactor = C;
|
using Unsigned = U;
|
using CompactStore = S;
|
using Element = typename C::Element;
|
using Arc = typename C::Arc;
|
using StateId = typename Arc::StateId;
|
using Weight = typename Arc::Weight;
|
using State = DefaultCompactState<C, U, S>;
|
friend State;
|
|
DefaultCompactor()
|
: arc_compactor_(nullptr), compact_store_(nullptr) {}
|
|
// Constructs from Fst.
|
DefaultCompactor(const Fst<Arc> &fst,
|
std::shared_ptr<ArcCompactor> arc_compactor)
|
: arc_compactor_(std::move(arc_compactor)),
|
compact_store_(std::make_shared<S>(fst, *arc_compactor_)) {}
|
|
DefaultCompactor(const Fst<Arc> &fst,
|
std::shared_ptr<DefaultCompactor<C, U, S>> compactor)
|
: arc_compactor_(compactor->arc_compactor_),
|
compact_store_(compactor->compact_store_ == nullptr ?
|
std::make_shared<S>(fst, *arc_compactor_) :
|
compactor->compact_store_) {}
|
|
// Constructs from CompactStore.
|
DefaultCompactor(std::shared_ptr<ArcCompactor> arc_compactor,
|
std::shared_ptr<CompactStore> compact_store)
|
: arc_compactor_(std::move(arc_compactor)),
|
compact_store_(std::move(compact_store)) {}
|
|
// Constructs from set of compact elements (when arc_compactor.Size() != -1).
|
template <class Iterator>
|
DefaultCompactor(const Iterator &b, const Iterator &e,
|
std::shared_ptr<C> arc_compactor)
|
: arc_compactor_(std::move(arc_compactor)),
|
compact_store_(std::make_shared<S>(b, e, *arc_compactor_)) {}
|
|
// Copy constructor.
|
DefaultCompactor(const DefaultCompactor<C, U, S> &compactor)
|
: arc_compactor_(std::make_shared<C>(*compactor.GetArcCompactor())),
|
compact_store_(compactor.SharedCompactStore()) {}
|
|
template <class OtherC>
|
explicit DefaultCompactor(const DefaultCompactor<OtherC, U, S> &compactor)
|
: arc_compactor_(std::make_shared<C>(*compactor.GetArcCompactor())),
|
compact_store_(compactor.SharedCompactStore()) {}
|
|
StateId Start() const { return compact_store_->Start(); }
|
StateId NumStates() const { return compact_store_->NumStates(); }
|
size_t NumArcs() const { return compact_store_->NumArcs(); }
|
|
void SetState(StateId s, State *state) const {
|
if (state->GetStateId() != s) state->Set(this, s);
|
}
|
|
static DefaultCompactor<C, U, S> *Read(std::istream &strm,
|
const FstReadOptions &opts,
|
const FstHeader &hdr) {
|
std::shared_ptr<C> arc_compactor(C::Read(strm));
|
if (arc_compactor == nullptr) return nullptr;
|
std::shared_ptr<S> compact_store(S::Read(strm, opts, hdr, *arc_compactor));
|
if (compact_store == nullptr) return nullptr;
|
return new DefaultCompactor<C, U, S>(arc_compactor, compact_store);
|
}
|
|
bool Write(std::ostream &strm, const FstWriteOptions &opts) const {
|
return arc_compactor_->Write(strm) && compact_store_->Write(strm, opts);
|
}
|
|
uint64 Properties() const { return arc_compactor_->Properties(); }
|
|
bool IsCompatible(const Fst<Arc> &fst) const {
|
return arc_compactor_->Compatible(fst);
|
}
|
|
bool Error() const { return compact_store_->Error(); }
|
|
bool HasFixedOutdegree() const { return arc_compactor_->Size() != -1; }
|
|
static const string &Type() {
|
static const string *const type = [] {
|
string type = "compact";
|
if (sizeof(U) != sizeof(uint32)) type += std::to_string(8 * sizeof(U));
|
type += "_";
|
type += C::Type();
|
if (CompactStore::Type() != "compact") {
|
type += "_";
|
type += CompactStore::Type();
|
}
|
return new string(type);
|
}();
|
return *type;
|
}
|
|
const ArcCompactor *GetArcCompactor() const { return arc_compactor_.get(); }
|
CompactStore *GetCompactStore() const { return compact_store_.get(); }
|
|
std::shared_ptr<ArcCompactor> SharedArcCompactor() const {
|
return arc_compactor_;
|
}
|
|
std::shared_ptr<CompactStore> SharedCompactStore() const {
|
return compact_store_;
|
}
|
|
// TODO(allauzen): remove dependencies on this method and make private.
|
Arc ComputeArc(StateId s, Unsigned i, uint32 f) const {
|
return arc_compactor_->Expand(s, compact_store_->Compacts(i), f);
|
}
|
|
private:
|
std::pair<Unsigned, Unsigned> CompactsRange(StateId s) const {
|
std::pair<size_t, size_t> range;
|
if (HasFixedOutdegree()) {
|
range.first = s * arc_compactor_->Size();
|
range.second = arc_compactor_->Size();
|
} else {
|
range.first = compact_store_->States(s);
|
range.second = compact_store_->States(s + 1) - range.first;
|
}
|
return range;
|
}
|
|
private:
|
std::shared_ptr<ArcCompactor> arc_compactor_;
|
std::shared_ptr<CompactStore> compact_store_;
|
};
|
|
// Default implementation of state attributes accessor class for
|
// DefaultCompactor. Use of efficient specialization strongly encouraged.
|
template <class C, class U, class S>
|
class DefaultCompactState {
|
public:
|
using Arc = typename C::Arc;
|
using StateId = typename Arc::StateId;
|
using Weight = typename Arc::Weight;
|
|
DefaultCompactState() = default;
|
|
DefaultCompactState(const DefaultCompactor<C, U, S> *compactor, StateId s)
|
: compactor_(compactor),
|
s_(s),
|
range_(compactor->CompactsRange(s)),
|
has_final_(
|
range_.second != 0 &&
|
compactor->ComputeArc(s, range_.first,
|
kArcILabelValue).ilabel == kNoLabel) {
|
if (has_final_) {
|
++range_.first;
|
--range_.second;
|
}
|
}
|
|
void Set(const DefaultCompactor<C, U, S> *compactor, StateId s) {
|
compactor_ = compactor;
|
s_ = s;
|
range_ = compactor->CompactsRange(s);
|
if (range_.second != 0 &&
|
compactor->ComputeArc(s, range_.first, kArcILabelValue).ilabel
|
== kNoLabel) {
|
has_final_ = true;
|
++range_.first;
|
--range_.second;
|
} else {
|
has_final_ = false;
|
}
|
}
|
|
StateId GetStateId() const { return s_; }
|
|
Weight Final() const {
|
if (!has_final_) return Weight::Zero();
|
return compactor_->ComputeArc(s_, range_.first - 1, kArcWeightValue).weight;
|
}
|
|
size_t NumArcs() const { return range_.second; }
|
|
Arc GetArc(size_t i, uint32 f) const {
|
return compactor_->ComputeArc(s_, range_.first + i, f);
|
}
|
|
private:
|
const DefaultCompactor<C, U, S> *compactor_ = nullptr; // borrowed ref.
|
StateId s_ = kNoStateId;
|
std::pair<U, U> range_ = {0, 0};
|
bool has_final_ = false;
|
};
|
|
// Specialization for DefaultCompactStore.
|
template <class C, class U>
|
class DefaultCompactState<C, U, DefaultCompactStore<typename C::Element, U>> {
|
public:
|
using Arc = typename C::Arc;
|
using StateId = typename Arc::StateId;
|
using Weight = typename Arc::Weight;
|
using CompactStore = DefaultCompactStore<typename C::Element, U>;
|
|
DefaultCompactState() = default;
|
|
DefaultCompactState(
|
const DefaultCompactor<C, U, CompactStore> *compactor, StateId s)
|
: arc_compactor_(compactor->GetArcCompactor()), s_(s) {
|
Init(compactor);
|
}
|
|
void Set(const DefaultCompactor<C, U, CompactStore> *compactor, StateId s) {
|
arc_compactor_ = compactor->GetArcCompactor();
|
s_ = s;
|
has_final_ = false;
|
Init(compactor);
|
}
|
|
StateId GetStateId() const { return s_; }
|
|
Weight Final() const {
|
if (!has_final_) return Weight::Zero();
|
return arc_compactor_->Expand(s_, *(compacts_ - 1), kArcWeightValue).weight;
|
}
|
|
size_t NumArcs() const { return num_arcs_; }
|
|
Arc GetArc(size_t i, uint32 f) const {
|
return arc_compactor_->Expand(s_, compacts_[i], f);
|
}
|
|
private:
|
void Init(const DefaultCompactor<C, U, CompactStore> *compactor) {
|
const auto *store = compactor->GetCompactStore();
|
U offset;
|
if (!compactor->HasFixedOutdegree()) { // Variable out-degree compactor.
|
offset = store->States(s_);
|
num_arcs_ = store->States(s_ + 1) - offset;
|
} else { // Fixed out-degree compactor.
|
offset = s_ * arc_compactor_->Size();
|
num_arcs_ = arc_compactor_->Size();
|
}
|
if (num_arcs_ > 0) {
|
compacts_ = &(store->Compacts(offset));
|
if (arc_compactor_->Expand(s_, *compacts_, kArcILabelValue).ilabel
|
== kNoStateId) {
|
++compacts_;
|
--num_arcs_;
|
has_final_ = true;
|
}
|
}
|
}
|
|
private:
|
const C *arc_compactor_ = nullptr; // Borrowed reference.
|
const typename C::Element *compacts_ = nullptr; // Borrowed reference.
|
StateId s_ = kNoStateId;
|
U num_arcs_ = 0;
|
bool has_final_ = false;
|
};
|
|
template <class Arc, class ArcCompactor, class Unsigned, class CompactStore,
|
class CacheStore>
|
class CompactFst;
|
|
template <class F, class G>
|
void Cast(const F &, G *);
|
|
namespace internal {
|
|
// Implementation class for CompactFst, which contains parametrizeable
|
// Fst data storage (DefaultCompactStore by default) and Fst cache.
|
template <class Arc, class C, class CacheStore = DefaultCacheStore<Arc>>
|
class CompactFstImpl
|
: public CacheBaseImpl<typename CacheStore::State, CacheStore> {
|
public:
|
using Weight = typename Arc::Weight;
|
using StateId = typename Arc::StateId;
|
using Compactor = C;
|
|
using FstImpl<Arc>::SetType;
|
using FstImpl<Arc>::SetProperties;
|
using FstImpl<Arc>::Properties;
|
using FstImpl<Arc>::SetInputSymbols;
|
using FstImpl<Arc>::SetOutputSymbols;
|
using FstImpl<Arc>::WriteHeader;
|
|
using ImplBase = CacheBaseImpl<typename CacheStore::State, CacheStore>;
|
using ImplBase::PushArc;
|
using ImplBase::HasArcs;
|
using ImplBase::HasFinal;
|
using ImplBase::HasStart;
|
using ImplBase::SetArcs;
|
using ImplBase::SetFinal;
|
using ImplBase::SetStart;
|
|
CompactFstImpl()
|
: ImplBase(CompactFstOptions()),
|
compactor_() {
|
SetType(Compactor::Type());
|
SetProperties(kNullProperties | kStaticProperties);
|
}
|
|
CompactFstImpl(const Fst<Arc> &fst, std::shared_ptr<Compactor> compactor,
|
const CompactFstOptions &opts)
|
: ImplBase(opts),
|
compactor_(std::make_shared<Compactor>(fst, compactor)) {
|
SetType(Compactor::Type());
|
SetInputSymbols(fst.InputSymbols());
|
SetOutputSymbols(fst.OutputSymbols());
|
if (compactor_->Error()) SetProperties(kError, kError);
|
uint64 copy_properties = fst.Properties(kMutable, false) ?
|
fst.Properties(kCopyProperties, true):
|
CheckProperties(fst,
|
kCopyProperties & ~kWeightedCycles & ~kUnweightedCycles,
|
kCopyProperties);
|
if ((copy_properties & kError) || !compactor_->IsCompatible(fst)) {
|
FSTERROR() << "CompactFstImpl: Input Fst incompatible with compactor";
|
SetProperties(kError, kError);
|
return;
|
}
|
SetProperties(copy_properties | kStaticProperties);
|
}
|
|
CompactFstImpl(std::shared_ptr<Compactor> compactor,
|
const CompactFstOptions &opts)
|
: ImplBase(opts),
|
compactor_(compactor) {
|
SetType(Compactor::Type());
|
SetProperties(kStaticProperties | compactor_->Properties());
|
if (compactor_->Error()) SetProperties(kError, kError);
|
}
|
|
CompactFstImpl(const CompactFstImpl<Arc, Compactor, CacheStore> &impl)
|
: ImplBase(impl),
|
compactor_(impl.compactor_ == nullptr ?
|
std::make_shared<Compactor>() :
|
std::make_shared<Compactor>(*impl.compactor_)) {
|
SetType(impl.Type());
|
SetProperties(impl.Properties());
|
SetInputSymbols(impl.InputSymbols());
|
SetOutputSymbols(impl.OutputSymbols());
|
}
|
|
// Allows to change the cache store from OtherI to I.
|
template <class OtherCacheStore>
|
CompactFstImpl(const CompactFstImpl<Arc, Compactor, OtherCacheStore> &impl)
|
: ImplBase(CacheOptions(impl.GetCacheGc(), impl.GetCacheLimit())),
|
compactor_(impl.compactor_ == nullptr ?
|
std::make_shared<Compactor>() :
|
std::make_shared<Compactor>(*impl.compactor_)) {
|
SetType(impl.Type());
|
SetProperties(impl.Properties());
|
SetInputSymbols(impl.InputSymbols());
|
SetOutputSymbols(impl.OutputSymbols());
|
}
|
|
StateId Start() {
|
if (!HasStart()) SetStart(compactor_->Start());
|
return ImplBase::Start();
|
}
|
|
Weight Final(StateId s) {
|
if (HasFinal(s)) return ImplBase::Final(s);
|
compactor_->SetState(s, &state_);
|
return state_.Final();
|
}
|
|
StateId NumStates() const {
|
if (Properties(kError)) return 0;
|
return compactor_->NumStates();
|
}
|
|
size_t NumArcs(StateId s) {
|
if (HasArcs(s)) return ImplBase::NumArcs(s);
|
compactor_->SetState(s, &state_);
|
return state_.NumArcs();
|
}
|
|
size_t NumInputEpsilons(StateId s) {
|
if (!HasArcs(s) && !Properties(kILabelSorted)) Expand(s);
|
if (HasArcs(s)) return ImplBase::NumInputEpsilons(s);
|
return CountEpsilons(s, false);
|
}
|
|
size_t NumOutputEpsilons(StateId s) {
|
if (!HasArcs(s) && !Properties(kOLabelSorted)) Expand(s);
|
if (HasArcs(s)) return ImplBase::NumOutputEpsilons(s);
|
return CountEpsilons(s, true);
|
}
|
|
size_t CountEpsilons(StateId s, bool output_epsilons) {
|
compactor_->SetState(s, &state_);
|
const uint32 f = output_epsilons ? kArcOLabelValue : kArcILabelValue;
|
size_t num_eps = 0;
|
for (size_t i = 0; i < state_.NumArcs(); ++i) {
|
const auto& arc = state_.GetArc(i, f);
|
const auto label = output_epsilons ? arc.olabel : arc.ilabel;
|
if (label == 0)
|
++num_eps;
|
else if (label > 0)
|
break;
|
}
|
return num_eps;
|
}
|
|
static CompactFstImpl<Arc, Compactor, CacheStore> *Read(
|
std::istream &strm, const FstReadOptions &opts) {
|
std::unique_ptr<CompactFstImpl<Arc, Compactor, CacheStore>> impl(
|
new CompactFstImpl<Arc, Compactor, CacheStore>());
|
FstHeader hdr;
|
if (!impl->ReadHeader(strm, opts, kMinFileVersion, &hdr)) {
|
return nullptr;
|
}
|
// Ensures compatibility.
|
if (hdr.Version() == kAlignedFileVersion) {
|
hdr.SetFlags(hdr.GetFlags() | FstHeader::IS_ALIGNED);
|
}
|
impl->compactor_ = std::shared_ptr<Compactor>(
|
Compactor::Read(strm, opts, hdr));
|
if (!impl->compactor_) {
|
return nullptr;
|
}
|
return impl.release();
|
}
|
|
bool Write(std::ostream &strm, const FstWriteOptions &opts) const {
|
FstHeader hdr;
|
hdr.SetStart(compactor_->Start());
|
hdr.SetNumStates(compactor_->NumStates());
|
hdr.SetNumArcs(compactor_->NumArcs());
|
// Ensures compatibility.
|
const auto file_version = opts.align ? kAlignedFileVersion : kFileVersion;
|
WriteHeader(strm, opts, file_version, &hdr);
|
return compactor_->Write(strm, opts);
|
}
|
|
// Provides information needed for generic state iterator.
|
void InitStateIterator(StateIteratorData<Arc> *data) const {
|
data->base = nullptr;
|
data->nstates = compactor_->NumStates();
|
}
|
|
void InitArcIterator(StateId s, ArcIteratorData<Arc> *data) {
|
if (!HasArcs(s)) Expand(s);
|
ImplBase::InitArcIterator(s, data);
|
}
|
|
void Expand(StateId s) {
|
compactor_->SetState(s, &state_);
|
for (size_t i = 0; i < state_.NumArcs(); ++i)
|
PushArc(s, state_.GetArc(i, kArcValueFlags));
|
SetArcs(s);
|
if (!HasFinal(s)) SetFinal(s, state_.Final());
|
}
|
|
const Compactor *GetCompactor() const { return compactor_.get(); }
|
std::shared_ptr<Compactor> SharedCompactor() const { return compactor_; }
|
void SetCompactor(std::shared_ptr<Compactor> compactor) {
|
// TODO(allauzen): is this correct? is this needed?
|
// TODO(allauzen): consider removing and forcing this through direct calls
|
// to compactor.
|
compactor_ = compactor;
|
}
|
|
// Properties always true of this FST class.
|
static constexpr uint64 kStaticProperties = kExpanded;
|
|
protected:
|
template <class OtherArc, class OtherCompactor, class OtherCacheStore>
|
explicit CompactFstImpl(
|
const CompactFstImpl<OtherArc, OtherCompactor, OtherCacheStore> &impl)
|
: compactor_(std::make_shared<Compactor>(*impl.GetCompactor())) {
|
SetType(impl.Type());
|
SetProperties(impl.Properties());
|
SetInputSymbols(impl.InputSymbols());
|
SetOutputSymbols(impl.OutputSymbols());
|
}
|
|
private:
|
// Allows access during write.
|
template <class AnyArc, class ArcCompactor, class Unsigned,
|
class CompactStore, class AnyCacheStore>
|
friend class ::fst::CompactFst; // allow access during write.
|
|
// Current unaligned file format version.
|
static constexpr int kFileVersion = 2;
|
// Current aligned file format version.
|
static constexpr int kAlignedFileVersion = 1;
|
// Minimum file format version supported.
|
static constexpr int kMinFileVersion = 1;
|
|
std::shared_ptr<Compactor> compactor_;
|
typename Compactor::State state_;
|
};
|
|
template <class Arc, class Compactor, class CacheStore>
|
constexpr uint64 CompactFstImpl<Arc, Compactor, CacheStore>::kStaticProperties;
|
|
template <class Arc, class Compactor, class CacheStore>
|
constexpr int CompactFstImpl<Arc, Compactor, CacheStore>::kFileVersion;
|
|
template <class Arc, class Compactor, class CacheStore>
|
constexpr int CompactFstImpl<Arc, Compactor, CacheStore>::kAlignedFileVersion;
|
|
template <class Arc, class Compactor, class CacheStore>
|
constexpr int CompactFstImpl<Arc, Compactor, CacheStore>::kMinFileVersion;
|
|
} // namespace internal
|
|
// This class attaches interface to implementation and handles reference
|
// counting, delegating most methods to ImplToExpandedFst. The Unsigned type
|
// is used to represent indices into the compact arc array. (Template
|
// argument defaults are declared in fst-decl.h.)
|
template <class A, class ArcCompactor, class Unsigned, class CompactStore,
|
class CacheStore>
|
class CompactFst
|
: public ImplToExpandedFst<internal::CompactFstImpl<
|
A,
|
DefaultCompactor<ArcCompactor, Unsigned, CompactStore>,
|
CacheStore>> {
|
public:
|
template <class F, class G>
|
void friend Cast(const F &, G *);
|
|
using Arc = A;
|
using StateId = typename A::StateId;
|
using Compactor = DefaultCompactor<ArcCompactor, Unsigned, CompactStore>;
|
using Impl = internal::CompactFstImpl<A, Compactor, CacheStore>;
|
using Store = CacheStore; // for CacheArcIterator
|
|
friend class StateIterator<
|
CompactFst<A, ArcCompactor, Unsigned, CompactStore, CacheStore>>;
|
friend class ArcIterator<
|
CompactFst<A, ArcCompactor, Unsigned, CompactStore, CacheStore>>;
|
|
CompactFst() : ImplToExpandedFst<Impl>(std::make_shared<Impl>()) {}
|
|
// If data is not nullptr, it is assumed to be already initialized.
|
explicit CompactFst(
|
const Fst<A> &fst,
|
const ArcCompactor &compactor = ArcCompactor(),
|
const CompactFstOptions &opts = CompactFstOptions(),
|
std::shared_ptr<CompactStore> data = std::shared_ptr<CompactStore>())
|
: ImplToExpandedFst<Impl>(
|
std::make_shared<Impl>(
|
fst,
|
std::make_shared<Compactor>(
|
std::make_shared<ArcCompactor>(compactor), data),
|
opts)) {}
|
|
// If data is not nullptr, it is assumed to be already initialized.
|
CompactFst(
|
const Fst<Arc> &fst,
|
std::shared_ptr<ArcCompactor> compactor,
|
const CompactFstOptions &opts = CompactFstOptions(),
|
std::shared_ptr<CompactStore> data = std::shared_ptr<CompactStore>())
|
: ImplToExpandedFst<Impl>(
|
std::make_shared<Impl>(fst,
|
std::make_shared<Compactor>(compactor, data),
|
opts)) {}
|
|
// The following 2 constructors take as input two iterators delimiting a set
|
// of (already) compacted transitions, starting with the transitions out of
|
// the initial state. The format of the input differs for fixed out-degree
|
// and variable out-degree compactors.
|
//
|
// - For fixed out-degree compactors, the final weight (encoded as a
|
// compacted transition) needs to be given only for final states. All strings
|
// (compactor of size 1) will be assume to be terminated by a final state
|
// even when the final state is not implicitely given.
|
//
|
// - For variable out-degree compactors, the final weight (encoded as a
|
// compacted transition) needs to be given for all states and must appeared
|
// first in the list (for state s, final weight of s, followed by outgoing
|
// transitons in s).
|
//
|
// These 2 constructors allows the direct construction of a CompactFst
|
// without first creating a more memory-hungry regular FST. This is useful
|
// when memory usage is severely constrained.
|
template <class Iterator>
|
explicit CompactFst(const Iterator &begin, const Iterator &end,
|
const ArcCompactor &compactor = ArcCompactor(),
|
const CompactFstOptions &opts = CompactFstOptions())
|
: ImplToExpandedFst<Impl>(
|
std::make_shared<Impl>(
|
std::make_shared<Compactor>(
|
begin, end, std::make_shared<ArcCompactor>(compactor)),
|
opts)) {}
|
|
template <class Iterator>
|
CompactFst(const Iterator &begin, const Iterator &end,
|
std::shared_ptr<ArcCompactor> compactor,
|
const CompactFstOptions &opts = CompactFstOptions())
|
: ImplToExpandedFst<Impl>(
|
std::make_shared<Impl>(
|
std::make_shared<Compactor>(begin, end, compactor), opts)) {}
|
|
// See Fst<>::Copy() for doc.
|
CompactFst(
|
const CompactFst<A, ArcCompactor, Unsigned, CompactStore, CacheStore>
|
&fst,
|
bool safe = false)
|
: ImplToExpandedFst<Impl>(fst, safe) {}
|
|
// Get a copy of this CompactFst. See Fst<>::Copy() for further doc.
|
CompactFst<A, ArcCompactor, Unsigned, CompactStore, CacheStore> *Copy(
|
bool safe = false) const override {
|
return new CompactFst<A, ArcCompactor, Unsigned, CompactStore, CacheStore>(
|
*this, safe);
|
}
|
|
// Read a CompactFst from an input stream; return nullptr on error
|
static CompactFst<A, ArcCompactor, Unsigned, CompactStore, CacheStore> *Read(
|
std::istream &strm, const FstReadOptions &opts) {
|
auto *impl = Impl::Read(strm, opts);
|
return impl ? new CompactFst<A, ArcCompactor, Unsigned, CompactStore,
|
CacheStore>(std::shared_ptr<Impl>(impl))
|
: nullptr;
|
}
|
|
// Read a CompactFst from a file; return nullptr on error
|
// Empty filename reads from standard input
|
static CompactFst<A, ArcCompactor, Unsigned, CompactStore, CacheStore> *Read(
|
const string &filename) {
|
auto *impl = ImplToExpandedFst<Impl>::Read(filename);
|
return impl ? new CompactFst<A, ArcCompactor, Unsigned, CompactStore,
|
CacheStore>(std::shared_ptr<Impl>(impl))
|
: nullptr;
|
}
|
|
bool Write(std::ostream &strm, const FstWriteOptions &opts) const override {
|
return GetImpl()->Write(strm, opts);
|
}
|
|
bool Write(const string &filename) const override {
|
return Fst<Arc>::WriteFile(filename);
|
}
|
|
template <class FST>
|
static bool WriteFst(const FST &fst, const ArcCompactor &compactor,
|
std::ostream &strm, const FstWriteOptions &opts);
|
|
void InitStateIterator(StateIteratorData<Arc> *data) const override {
|
GetImpl()->InitStateIterator(data);
|
}
|
|
void InitArcIterator(StateId s, ArcIteratorData<Arc> *data) const override {
|
GetMutableImpl()->InitArcIterator(s, data);
|
}
|
|
MatcherBase<Arc> *InitMatcher(MatchType match_type) const override {
|
return new SortedMatcher<
|
CompactFst<A, ArcCompactor, Unsigned, CompactStore, CacheStore>>(
|
*this, match_type);
|
}
|
|
template <class Iterator>
|
void SetCompactElements(const Iterator &b, const Iterator &e) {
|
GetMutableImpl()->SetCompactor(std::make_shared<Compactor>(
|
b, e, std::make_shared<ArcCompactor>()));
|
}
|
|
private:
|
using ImplToFst<Impl, ExpandedFst<Arc>>::GetImpl;
|
using ImplToFst<Impl, ExpandedFst<Arc>>::GetMutableImpl;
|
|
explicit CompactFst(std::shared_ptr<Impl> impl)
|
: ImplToExpandedFst<Impl>(impl) {}
|
|
// Use overloading to extract the type of the argument.
|
static Impl *GetImplIfCompactFst(
|
const CompactFst<A, ArcCompactor, Unsigned, CompactStore, CacheStore>
|
&compact_fst) {
|
return compact_fst.GetImpl();
|
}
|
|
// This does not give privileged treatment to subclasses of CompactFst.
|
template <typename NonCompactFst>
|
static Impl *GetImplIfCompactFst(const NonCompactFst &fst) {
|
return nullptr;
|
}
|
|
CompactFst &operator=(const CompactFst &fst) = delete;
|
};
|
|
// Writes FST in Compact format, with a possible pass over the machine before
|
// writing to compute the number of states and arcs.
|
template <class A, class ArcCompactor, class Unsigned, class CompactStore,
|
class CacheStore>
|
template <class FST>
|
bool CompactFst<A, ArcCompactor, Unsigned, CompactStore, CacheStore>::WriteFst(
|
const FST &fst, const ArcCompactor &compactor, std::ostream &strm,
|
const FstWriteOptions &opts) {
|
using Arc = A;
|
using Weight = typename A::Weight;
|
using Element = typename ArcCompactor::Element;
|
const auto file_version =
|
opts.align ? Impl::kAlignedFileVersion : Impl::kFileVersion;
|
size_t num_arcs = -1;
|
size_t num_states = -1;
|
auto first_pass_compactor = compactor;
|
if (auto *impl = GetImplIfCompactFst(fst)) {
|
num_arcs = impl->GetCompactor()->GetCompactStore()->NumArcs();
|
num_states = impl->GetCompactor()->GetCompactStore()->NumStates();
|
first_pass_compactor = *impl->GetCompactor()->GetArcCompactor();
|
} else {
|
// A first pass is needed to compute the state of the compactor, which
|
// is saved ahead of the rest of the data structures. This unfortunately
|
// means forcing a complete double compaction when writing in this format.
|
// TODO(allauzen): eliminate mutable state from compactors.
|
num_arcs = 0;
|
num_states = 0;
|
for (StateIterator<FST> siter(fst); !siter.Done(); siter.Next()) {
|
const auto s = siter.Value();
|
++num_states;
|
if (fst.Final(s) != Weight::Zero()) {
|
first_pass_compactor.Compact(
|
s, Arc(kNoLabel, kNoLabel, fst.Final(s), kNoStateId));
|
}
|
for (ArcIterator<FST> aiter(fst, s); !aiter.Done(); aiter.Next()) {
|
++num_arcs;
|
first_pass_compactor.Compact(s, aiter.Value());
|
}
|
}
|
}
|
FstHeader hdr;
|
hdr.SetStart(fst.Start());
|
hdr.SetNumStates(num_states);
|
hdr.SetNumArcs(num_arcs);
|
string type = "compact";
|
if (sizeof(Unsigned) != sizeof(uint32)) {
|
type += std::to_string(CHAR_BIT * sizeof(Unsigned));
|
}
|
type += "_";
|
type += ArcCompactor::Type();
|
if (CompactStore::Type() != "compact") {
|
type += "_";
|
type += CompactStore::Type();
|
}
|
const auto copy_properties = fst.Properties(kCopyProperties, true);
|
if ((copy_properties & kError) || !compactor.Compatible(fst)) {
|
FSTERROR() << "Fst incompatible with compactor";
|
return false;
|
}
|
uint64 properties = copy_properties | Impl::kStaticProperties;
|
internal::FstImpl<Arc>::WriteFstHeader(fst, strm, opts, file_version, type,
|
properties, &hdr);
|
first_pass_compactor.Write(strm);
|
if (first_pass_compactor.Size() == -1) {
|
if (opts.align && !AlignOutput(strm)) {
|
LOG(ERROR) << "CompactFst::Write: Alignment failed: " << opts.source;
|
return false;
|
}
|
Unsigned compacts = 0;
|
for (StateIterator<FST> siter(fst); !siter.Done(); siter.Next()) {
|
const auto s = siter.Value();
|
strm.write(reinterpret_cast<const char *>(&compacts), sizeof(compacts));
|
if (fst.Final(s) != Weight::Zero()) {
|
++compacts;
|
}
|
compacts += fst.NumArcs(s);
|
}
|
strm.write(reinterpret_cast<const char *>(&compacts), sizeof(compacts));
|
}
|
if (opts.align && !AlignOutput(strm)) {
|
LOG(ERROR) << "Could not align file during write after writing states";
|
}
|
const auto &second_pass_compactor = compactor;
|
Element element;
|
for (StateIterator<FST> siter(fst); !siter.Done(); siter.Next()) {
|
const auto s = siter.Value();
|
if (fst.Final(s) != Weight::Zero()) {
|
element = second_pass_compactor.Compact(
|
s, A(kNoLabel, kNoLabel, fst.Final(s), kNoStateId));
|
strm.write(reinterpret_cast<const char *>(&element), sizeof(element));
|
}
|
for (ArcIterator<FST> aiter(fst, s); !aiter.Done(); aiter.Next()) {
|
element = second_pass_compactor.Compact(s, aiter.Value());
|
strm.write(reinterpret_cast<const char *>(&element), sizeof(element));
|
}
|
}
|
strm.flush();
|
if (!strm) {
|
LOG(ERROR) << "CompactFst write failed: " << opts.source;
|
return false;
|
}
|
return true;
|
}
|
|
// Specialization for CompactFst; see generic version in fst.h for sample
|
// usage (but use the CompactFst type!). This version should inline.
|
template <class Arc, class ArcCompactor, class Unsigned, class CompactStore,
|
class CacheStore>
|
class StateIterator<
|
CompactFst<Arc, ArcCompactor, Unsigned, CompactStore, CacheStore>> {
|
public:
|
using StateId = typename Arc::StateId;
|
|
explicit StateIterator(
|
const CompactFst<Arc, ArcCompactor, Unsigned, CompactStore,
|
CacheStore> &fst)
|
: nstates_(fst.GetImpl()->NumStates()), s_(0) {}
|
|
bool Done() const { return s_ >= nstates_; }
|
|
StateId Value() const { return s_; }
|
|
void Next() { ++s_; }
|
|
void Reset() { s_ = 0; }
|
|
private:
|
StateId nstates_;
|
StateId s_;
|
};
|
|
// Specialization for CompactFst. Never caches,
|
// always iterates over the underlying compact elements.
|
template <class Arc, class ArcCompactor, class Unsigned,
|
class CompactStore, class CacheStore>
|
class ArcIterator<CompactFst<
|
Arc, ArcCompactor, Unsigned, CompactStore, CacheStore>> {
|
public:
|
using StateId = typename Arc::StateId;
|
using Element = typename ArcCompactor::Element;
|
using Compactor = DefaultCompactor<ArcCompactor, Unsigned, CompactStore>;
|
using State = typename Compactor::State;
|
|
ArcIterator(const CompactFst<Arc, ArcCompactor, Unsigned, CompactStore,
|
CacheStore> &fst,
|
StateId s)
|
: state_(fst.GetImpl()->GetCompactor(), s),
|
pos_(0),
|
flags_(kArcValueFlags) {}
|
|
bool Done() const { return pos_ >= state_.NumArcs(); }
|
|
const Arc &Value() const {
|
arc_ = state_.GetArc(pos_, flags_);
|
return arc_;
|
}
|
|
void Next() { ++pos_; }
|
|
size_t Position() const { return pos_; }
|
|
void Reset() { pos_ = 0; }
|
|
void Seek(size_t pos) { pos_ = pos; }
|
|
uint32 Flags() const { return flags_; }
|
|
void SetFlags(uint32 f, uint32 m) {
|
flags_ &= ~m;
|
flags_ |= (f & kArcValueFlags);
|
}
|
|
private:
|
State state_;
|
size_t pos_;
|
mutable Arc arc_;
|
uint32 flags_;
|
};
|
|
// ArcCompactor for unweighted string FSTs.
|
template <class A>
|
class StringCompactor {
|
public:
|
using Arc = A;
|
using Label = typename Arc::Label;
|
using StateId = typename Arc::StateId;
|
using Weight = typename Arc::Weight;
|
|
using Element = Label;
|
|
Element Compact(StateId s, const Arc &arc) const { return arc.ilabel; }
|
|
Arc Expand(StateId s, const Element &p, uint32 f = kArcValueFlags) const {
|
return Arc(p, p, Weight::One(), p != kNoLabel ? s + 1 : kNoStateId);
|
}
|
|
constexpr ssize_t Size() const { return 1; }
|
|
constexpr uint64 Properties() const {
|
return kString | kAcceptor | kUnweighted;
|
}
|
|
bool Compatible(const Fst<Arc> &fst) const {
|
const auto props = Properties();
|
return fst.Properties(props, true) == props;
|
}
|
|
static const string &Type() {
|
static const string *const type = new string("string");
|
return *type;
|
}
|
|
bool Write(std::ostream &strm) const { return true; }
|
|
static StringCompactor *Read(std::istream &strm) {
|
return new StringCompactor;
|
}
|
};
|
|
// ArcCompactor for weighted string FSTs.
|
template <class A>
|
class WeightedStringCompactor {
|
public:
|
using Arc = A;
|
using Label = typename Arc::Label;
|
using StateId = typename Arc::StateId;
|
using Weight = typename Arc::Weight;
|
|
using Element = std::pair<Label, Weight>;
|
|
Element Compact(StateId s, const Arc &arc) const {
|
return std::make_pair(arc.ilabel, arc.weight);
|
}
|
|
Arc Expand(StateId s, const Element &p, uint32 f = kArcValueFlags) const {
|
return Arc(p.first, p.first, p.second,
|
p.first != kNoLabel ? s + 1 : kNoStateId);
|
}
|
|
constexpr ssize_t Size() const { return 1; }
|
|
constexpr uint64 Properties() const { return kString | kAcceptor; }
|
|
bool Compatible(const Fst<Arc> &fst) const {
|
const auto props = Properties();
|
return fst.Properties(props, true) == props;
|
}
|
|
static const string &Type() {
|
static const string *const type = new string("weighted_string");
|
return *type;
|
}
|
|
bool Write(std::ostream &strm) const { return true; }
|
|
static WeightedStringCompactor *Read(std::istream &strm) {
|
return new WeightedStringCompactor;
|
}
|
};
|
|
// ArcCompactor for unweighted acceptor FSTs.
|
template <class A>
|
class UnweightedAcceptorCompactor {
|
public:
|
using Arc = A;
|
using Label = typename Arc::Label;
|
using StateId = typename Arc::StateId;
|
using Weight = typename Arc::Weight;
|
|
using Element = std::pair<Label, StateId>;
|
|
Element Compact(StateId s, const Arc &arc) const {
|
return std::make_pair(arc.ilabel, arc.nextstate);
|
}
|
|
Arc Expand(StateId s, const Element &p, uint32 f = kArcValueFlags) const {
|
return Arc(p.first, p.first, Weight::One(), p.second);
|
}
|
|
constexpr ssize_t Size() const { return -1; }
|
|
constexpr uint64 Properties() const { return kAcceptor | kUnweighted; }
|
|
bool Compatible(const Fst<Arc> &fst) const {
|
const auto props = Properties();
|
return fst.Properties(props, true) == props;
|
}
|
|
static const string &Type() {
|
static const string *const type = new string("unweighted_acceptor");
|
return *type;
|
}
|
|
bool Write(std::ostream &strm) const { return true; }
|
|
static UnweightedAcceptorCompactor *Read(std::istream &istrm) {
|
return new UnweightedAcceptorCompactor;
|
}
|
};
|
|
// ArcCompactor for weighted acceptor FSTs.
|
template <class A>
|
class AcceptorCompactor {
|
public:
|
using Arc = A;
|
using Label = typename Arc::Label;
|
using StateId = typename Arc::StateId;
|
using Weight = typename Arc::Weight;
|
|
using Element = std::pair<std::pair<Label, Weight>, StateId>;
|
|
Element Compact(StateId s, const Arc &arc) const {
|
return std::make_pair(std::make_pair(arc.ilabel, arc.weight),
|
arc.nextstate);
|
}
|
|
Arc Expand(StateId s, const Element &p, uint32 f = kArcValueFlags) const {
|
return Arc(p.first.first, p.first.first, p.first.second, p.second);
|
}
|
|
constexpr ssize_t Size() const { return -1; }
|
|
constexpr uint64 Properties() const { return kAcceptor; }
|
|
bool Compatible(const Fst<Arc> &fst) const {
|
const auto props = Properties();
|
return fst.Properties(props, true) == props;
|
}
|
|
static const string &Type() {
|
static const string *const type = new string("acceptor");
|
return *type;
|
}
|
|
bool Write(std::ostream &strm) const { return true; }
|
|
static AcceptorCompactor *Read(std::istream &strm) {
|
return new AcceptorCompactor;
|
}
|
};
|
|
// ArcCompactor for unweighted FSTs.
|
template <class A>
|
class UnweightedCompactor {
|
public:
|
using Arc = A;
|
using Label = typename Arc::Label;
|
using StateId = typename Arc::StateId;
|
using Weight = typename Arc::Weight;
|
|
using Element = std::pair<std::pair<Label, Label>, StateId>;
|
|
Element Compact(StateId s, const Arc &arc) const {
|
return std::make_pair(std::make_pair(arc.ilabel, arc.olabel),
|
arc.nextstate);
|
}
|
|
Arc Expand(StateId s, const Element &p, uint32 f = kArcValueFlags) const {
|
return Arc(p.first.first, p.first.second, Weight::One(), p.second);
|
}
|
|
constexpr ssize_t Size() const { return -1; }
|
|
constexpr uint64 Properties() const { return kUnweighted; }
|
|
bool Compatible(const Fst<Arc> &fst) const {
|
const auto props = Properties();
|
return fst.Properties(props, true) == props;
|
}
|
|
static const string &Type() {
|
static const string *const type = new string("unweighted");
|
return *type;
|
}
|
|
bool Write(std::ostream &strm) const { return true; }
|
|
static UnweightedCompactor *Read(std::istream &strm) {
|
return new UnweightedCompactor;
|
}
|
};
|
|
template <class Arc, class Unsigned /* = uint32 */>
|
using CompactStringFst = CompactFst<Arc, StringCompactor<Arc>, Unsigned>;
|
|
template <class Arc, class Unsigned /* = uint32 */>
|
using CompactWeightedStringFst =
|
CompactFst<Arc, WeightedStringCompactor<Arc>, Unsigned>;
|
|
template <class Arc, class Unsigned /* = uint32 */>
|
using CompactAcceptorFst = CompactFst<Arc, AcceptorCompactor<Arc>, Unsigned>;
|
|
template <class Arc, class Unsigned /* = uint32 */>
|
using CompactUnweightedFst =
|
CompactFst<Arc, UnweightedCompactor<Arc>, Unsigned>;
|
|
template <class Arc, class Unsigned /* = uint32 */>
|
using CompactUnweightedAcceptorFst =
|
CompactFst<Arc, UnweightedAcceptorCompactor<Arc>, Unsigned>;
|
|
using StdCompactStringFst = CompactStringFst<StdArc, uint32>;
|
|
using StdCompactWeightedStringFst = CompactWeightedStringFst<StdArc, uint32>;
|
|
using StdCompactAcceptorFst = CompactAcceptorFst<StdArc, uint32>;
|
|
using StdCompactUnweightedFst = CompactUnweightedFst<StdArc, uint32>;
|
|
using StdCompactUnweightedAcceptorFst =
|
CompactUnweightedAcceptorFst<StdArc, uint32>;
|
|
} // namespace fst
|
|
#endif // FST_COMPACT_FST_H_
|
