#include <fst/compact-fst.h>

Collaboration diagram for fst::CompactFstData< A, C, U >:

Public Types
typedef A	Arc
typedef A::Weight	Weight
typedef A::StateId	StateId
typedef C	Compactor
typedef C::Element	CompactElement
typedef U	Unsigned
Public Member Functions
	CompactFstData ()
	CompactFstData (const Fst< A > &fst, const Compactor &compactor)
template<class Iterator >
	CompactFstData (const Iterator &begin, const Iterator &end, const Compactor &compactor)
	~CompactFstData ()
bool	Write (ostream &strm, const FstWriteOptions &opts, const C &compactor) const
Unsigned	States (StateId i) const
const CompactElement &	Compacts (size_t i) const
StateId	NumStates () const
size_t	NumCompacts () const
size_t	NumArcs () const
StateId	Start () const
int	RefCount () const
int	IncrRefCount ()
int	DecrRefCount ()
template<class Iterator >
	CompactFstData (const Iterator &begin, const Iterator &end, const C &compactor)
Static Public Member Functions
static CompactFstData< A, C, U > *	Read (istream &strm, const FstReadOptions &opts, const FstHeader &hdr, const Compactor &compactor)

Detailed Description

template<class A, class C, class U>
class fst::CompactFstData< A, C, U >

Compactor Interface - class determinies 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.

class Compactor { public: Element is the type of the compacted transitions. typedef ... Element; Return the compacted representation of a transition 'arc' at a state 's'. Element Compact(StateId s, const Arc &arc); Return the transition at state 's' represented by the compacted transition 'e'. Arc Expand(StateId s, const Element &e); Return -1 for variable out-degree compactors, and the mandatory out-degree otherwise. ssize_t Size(); Test whether 'fst' can be compacted by this compactor. bool Compatible(const Fst<A> &fst); Return the properties that are always true for an fst compacted using this compactor uint64 Properties(); Return a string identifying the type of compactor. static const string &Type(); Write a compactor to a file. bool Write(ostream &strm); Read a compactor from a file. static Compactor *Read(istream &strm); Default constructor (optional, see comment below). Compactor(); };

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 specify for this code to compile, but one can have it simply raised an error when called:

Compactor::Compactor() { LOG(FATAL) << "Compactor: no default constructor"; } Implementation data for Compact Fst, 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 transitons (when 's' is final, i.e. 'Final(s) != Weight::Zero()') is stored first.

The unsigned type U is used to represent indices into the compacts_ array.

Definition at line 130 of file compact-fst.h.