fst Namespace Reference

For an extended explanation of the framework of which grammar-fsts are a part, please see Support for grammars and graphs with on-the-fly parts. (i.e. More...

Namespaces
	internal
	pre_determinize_helpers

Classes
class	ArcIterator< GrammarFst >
	This is the overridden template for class ArcIterator for GrammarFst. More...
class	ArcIterator< TrivialFactorWeightFst< A, F > >
class	ArcticWeightTpl
class	BackoffDeterministicOnDemandFst
	This class wraps an Fst, representing a language model, using the interface for "BackoffDeterministicOnDemandFst". More...
class	CacheDeterministicOnDemandFst
class	CompactLatticeMinimizer
class	CompactLatticePusher
class	CompactLatticeWeightCommonDivisorTpl
class	CompactLatticeWeightTpl
class	ComposeDeterministicOnDemandFst
class	DeterministicOnDemandFst
	class DeterministicOnDemandFst is an "FST-like" base-class. More...
struct	DeterminizeLatticeOptions
struct	DeterminizeLatticePhonePrunedOptions
struct	DeterminizeLatticePrunedOptions
class	DeterminizerStar
class	DfsOrderVisitor
class	GrammarFst
	GrammarFst is an FST that is 'stitched together' from multiple FSTs, that can recursively incorporate each other. More...
struct	GrammarFstArc
class	GrammarFstPreparer
struct	IdentityFunction
class	InverseContextFst
class	InverseLeftBiphoneContextFst
class	LatticeDeterminizer
class	LatticeDeterminizerPruned
class	LatticeStringRepository
class	LatticeToStdMapper
	Class LatticeToStdMapper maps a LatticeArc to a normal arc (StdArc) by adding the elements of the LatticeArc weight. More...
class	LatticeWeightTpl
class	LmExampleDeterministicOnDemandFst
	This class is for didactic purposes, it does not really do anything. More...
class	MapInputSymbolsMapper
class	NaturalLess< CompactLatticeWeightTpl< LatticeWeightTpl< double >, int32 > >
class	NaturalLess< CompactLatticeWeightTpl< LatticeWeightTpl< float >, int32 > >
class	NaturalLess< CompactLatticeWeightTpl< LatticeWeightTpl< FloatType >, IntType > >
class	NaturalLess< LatticeWeightTpl< double > >
class	NaturalLess< LatticeWeightTpl< float > >
class	NaturalLess< LatticeWeightTpl< FloatType > >
class	PruneSpecialClass
	This class is used to implement the function PruneSpecial. More...
class	PushSpecialClass
struct	RandFstOptions
class	RemoveEpsLocalClass
class	RemoveSomeInputSymbolsMapper
struct	ReweightPlusDefault
struct	ReweightPlusLogArc
class	ScaleDeterministicOnDemandFst
	Class ScaleDeterministicOnDemandFst takes another DeterministicOnDemandFst and scales the weights (like applying a language-model scale). More...
class	StateIterator< TrivialFactorWeightFst< A, F > >
class	StdToLatticeMapper
	Class StdToLatticeMapper maps a normal arc (StdArc) to a LatticeArc by putting the StdArc weight as the first element of the LatticeWeight. More...
class	StringRepository
struct	TableComposeCache
	TableComposeCache lets us do multiple compositions while caching the same matcher. More...
struct	TableComposeOptions
class	TableMatcher
class	TableMatcherImpl
struct	TableMatcherOptions
	TableMatcher is a matcher specialized for the case where the output side of the left FST always has either all-epsilons coming out of a state, or a majority of the symbol table. More...
struct	TestFunctor
class	TrivialFactorWeightFst
	TrivialFactorWeightFst takes as template parameter a FactorIterator as defined above. More...
struct	TrivialFactorWeightOptions
class	UnweightedNgramFst
	The class UnweightedNgramFst is a DeterministicOnDemandFst whose states encode an n-gram history. More...
class	VectorFstTplHolder

Typedefs
typedef fst::StdArc	StdArc
typedef fst::StdArc::Label	Label
typedef fst::StdArc::StateId	StateId
typedef fst::StdVectorFst	StdVectorFst
typedef fst::StdArc::Weight	Weight
typedef unsigned char	StatePropertiesType
typedef VectorFstTplHolder< StdArc >	VectorFstHolder
typedef float	BaseFloat
typedef LatticeWeightTpl< BaseFloat >	LatticeWeight
typedef CompactLatticeWeightTpl< LatticeWeight, int32 >	CompactLatticeWeight
typedef CompactLatticeWeightCommonDivisorTpl< LatticeWeight, int32 >	CompactLatticeWeightCommonDivisor
typedef ArcticWeightTpl< float >	ArcticWeight

Enumerations
enum	{ kStateHasEpsilonArcsEntering = 0x1, kStateHasNonEpsilonArcsEntering = 0x2, kStateHasEpsilonArcsLeaving = 0x4, kStateHasNonEpsilonArcsLeaving = 0x8 }
enum	StatePropertiesEnum {   kStateFinal = 0x1, kStateInitial = 0x2, kStateArcsIn = 0x4, kStateMultipleArcsIn = 0x8,   kStateArcsOut = 0x10, kStateMultipleArcsOut = 0x20, kStateOlabelsOut = 0x40, kStateIlabelsOut = 0x80 }
enum	NonterminalValues {   kNontermBos = 0, kNontermBegin = 1, kNontermEnd = 2, kNontermReenter = 3,   kNontermUserDefined = 4, kNontermMediumNumber = 1000, kNontermBigNumber = 10000000 }
	An anonymous enum to define some values for symbols used in our grammar-fst framework. More...

Functions
template<class Arc >
static VectorFst< Arc > *	GenAcceptorFromSequence (const vector< typename Arc::Label > &symbols, float cost)
template<class Arc >
static float	CheckPhones (const VectorFst< Arc > &linear_fst, const vector< typename Arc::Label > &phone_ids, const vector< typename Arc::Label > &disambig_ids, const vector< typename Arc::Label > &phone_seq, const vector< vector< typename Arc::Label > > &ilabel_info, int N, int P)
template<class Arc >
static VectorFst< Arc > *	GenRandPhoneSeq (vector< typename Arc::Label > &phone_syms, vector< typename Arc::Label > &disambig_syms, typename Arc::Label subsequential_symbol, int num_subseq_syms, float seq_prob, vector< typename Arc::Label > *phoneseq_out)
static void	TestContextFst (bool verbose, bool use_matcher)
void	ComposeContext (const vector< int32 > &disambig_syms_in, int32 context_width, int32 central_position, VectorFst< StdArc > *ifst, VectorFst< StdArc > *ofst, vector< vector< int32 > > *ilabels_out, bool project_ifst)
	Used in the command-line tool fstcomposecontext. More...
void	AddSubsequentialLoop (StdArc::Label subseq_symbol, MutableFst< StdArc > *fst)
	Modifies an FST so that it transuces the same paths, but the input side of the paths can all have the subsequential symbol '$' appended to them any number of times (we could easily specify the number of times, but accepting any number of repetitions is just more convenient). More...
void	WriteILabelInfo (std::ostream &os, bool binary, const vector< vector< int32 > > &info)
	Utility function for writing ilabel-info vectors to disk. More...
void	ReadILabelInfo (std::istream &is, bool binary, vector< vector< int32 > > *info)
	Utility function for reading ilabel-info vectors from disk. More...
SymbolTable *	CreateILabelInfoSymbolTable (const vector< vector< int32 > > &info, const SymbolTable &phones_symtab, std::string separator, std::string initial_disambig)
	The following function is mainly of use for printing and debugging. More...
void	WriteILabelInfo (std::ostream &os, bool binary, const std::vector< std::vector< int32 > > &ilabel_info)
	Utility function for writing ilabel-info vectors to disk. More...
void	ReadILabelInfo (std::istream &is, bool binary, std::vector< std::vector< int32 > > *ilabel_info)
	Utility function for reading ilabel-info vectors from disk. More...
SymbolTable *	CreateILabelInfoSymbolTable (const std::vector< std::vector< int32 > > &ilabel_info, const SymbolTable &phones_symtab, std::string separator, std::string disambig_prefix)
	The following function is mainly of use for printing and debugging. More...
void	ComposeContext (const std::vector< int32 > &disambig_syms, int32 context_width, int32 central_position, VectorFst< StdArc > *ifst, VectorFst< StdArc > *ofst, std::vector< std::vector< int32 > > *ilabels_out, bool project_ifst=false)
	Used in the command-line tool fstcomposecontext. More...
template<class Arc >
void	ComposeDeterministicOnDemand (const Fst< Arc > &fst1, DeterministicOnDemandFst< Arc > *fst2, MutableFst< Arc > *fst_composed)
template<class Arc >
void	ComposeDeterministicOnDemandInverse (const Fst< Arc > &fst1, DeterministicOnDemandFst< Arc > *fst2, MutableFst< Arc > *fst_composed)
	This function does '*fst_composed = Compose(Inverse(*fst2), fst1)' Note that the arguments are reversed; this is unfortunate but it's because the fst2 argument needs to be non-const and non-const arguments must follow const ones. More...
bool	FileExists (std::string strFilename)
StdVectorFst *	CreateBackoffFst ()
StdVectorFst *	CreateResultFst ()
void	DeleteTestFst (StdVectorFst *fst)
Weight	WalkSinglePath (StdVectorFst *ifst, DeterministicOnDemandFst< StdArc > *dfst)
void	TestBackoffAndCache ()
void	TestCompose ()
template<class Weight , class IntType >
bool	DeterminizeLattice (const Fst< ArcTpl< Weight > > &ifst, MutableFst< ArcTpl< Weight > > *ofst, DeterminizeLatticeOptions opts=DeterminizeLatticeOptions(), bool *debug_ptr=NULL)
	This function implements the normal version of DeterminizeLattice, in which the output strings are represented using sequences of arcs, where all but the first one has an epsilon on the input side. More...
template<class Weight , class IntType >
bool	DeterminizeLattice (const Fst< ArcTpl< Weight > > &ifst, MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, IntType > > > *ofst, DeterminizeLatticeOptions opts, bool *debug_ptr)
void	TestLatticeStringRepository ()
template<class Arc >
void	TestDeterminizeLattice ()
template<class Arc >
void	TestDeterminizeLattice2 ()
template<class F >
bool	DeterminizeStar (F &ifst, MutableFst< typename F::Arc > *ofst, float delta=kDelta, bool *debug_ptr=NULL, int max_states=-1, bool allow_partial=false)
	This function implements the normal version of DeterminizeStar, in which the output strings are represented using sequences of arcs, where all but the first one has an epsilon on the input side. More...
template<class F >
bool	DeterminizeStar (F &ifst, MutableFst< GallicArc< typename F::Arc > > *ofst, float delta, bool *debug_ptr, int max_states, bool allow_partial)
template<class Arc >
void	TestDeterminizeGeneral ()
template<class Arc >
void	TestDeterminize ()
template<class Arc >
void	TestDeterminize2 ()
template<class Arc >
void	TestPush ()
template<class Arc >
void	TestMinimize ()
template<class Arc , class inttype >
void	TestStringRepository ()
template<class Arc >
void	ComputeStateInfo (const VectorFst< Arc > &fst, std::vector< char > *epsilon_info)
	This function will set epsilon_info to have size equal to the NumStates() of the FST, containing a logical-or of the enum values kStateHasEpsilonArcsEntering, kStateHasNonEpsilonArcsEntering, kStateHasEpsilonArcsLeaving, and kStateHasNonEpsilonArcsLeaving. More...
template<class Arc >
void	EnsureEpsilonProperty (VectorFst< Arc > *fst)
	This function modifies the fst (while maintaining equivalence) in such a way that, after the modification, all states of the FST which have epsilon-arcs entering them, have no non-epsilon arcs entering them, and all states which have epsilon-arcs leaving them, have no non-epsilon arcs leaving them. More...
void	TestEnsureEpsilonProperty ()
template<class Arc >
void	GetStateProperties (const Fst< Arc > &fst, typename Arc::StateId max_state, std::vector< StatePropertiesType > *props)
	This function works out various properties of the states in the FST, using the bit properties defined in StatePropertiesEnum. More...
template<class Arc , class I >
void	Factor (const Fst< Arc > &fst, MutableFst< Arc > *ofst, std::vector< std::vector< I > > *symbols)
	Factor identifies linear chains of states with an olabel (if any) only on the first arc of the chain, and possibly a sequence of ilabels; it outputs an FST with different symbols on the input that represent sequences of the original input symbols; it outputs the mapping from the new symbol to sequences of original symbols, as "symbols" [zero is reserved for epsilon]. More...
template<class Arc >
void	Factor (const Fst< Arc > &fst, MutableFst< Arc > *ofst1, MutableFst< Arc > *ofst2)
	This is a more conventional interface of Factor that outputs the result as two FSTs. More...
template<class Arc , class I >
void	ExpandInputSequences (const std::vector< std::vector< I > > &sequences, MutableFst< Arc > *fst)
	ExpandInputSequences expands out the input symbols into sequences of input symbols. More...
template<class Arc , class I >
void	CreateFactorFst (const std::vector< std::vector< I > > &sequences, MutableFst< Arc > *fst)
	The function CreateFactorFst will create an FST that expands out the "factors" that are the indices of the "sequences" array, into linear sequences of symbols. More...
template<class Arc , class I >
void	CreateMapFst (const std::vector< I > &symbol_map, MutableFst< Arc > *fst)
	CreateMapFst will create an FST representing this symbol_map. More...
template<class Arc >
static void	TestFactor ()
template<class Arc >
Arc::Label	HighestNumberedOutputSymbol (const Fst< Arc > &fst)
	Returns the highest numbered output symbol id of the FST (or zero for an empty FST. More...
template<class Arc >
Arc::Label	HighestNumberedInputSymbol (const Fst< Arc > &fst)
	Returns the highest numbered input symbol id of the FST (or zero for an empty FST. More...
template<class Arc >
Arc::StateId	NumArcs (const ExpandedFst< Arc > &fst)
	Returns the total number of arcs in an FST. More...
template<class Arc , class I >
void	GetOutputSymbols (const Fst< Arc > &fst, bool include_eps, std::vector< I > *symbols)
	GetOutputSymbols gets the list of symbols on the output of fst (including epsilon, if include_eps == true) More...
template<class Arc , class I >
void	GetInputSymbols (const Fst< Arc > &fst, bool include_eps, std::vector< I > *symbols)
	GetInputSymbols gets the list of symbols on the input of fst (including epsilon, if include_eps == true), as a sorted, unique list. More...
template<class Arc , class I >
void	RemoveSomeInputSymbols (const std::vector< I > &to_remove, MutableFst< Arc > *fst)
	RemoveSomeInputSymbols removes any symbol that appears in "to_remove", from the input side of the FST, replacing them with epsilon. More...
template<class Arc , class I >
void	MapInputSymbols (const std::vector< I > &symbol_mapping, MutableFst< Arc > *fst)
template<class Arc , class I >
bool	GetLinearSymbolSequence (const Fst< Arc > &fst, std::vector< I > *isymbols_out, std::vector< I > *osymbols_out, typename Arc::Weight *tot_weight_out)
	GetLinearSymbolSequence gets the symbol sequence from a linear FST. More...
template<class Arc >
void	ConvertNbestToVector (const Fst< Arc > &fst, std::vector< VectorFst< Arc > > *fsts_out)
	This function converts an FST with a special structure, which is output by the OpenFst functions ShortestPath and RandGen, and converts them into a std::vector of separate FSTs. More...
template<class Arc >
void	NbestAsFsts (const Fst< Arc > &fst, size_t n, std::vector< VectorFst< Arc > > *fsts_out)
	Takes the n-shortest-paths (using ShortestPath), but outputs the result as a vector of up to n fsts. More...
template<class Arc , class I >
void	MakeLinearAcceptorWithAlternatives (const std::vector< std::vector< I > > &labels, MutableFst< Arc > *ofst)
	Creates an unweighted acceptor with a linear structure, with alternatives at each position. More...
template<class Arc , class I >
void	MakeLinearAcceptor (const std::vector< I > &labels, MutableFst< Arc > *ofst)
	Creates unweighted linear acceptor from symbol sequence. More...
template<class I >
void	GetSymbols (const SymbolTable &symtab, bool include_eps, std::vector< I > *syms_out)
template<class Arc >
void	SafeDeterminizeWrapper (MutableFst< Arc > *ifst, MutableFst< Arc > *ofst, float delta=kDelta)
	Does PreDeterminize and DeterminizeStar and then removes the disambiguation symbols. More...
template<class Arc >
void	SafeDeterminizeMinimizeWrapper (MutableFst< Arc > *ifst, VectorFst< Arc > *ofst, float delta=kDelta)
	SafeDeterminizeMinimizeWapper is as SafeDeterminizeWrapper except that it also minimizes (encoded minimization, which is safe). More...
void	DeterminizeStarInLog (VectorFst< StdArc > *fst, float delta, bool *debug_ptr, int max_states)
void	DeterminizeInLog (VectorFst< StdArc > *fst)
void	SafeDeterminizeMinimizeWrapperInLog (VectorFst< StdArc > *ifst, VectorFst< StdArc > *ofst, float delta=kDelta)
	SafeDeterminizeMinimizeWapperInLog is as SafeDeterminizeMinimizeWrapper except it first casts tothe log semiring. More...
void	SafeDeterminizeWrapperInLog (VectorFst< StdArc > *ifst, VectorFst< StdArc > *ofst, float delta)
template<class Arc >
void	RemoveWeights (MutableFst< Arc > *ifst)
template<class Arc >
bool	PrecedingInputSymbolsAreSame (bool start_is_epsilon, const Fst< Arc > &fst)
	Returns true if and only if the FST is such that the input symbols on arcs entering any given state all have the same value. More...
template<class Arc , class F >
bool	PrecedingInputSymbolsAreSameClass (bool start_is_epsilon, const Fst< Arc > &fst, const F &f)
	This is as PrecedingInputSymbolsAreSame, but with a functor f that maps labels to classes. More...
template<class Arc >
bool	FollowingInputSymbolsAreSame (bool end_is_epsilon, const Fst< Arc > &fst)
	Returns true if and only if the FST is such that the input symbols on arcs exiting any given state all have the same value. More...
template<class Arc , class F >
bool	FollowingInputSymbolsAreSameClass (bool end_is_epsilon, const Fst< Arc > &fst, const F &f)
template<class Arc >
void	MakePrecedingInputSymbolsSame (bool start_is_epsilon, MutableFst< Arc > *fst)
	MakePrecedingInputSymbolsSame ensures that all arcs entering any given fst state have the same input symbol. More...
template<class Arc , class F >
void	MakePrecedingInputSymbolsSameClass (bool start_is_epsilon, MutableFst< Arc > *fst, const F &f)
	As MakePrecedingInputSymbolsSame, but takes a functor object that maps labels to classes. More...
template<class Arc >
void	MakeFollowingInputSymbolsSame (bool end_is_epsilon, MutableFst< Arc > *fst)
	MakeFollowingInputSymbolsSame ensures that all arcs exiting any given fst state have the same input symbol. More...
template<class Arc , class F >
void	MakeFollowingInputSymbolsSameClass (bool end_is_epsilon, MutableFst< Arc > *fst, const F &f)
	As MakeFollowingInputSymbolsSame, but takes a functor object that maps labels to classes. More...
template<class Arc >
VectorFst< Arc > *	MakeLoopFst (const std::vector< const ExpandedFst< Arc > * > &fsts)
	MakeLoopFst creates an FST that has a state that is both initial and final (weight == Weight::One()), and for each non-NULL pointer fsts[i], it has an arc out whose output-symbol is i and which goes to a sub-graph whose input language is equivalent to fsts[i], where the final-state becomes a transition to the loop-state. More...
template<class Arc >
void	ClearSymbols (bool clear_input, bool clear_output, MutableFst< Arc > *fst)
	ClearSymbols sets all the symbols on the input and/or output side of the FST to zero, as specified. More...
template<class Arc >
void	ApplyProbabilityScale (float scale, MutableFst< Arc > *fst)
	ApplyProbabilityScale is applicable to FSTs in the log or tropical semiring. More...
template<class Arc >
ssize_t	FindSelfLoopWithILabel (const Fst< Arc > &fst, typename Arc::StateId s)
template<class Arc >
bool	EqualAlign (const Fst< Arc > &ifst, typename Arc::StateId length, int rand_seed, MutableFst< Arc > *ofst, int num_retries=10)
	EqualAlign is similar to RandGen, but it generates a sequence with exactly "length" input symbols. More...
template<class Arc >
void	RemoveUselessArcs (MutableFst< Arc > *fst)
template<class Arc >
void	PhiCompose (const Fst< Arc > &fst1, const Fst< Arc > &fst2, typename Arc::Label phi_label, MutableFst< Arc > *ofst)
template<class Arc >
void	PropagateFinalInternal (typename Arc::Label phi_label, typename Arc::StateId s, MutableFst< Arc > *fst)
template<class Arc >
void	PropagateFinal (typename Arc::Label phi_label, MutableFst< Arc > *fst)
template<class Arc >
void	RhoCompose (const Fst< Arc > &fst1, const Fst< Arc > &fst2, typename Arc::Label rho_label, MutableFst< Arc > *ofst)
template<>
bool	IsStochasticFst (const Fst< LogArc > &fst, float delta, LogArc::Weight *min_sum, LogArc::Weight *max_sum)
template<class Arc >
bool	IsStochasticFst (const Fst< Arc > &fst, float delta=kDelta, typename Arc::Weight *min_sum=NULL, typename Arc::Weight *max_sum=NULL)
	This function returns true if, in the semiring of the FST, the sum (within the semiring) of all the arcs out of each state in the FST is one, to within delta. More...
bool	IsStochasticFstInLog (const Fst< StdArc > &fst, float delta, StdArc::Weight *min_sum, StdArc::Weight *max_sum)
template<class Arc , class I >
void	TestMakeLinearAcceptor ()
template<class Arc >
void	TestDeterminizeStarInLog ()
template<class Arc >
void	TestSafeDeterminizeWrapper ()
void	TestPushInLog ()
template<class Arc >
void	TestAcceptorMinimize ()
template<class Arc >
void	TestMakeSymbolsSame ()
template<class Arc >
void	TestMakeSymbolsSameClass ()
template<class Arc >
VectorFst< Arc > *	MakeLoopFstCompare (const vector< const ExpandedFst< Arc > *> &fsts)
template<class Arc >
void	TestMakeLoopFst ()
template<class Arc >
void	TestEqualAlign ()
template<class Arc >
void	Print (const Fst< Arc > &fst, std::string message)
template<class Arc >
void	TestRemoveUselessArcs ()
template<ReweightType rtype>
void	PushInLog (VectorFst< StdArc > *fst, uint32 ptype, float delta=kDelta)
template<class Arc >
void	MinimizeEncoded (VectorFst< Arc > *fst, float delta=kDelta)
void	ComposeContextLeftBiphone (int32 nonterm_phones_offset, const vector< int32 > &disambig_syms_in, const VectorFst< StdArc > &ifst, VectorFst< StdArc > *ofst, std::vector< std::vector< int32 > > *ilabels)
	This is a variant of the function ComposeContext() which is to be used with our "grammar FST" framework (see The ContextFst object, i.e. More...
int32	GetEncodingMultiple (int32 nonterm_phones_offset)
void	ComposeContextLeftBiphone (int32 nonterm_phones_offset, const std::vector< int32 > &disambig_syms, const VectorFst< StdArc > &ifst, VectorFst< StdArc > *ofst, std::vector< std::vector< int32 > > *ilabels)
	This is a variant of the function ComposeContext() which is to be used with our "grammar FST" framework (see The ContextFst object, i.e. More...
template<class Arc >
void	WriteFstKaldi (std::ostream &os, bool binary, const VectorFst< Arc > &t)
template<class W >
bool	StrToWeight (const std::string &s, bool allow_zero, W *w)
template<class Arc >
void	ReadFstKaldi (std::istream &is, bool binary, VectorFst< Arc > *fst)
VectorFst< StdArc > *	ReadFstKaldi (std::string rxfilename)
Fst< StdArc > *	ReadFstKaldiGeneric (std::string rxfilename, bool throw_on_err)
VectorFst< StdArc > *	CastOrConvertToVectorFst (Fst< StdArc > *fst)
void	ReadFstKaldi (std::string rxfilename, fst::StdVectorFst *ofst)
void	WriteFstKaldi (const VectorFst< StdArc > &fst, std::string wxfilename)
fst::VectorFst< fst::StdArc > *	ReadAndPrepareLmFst (std::string rxfilename)
void	ReadFstKaldi (std::string rxfilename, VectorFst< StdArc > *ofst)
template<class Weight , class Int >
void	ConvertLattice (const ExpandedFst< ArcTpl< Weight > > &ifst, MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, Int > > > *ofst, bool invert=true)
	Convert lattice from a normal FST to a CompactLattice FST. More...
template<class Weight , class Int >
void	ConvertLattice (const ExpandedFst< ArcTpl< CompactLatticeWeightTpl< Weight, Int > > > &ifst, MutableFst< ArcTpl< Weight > > *ofst, bool invert=true)
	Convert lattice CompactLattice format to Lattice. More...
template<class WeightIn , class WeightOut >
void	ConvertLattice (const ExpandedFst< ArcTpl< WeightIn > > &ifst, MutableFst< ArcTpl< WeightOut > > *ofst)
	Convert between CompactLattices and Lattices of different floating point types... More...
template<class Weight , class ScaleFloat >
void	ScaleLattice (const std::vector< std::vector< ScaleFloat > > &scale, MutableFst< ArcTpl< Weight > > *fst)
	Scales the pairs of weights in LatticeWeight or CompactLatticeWeight by viewing the pair (a, b) as a 2-vector and pre-multiplying by the 2x2 matrix in "scale". More...
template<class Weight , class Int >
void	RemoveAlignmentsFromCompactLattice (MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, Int > > > *fst)
	Removes state-level alignments (the strings that are part of the weights). More...
template<class Weight , class Int >
bool	CompactLatticeHasAlignment (const ExpandedFst< ArcTpl< CompactLatticeWeightTpl< Weight, Int > > > &fst)
	Returns true if lattice has alignments, i.e. More...
template<class Real >
void	ConvertFstToLattice (const ExpandedFst< ArcTpl< TropicalWeight > > &ifst, MutableFst< ArcTpl< LatticeWeightTpl< Real > > > *ofst)
	Converts TropicalWeight to LatticeWeight (puts all the weight on the first float in the lattice's pair). More...
template<class Weight , class Int >
void	TestConvert (bool invert)
template<class Weight , class Int >
void	TestShortestPath ()
template<class Int >
void	TestConvert2 ()
template<class Weight , class Int >
void	TestConvertPair (bool invert)
template<class Weight , class Int >
void	TestScalePair (bool invert)
template<class Int >
void	ConvertLattice (const ExpandedFst< ArcTpl< LatticeWeightTpl< float > > > &ifst, MutableFst< ArcTpl< CompactLatticeWeightTpl< LatticeWeightTpl< double >, Int > > > *ofst)
template<class Int >
void	ConvertLattice (const ExpandedFst< ArcTpl< LatticeWeightTpl< double > > > &ifst, MutableFst< ArcTpl< CompactLatticeWeightTpl< LatticeWeightTpl< float >, Int > > > *ofst)
template<class Int >
void	ConvertLattice (const ExpandedFst< ArcTpl< CompactLatticeWeightTpl< LatticeWeightTpl< double >, Int > > > &ifst, MutableFst< ArcTpl< LatticeWeightTpl< float > > > *ofst)
	Converts CompactLattice with double to Lattice with float. More...
template<class Int >
void	ConvertLattice (const ExpandedFst< ArcTpl< CompactLatticeWeightTpl< LatticeWeightTpl< float >, Int > > > &ifst, MutableFst< ArcTpl< LatticeWeightTpl< double > > > *ofst)
	Converts CompactLattice with float to Lattice with double. More...
std::vector< std::vector< double > >	DefaultLatticeScale ()
	Returns a default 2x2 matrix scaling factor for LatticeWeight. More...
std::vector< std::vector< double > >	AcousticLatticeScale (double acwt)
std::vector< std::vector< double > >	GraphLatticeScale (double lmwt)
std::vector< std::vector< double > >	LatticeScale (double lmwt, double acwt)
template<class Weight , class Int >
void	PruneCompactLattice (Weight beam, MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, Int > > > *fst)
LatticeWeight	RandomLatticeWeight ()
CompactLatticeWeight	RandomCompactLatticeWeight ()
void	LatticeWeightTest ()
void	CompactLatticeWeightTest ()
template<class FloatType >
std::ostream &	operator<< (std::ostream &strm, const LatticeWeightTpl< FloatType > &w)
template<class FloatType >
std::istream &	operator>> (std::istream &strm, LatticeWeightTpl< FloatType > &w)
template<class FloatType , class ScaleFloatType >
LatticeWeightTpl< FloatType >	ScaleTupleWeight (const LatticeWeightTpl< FloatType > &w, const std::vector< std::vector< ScaleFloatType > > &scale)
template<class FloatType , class ScaleFloatType >
PairWeight< TropicalWeightTpl< FloatType >, TropicalWeightTpl< FloatType > >	ScaleTupleWeight (const PairWeight< TropicalWeightTpl< FloatType >, TropicalWeightTpl< FloatType > > &w, const std::vector< std::vector< ScaleFloatType > > &scale)
template<class FloatType >
bool	operator== (const LatticeWeightTpl< FloatType > &wa, const LatticeWeightTpl< FloatType > &wb)
template<class FloatType >
bool	operator!= (const LatticeWeightTpl< FloatType > &wa, const LatticeWeightTpl< FloatType > &wb)
template<class FloatType >
int	Compare (const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2)
	Compare returns -1 if w1 < w2, +1 if w1 > w2, and 0 if w1 == w2. More...
template<class FloatType >
LatticeWeightTpl< FloatType >	Plus (const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2)
template<class FloatType >
LatticeWeightTpl< FloatType >	Times (const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2)
template<class FloatType >
LatticeWeightTpl< FloatType >	Divide (const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2, DivideType typ=DIVIDE_ANY)
template<class FloatType >
bool	ApproxEqual (const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2, float delta=kDelta)
template<class WeightType , class IntType >
bool	operator== (const CompactLatticeWeightTpl< WeightType, IntType > &w1, const CompactLatticeWeightTpl< WeightType, IntType > &w2)
template<class WeightType , class IntType >
bool	operator!= (const CompactLatticeWeightTpl< WeightType, IntType > &w1, const CompactLatticeWeightTpl< WeightType, IntType > &w2)
template<class WeightType , class IntType >
bool	ApproxEqual (const CompactLatticeWeightTpl< WeightType, IntType > &w1, const CompactLatticeWeightTpl< WeightType, IntType > &w2, float delta=kDelta)
template<class WeightType , class IntType >
int	Compare (const CompactLatticeWeightTpl< WeightType, IntType > &w1, const CompactLatticeWeightTpl< WeightType, IntType > &w2)
int	Compare (const TropicalWeight &w1, const TropicalWeight &w2)
template<class WeightType , class IntType >
CompactLatticeWeightTpl< WeightType, IntType >	Plus (const CompactLatticeWeightTpl< WeightType, IntType > &w1, const CompactLatticeWeightTpl< WeightType, IntType > &w2)
template<class WeightType , class IntType >
CompactLatticeWeightTpl< WeightType, IntType >	Times (const CompactLatticeWeightTpl< WeightType, IntType > &w1, const CompactLatticeWeightTpl< WeightType, IntType > &w2)
template<class WeightType , class IntType >
CompactLatticeWeightTpl< WeightType, IntType >	Divide (const CompactLatticeWeightTpl< WeightType, IntType > &w1, const CompactLatticeWeightTpl< WeightType, IntType > &w2, DivideType div=DIVIDE_ANY)
template<class WeightType , class IntType >
std::ostream &	operator<< (std::ostream &strm, const CompactLatticeWeightTpl< WeightType, IntType > &w)
template<class WeightType , class IntType >
std::istream &	operator>> (std::istream &strm, CompactLatticeWeightTpl< WeightType, IntType > &w)
template<class Weight , class IntType , class ScaleFloatType >
CompactLatticeWeightTpl< Weight, IntType >	ScaleTupleWeight (const CompactLatticeWeightTpl< Weight, IntType > &w, const std::vector< std::vector< ScaleFloatType > > &scale)
	Scales the pair (a, b) of floating-point weights inside a CompactLatticeWeight by premultiplying it (viewed as a vector) by a 2x2 matrix "scale". More...
template<class Float1 , class Float2 >
void	ConvertLatticeWeight (const LatticeWeightTpl< Float1 > &w_in, LatticeWeightTpl< Float2 > *w_out)
	Define some ConvertLatticeWeight functions that are used in various lattice conversions... More...
template<class Float1 , class Float2 , class Int >
void	ConvertLatticeWeight (const CompactLatticeWeightTpl< LatticeWeightTpl< Float1 >, Int > &w_in, CompactLatticeWeightTpl< LatticeWeightTpl< Float2 >, Int > *w_out)
template<class Float1 , class Float2 >
void	ConvertLatticeWeight (const LatticeWeightTpl< Float1 > &w_in, TropicalWeightTpl< Float2 > *w_out)
template<class Float >
double	ConvertToCost (const LatticeWeightTpl< Float > &w)
template<class Float , class Int >
double	ConvertToCost (const CompactLatticeWeightTpl< LatticeWeightTpl< Float >, Int > &w)
template<class Float >
double	ConvertToCost (const TropicalWeightTpl< Float > &w)
template<class Arc , class Int >
void	PreDeterminize (MutableFst< Arc > *fst, typename Arc::Label first_new_sym, std::vector< Int > *symsOut)
template<class Label >
void	CreateNewSymbols (SymbolTable *input_sym_table, int nSym, std::string prefix, std::vector< Label > *symsOut)
template<class Arc >
void	AddSelfLoops (MutableFst< Arc > *fst, std::vector< typename Arc::Label > &isyms, std::vector< typename Arc::Label > &osyms)
	AddSelfLoops is a function you will probably want to use alongside PreDeterminize, to add self-loops to any FSTs that you compose on the left hand side of the one modified by PreDeterminize. More...
template<class Arc >
int64	DeleteISymbols (MutableFst< Arc > *fst, std::vector< typename Arc::Label > isyms)
template<class Arc >
Arc::StateId	CreateSuperFinal (MutableFst< Arc > *fst)
template<class Arc >
void	TestPreDeterminize ()
template<class Arc >
void	TestAddSelfLoops ()
template<class Arc >
void	PruneSpecial (const Fst< Arc > &ifst, VectorFst< Arc > *ofst, typename Arc::Weight beam, size_t max_states=0)
	The function PruneSpecial is like the standard OpenFst function "prune", except it does not expand the entire "ifst"- this is useful for cases where ifst is an on-demand FST such as a ComposeFst and we don't want to visit it all. More...
static void	TestPruneSpecial ()
static void	TestPushSpecial ()
void	PushSpecial (VectorFst< StdArc > *fst, float delta)
template<class Arc >
VectorFst< Arc > *	RandFst (RandFstOptions opts=RandFstOptions())
	Returns a random FST. More...
template<class Arc >
VectorFst< Arc > *	RandPairFst (RandFstOptions opts=RandFstOptions())
	Returns a random FST. More...
template<class Arc >
void	RemoveEpsLocal (MutableFst< Arc > *fst)
	RemoveEpsLocal remove some (but not necessarily all) epsilons in an FST, using an algorithm that is guaranteed to never increase the number of arcs in the FST (and will also never increase the number of states). More...
void	RemoveEpsLocalSpecial (MutableFst< StdArc > *fst)
	As RemoveEpsLocal but takes care to preserve stochasticity when cast to LogArc. More...
template<class Arc >
static void	TestRemoveEpsLocal ()
static void	TestRemoveEpsLocalSpecial ()
template<class Arc >
void	TestTableMatcher (bool connect, bool left)
template<class Arc >
void	TestTableMatcherCacheLeft (bool connect)
template<class Arc >
void	TestTableMatcherCacheRight (bool connect)
template<class Arc >
void	TableCompose (const Fst< Arc > &ifst1, const Fst< Arc > &ifst2, MutableFst< Arc > *ofst, const TableComposeOptions &opts=TableComposeOptions())
template<class Arc >
void	TableCompose (const Fst< Arc > &ifst1, const Fst< Arc > &ifst2, MutableFst< Arc > *ofst, TableComposeCache< Fst< Arc > > *cache)
template<class Arc >
void	TestFactor ()
static ConstFst< StdArc > *	ReadConstFstFromStream (std::istream &is)
static void	InputDeterminizeSingleState (StdArc::StateId s, VectorFst< StdArc > *fst)
	This utility function input-determinizes a specified state s of the FST 'fst'. More...
void	PrepareForGrammarFst (int32 nonterm_phones_offset, VectorFst< StdArc > *fst)
	This function prepares 'ifst' for use in GrammarFst: it ensures that it has the expected properties, changing it slightly as needed. More...
void	CopyToVectorFst (GrammarFst *grammar_fst, VectorFst< StdArc > *vector_fst)
	This function copies a GrammarFst to a VectorFst (intended mostly for testing and comparison purposes). More...
template<class T >
ArcticWeightTpl< T >	Plus (const ArcticWeightTpl< T > &w1, const ArcticWeightTpl< T > &w2)
ArcticWeightTpl< float >	Plus (const ArcticWeightTpl< float > &w1, const ArcticWeightTpl< float > &w2)
ArcticWeightTpl< double >	Plus (const ArcticWeightTpl< double > &w1, const ArcticWeightTpl< double > &w2)
template<class T >
ArcticWeightTpl< T >	Times (const ArcticWeightTpl< T > &w1, const ArcticWeightTpl< T > &w2)
ArcticWeightTpl< float >	Times (const ArcticWeightTpl< float > &w1, const ArcticWeightTpl< float > &w2)
ArcticWeightTpl< double >	Times (const ArcticWeightTpl< double > &w1, const ArcticWeightTpl< double > &w2)
template<class T >
ArcticWeightTpl< T >	Divide (const ArcticWeightTpl< T > &w1, const ArcticWeightTpl< T > &w2, DivideType typ=DIVIDE_ANY)
ArcticWeightTpl< float >	Divide (const ArcticWeightTpl< float > &w1, const ArcticWeightTpl< float > &w2, DivideType typ=DIVIDE_ANY)
ArcticWeightTpl< double >	Divide (const ArcticWeightTpl< double > &w1, const ArcticWeightTpl< double > &w2, DivideType typ=DIVIDE_ANY)
template<class Arc >
void	TestDeterminizeLatticePruned ()
template<class Arc >
void	TestDeterminizeLatticePruned2 ()
template<class Weight , class IntType >
bool	DeterminizeLatticePruned (const ExpandedFst< ArcTpl< Weight > > &ifst, double beam, MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, IntType > > > *ofst, DeterminizeLatticePrunedOptions opts)
template<class Weight >
bool	DeterminizeLatticePruned (const ExpandedFst< ArcTpl< Weight > > &ifst, double prune, MutableFst< ArcTpl< Weight > > *ofst, DeterminizeLatticePrunedOptions opts=DeterminizeLatticePrunedOptions())
	This function implements the normal version of DeterminizeLattice, in which the output strings are represented using sequences of arcs, where all but the first one has an epsilon on the input side. More...
template<class Weight >
ArcTpl< Weight >::Label	DeterminizeLatticeInsertPhones (const kaldi::TransitionModel &trans_model, MutableFst< ArcTpl< Weight > > *fst)
	This function takes in lattices and inserts phones at phone boundaries. More...
template<class Weight >
void	DeterminizeLatticeDeletePhones (typename ArcTpl< Weight >::Label first_phone_label, MutableFst< ArcTpl< Weight > > *fst)
	This function takes in lattices and deletes "phones" from them. More...
template void	DeterminizeLatticeDeletePhones (ArcTpl< kaldi::LatticeWeight >::Label first_phone_label, MutableFst< ArcTpl< kaldi::LatticeWeight > > *fst)
template<class Weight , class IntType >
bool	DeterminizeLatticePhonePrunedFirstPass (const kaldi::TransitionModel &trans_model, double beam, MutableFst< ArcTpl< Weight > > *fst, const DeterminizeLatticePrunedOptions &opts)
	This function does a first pass determinization with phone symbols inserted at phone boundary. More...
template<class Weight , class IntType >
bool	DeterminizeLatticePhonePruned (const kaldi::TransitionModel &trans_model, MutableFst< ArcTpl< Weight > > *ifst, double prune, MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, IntType > > > *ofst, DeterminizeLatticePhonePrunedOptions opts=DeterminizeLatticePhonePrunedOptions())
	"Destructive" version of DeterminizeLatticePhonePruned() where the input lattice might be changed. More...
template<class Weight , class IntType >
bool	DeterminizeLatticePhonePruned (const kaldi::TransitionModel &trans_model, const ExpandedFst< ArcTpl< Weight > > &ifst, double prune, MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, IntType > > > *ofst, DeterminizeLatticePhonePrunedOptions opts=DeterminizeLatticePhonePrunedOptions())
	This function is a wrapper of DeterminizeLatticePhonePrunedFirstPass() and DeterminizeLatticePruned(). More...
bool	DeterminizeLatticePhonePrunedWrapper (const kaldi::TransitionModel &trans_model, MutableFst< kaldi::LatticeArc > *ifst, double prune, MutableFst< kaldi::CompactLatticeArc > *ofst, DeterminizeLatticePhonePrunedOptions opts=DeterminizeLatticePhonePrunedOptions())
	This function is a wrapper of DeterminizeLatticePhonePruned() that works for Lattice type FSTs. More...
template bool	DeterminizeLatticePruned< kaldi::LatticeWeight > (const ExpandedFst< kaldi::LatticeArc > &ifst, double prune, MutableFst< kaldi::CompactLatticeArc > *ofst, DeterminizeLatticePrunedOptions opts)
template bool	DeterminizeLatticePruned< kaldi::LatticeWeight > (const ExpandedFst< kaldi::LatticeArc > &ifst, double prune, MutableFst< kaldi::LatticeArc > *ofst, DeterminizeLatticePrunedOptions opts)
template bool	DeterminizeLatticePhonePruned< kaldi::LatticeWeight, kaldi::int32 > (const kaldi::TransitionModel &trans_model, const ExpandedFst< kaldi::LatticeArc > &ifst, double prune, MutableFst< kaldi::CompactLatticeArc > *ofst, DeterminizeLatticePhonePrunedOptions opts)
template bool	DeterminizeLatticePhonePruned< kaldi::LatticeWeight, kaldi::int32 > (const kaldi::TransitionModel &trans_model, MutableFst< kaldi::LatticeArc > *ifst, double prune, MutableFst< kaldi::CompactLatticeArc > *ofst, DeterminizeLatticePhonePrunedOptions opts)
template<class Weight , class IntType >
bool	MinimizeCompactLattice (MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, IntType > > > *clat, float delta=fst::kDelta)
	This function minimizes the compact lattice. More...
template bool	MinimizeCompactLattice< kaldi::LatticeWeight, kaldi::int32 > (MutableFst< kaldi::CompactLatticeArc > *clat, float delta)
template<class Weight , class IntType >
bool	PushCompactLatticeStrings (MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, IntType > > > *clat)
	This function pushes the transition-ids as far towards the start as they will go. More...
template<class Weight , class IntType >
bool	PushCompactLatticeWeights (MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, IntType > > > *clat)
	This function pushes the weights in the CompactLattice so that all states except possibly the start state, have Weight components (of type LatticeWeight) that "sum to one" in the LatticeWeight (i.e. More...
template bool	PushCompactLatticeStrings< kaldi::LatticeWeight, kaldi::int32 > (MutableFst< kaldi::CompactLatticeArc > *clat)
template bool	PushCompactLatticeWeights< kaldi::LatticeWeight, kaldi::int32 > (MutableFst< kaldi::CompactLatticeArc > *clat)
static void	InputDeterminizeSingleState (StdArc::StateId s, VectorFst< StdArc > *fst)
template<class Arc , class I >
void	RemoveArcsWithSomeInputSymbols (const std::vector< I > &symbols_in, VectorFst< Arc > *fst)
template<class Arc , class I >
void	PenalizeArcsWithSomeInputSymbols (const std::vector< I > &symbols_in, float penalty, VectorFst< Arc > *fst)
ConstFst< StdArc > *	ReadAsConstFst (std::string rxfilename)
bool	PrintProxyFstPath (const VectorFst< StdArc > &proxy, vector< vector< StdArc::Label > > *path, vector< StdArc::Weight > *weight, StdArc::StateId cur_state, vector< StdArc::Label > cur_path, StdArc::Weight cur_weight)

Detailed Description

For an extended explanation of the framework of which grammar-fsts are a part, please see Support for grammars and graphs with on-the-fly parts. (i.e.

../doc/grammar.dox).

This header implements a special FST type which we use in that framework; it is a lightweight wrapper which stitches together several FSTs and makes them look, to the decoder code, like a single FST. It is a bit like OpenFst's Replace() function, but with support for left-biphone context.

Typedef Documentation

ArcticWeight

typedef ArcticWeightTpl<float> ArcticWeight

Definition at line 84 of file arctic-weight.h.

BaseFloat

typedef float BaseFloat

Definition at line 28 of file lattice-weight-test.cc.

CompactLatticeWeight

typedef CompactLatticeWeightTpl<LatticeWeight, int32> CompactLatticeWeight

Definition at line 32 of file lattice-weight-test.cc.

CompactLatticeWeightCommonDivisor

typedef CompactLatticeWeightCommonDivisorTpl<LatticeWeight, int32> CompactLatticeWeightCommonDivisor

Definition at line 35 of file lattice-weight-test.cc.

Label

typedef fst::StdArc::Label Label

Definition at line 57 of file deterministic-fst-test.cc.

LatticeWeight

typedef LatticeWeightTpl<BaseFloat> LatticeWeight

Definition at line 30 of file lattice-weight-test.cc.

StateId

typedef fst::StdArc::StateId StateId

Definition at line 58 of file deterministic-fst-test.cc.

StatePropertiesType

typedef unsigned char StatePropertiesType

Definition at line 122 of file factor.h.

StdArc

typedef fst::StdArc StdArc

Definition at line 56 of file deterministic-fst-test.cc.

StdVectorFst

typedef fst::StdVectorFst StdVectorFst

Definition at line 59 of file deterministic-fst-test.cc.

VectorFstHolder

typedef VectorFstTplHolder<StdArc> VectorFstHolder

Definition at line 151 of file kaldi-fst-io.h.

Weight

typedef fst::StdArc::Weight Weight

Definition at line 60 of file deterministic-fst-test.cc.

Enumeration Type Documentation

anonymous enum

anonymous enum

Enumerator
kStateHasEpsilonArcsEntering
kStateHasNonEpsilonArcsEntering
kStateHasEpsilonArcsLeaving
kStateHasNonEpsilonArcsLeaving

Definition at line 27 of file epsilon-property.h.

     {
  kStateHasEpsilonArcsEntering = 0x1,
  kStateHasNonEpsilonArcsEntering = 0x2,
  kStateHasEpsilonArcsLeaving = 0x4,
  kStateHasNonEpsilonArcsLeaving = 0x8
}; // use 'char' for this enum.

NonterminalValues

enum NonterminalValues

An anonymous enum to define some values for symbols used in our grammar-fst framework.

Please understand this with reference to the documentation in Support for grammars and graphs with on-the-fly parts. (../doc/grammar.dox). This enum defines the values of nonterminal-related symbols in phones.txt. They are not the actual values– they will be shifted by adding the value nonterm_phones_offset which is passed in by the command-line flag –nonterm-phones-offset.

Enumerator
kNontermBos
kNontermBegin
kNontermEnd
kNontermReenter
kNontermUserDefined
kNontermMediumNumber
kNontermBigNumber

Definition at line 68 of file grammar-context-fst.h.

                       {
  kNontermBos = 0,  // #nonterm_bos
  kNontermBegin = 1,  // #nonterm_begin
  kNontermEnd = 2,  // #nonterm_end
  kNontermReenter = 3,  // #nonterm_reenter
  kNontermUserDefined = 4,   // the lowest-numbered user-defined nonterminal, e.g. #nonterm:foo
  // kNontermMediumNumber and kNontermBigNumber come into the encoding of
  // nonterminal-related symbols in HCLG.fst.  The only hard constraint on them
  // is that kNontermBigNumber must be bigger than the biggest transition-id in
  // your system, and kNontermMediumNumber must be >0.  These values were chosen
  // for ease of human inspection of numbers encoded with them.
  kNontermMediumNumber = 1000,
  kNontermBigNumber = 10000000
};

StatePropertiesEnum

enum StatePropertiesEnum

Enumerator
kStateFinal
kStateInitial
kStateArcsIn
kStateMultipleArcsIn
kStateArcsOut
kStateMultipleArcsOut
kStateOlabelsOut
kStateIlabelsOut

Definition at line 112 of file factor.h.

{ kStateFinal = 0x1,
  kStateInitial = 0x2,
  kStateArcsIn = 0x4,
  kStateMultipleArcsIn = 0x8,
  kStateArcsOut = 0x10,
  kStateMultipleArcsOut = 0x20,
  kStateOlabelsOut = 0x40,
  kStateIlabelsOut = 0x80 };

Function Documentation

AcousticLatticeScale()

std::vector<std::vector<double> > fst::AcousticLatticeScale ( double  acwt )

inline

Definition at line 138 of file lattice-utils.h.

Referenced by DiscriminativeSupervisionSplitter::CreateRangeLattice(), kaldi::DecodeUtterance(), kaldi::DecodeUtteranceLatticeFaster(), kaldi::DecodeUtteranceLatticeIncremental(), kaldi::DecodeUtteranceLatticeSimple(), main(), DeterminizeLatticeTask::operator()(), DecodeUtteranceLatticeFasterClass::operator()(), DiscriminativeSupervisionSplitter::PrepareLattice(), and NnetBatchDecoder::ProcessOutputUtterance().

                                                                       {
  std::vector<std::vector<double> > ans(2);
  ans[0].resize(2, 0.0);
  ans[1].resize(2, 0.0);
  ans[0][0] = 1.0;
  ans[1][1] = acwt;
  return ans;
}

AddSelfLoops()

void AddSelfLoops	(	MutableFst< Arc > *	fst,
		std::vector< typename Arc::Label > &	isyms,
		std::vector< typename Arc::Label > &	osyms
	)

AddSelfLoops is a function you will probably want to use alongside PreDeterminize, to add self-loops to any FSTs that you compose on the left hand side of the one modified by PreDeterminize.

This function inserts loops with "special symbols" [e.g. #0, #1] into an FST. This is done at each final state and each state with non-epsilon output symbols on at least one arc out of it. This is to ensure that these symbols, when inserted into the input side of an FST we will compose with on the right, can "pass through" this FST.

At input, isyms and osyms must be vectors of the same size n, corresponding to symbols that currently do not exist in 'fst'. For each state in n that has non-epsilon symbols on the output side of arcs leaving it, or which is a final state, this function inserts n self-loops with unit weight and one of the n pairs of symbols on its input and output.

Definition at line 599 of file pre-determinize-inl.h.

References rnnlm::i, and rnnlm::n.

Referenced by TestAddSelfLoops().

                                                                           {
  assert(fst != NULL);
  assert(isyms.size() == osyms.size());
  typedef typename Arc::Label Label;
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Weight Weight;
  size_t n = isyms.size();
  if (n == 0) return;  // Nothing to do.

  // {
  // the following declarations and statements are for quick detection of these
  // symbols, which is purely for debugging/checking purposes.
  Label  isyms_min = *std::min_element(isyms.begin(), isyms.end()),
         isyms_max = *std::max_element(isyms.begin(), isyms.end()),
         osyms_min = *std::min_element(osyms.begin(), osyms.end()),
         osyms_max = *std::max_element(osyms.begin(), osyms.end());
  std::set<Label> isyms_set, osyms_set;
  for (size_t i = 0; i < isyms.size(); i++) {
    assert(isyms[i] > 0 && osyms[i] > 0);  // should not have epsilon or invalid symbols.
    isyms_set.insert(isyms[i]);
    osyms_set.insert(osyms[i]);
  }
  assert(isyms_set.size() == n && osyms_set.size() == n);
  // } end block.

  for (StateIterator<MutableFst<Arc> > siter(*fst); ! siter.Done(); siter.Next()) {
    StateId state = siter.Value();
    bool this_state_needs_self_loops = (fst->Final(state) != Weight::Zero());
    for (ArcIterator<MutableFst<Arc> > aiter(*fst, state); ! aiter.Done(); aiter.Next()) {
      const Arc &arc = aiter.Value();
      // If one of the following asserts fails, it means that the input FST already had the symbols
      // we are inserting.  This is contrary to the preconditions of this algorithm.
      assert(!(arc.ilabel>=isyms_min && arc.ilabel<=isyms_max && isyms_set.count(arc.ilabel) != 0));
      assert(!(arc.olabel>=osyms_min && arc.olabel<=osyms_max && osyms_set.count(arc.olabel) != 0));
      if (arc.olabel != 0) // Has non-epsilon output label -> need self loops.
        this_state_needs_self_loops = true;
    }
    if (this_state_needs_self_loops) {
      for (size_t i = 0;i < n;i++) {
        Arc arc;
        arc.ilabel = isyms[i];
        arc.olabel = osyms[i];
        arc.weight = Weight::One();
        arc.nextstate = state;
        fst->AddArc(state, arc);
      }
    }
  }
}

AddSubsequentialLoop()

void AddSubsequentialLoop	(	StdArc::Label	subseq_symbol,
		MutableFst< StdArc > *	fst
	)

Modifies an FST so that it transuces the same paths, but the input side of the paths can all have the subsequential symbol '$' appended to them any number of times (we could easily specify the number of times, but accepting any number of repetitions is just more convenient).

The actual way we do this is for each final state, we add a transition with weight equal to the final-weight of that state, with input-symbol '$' and output-symbols <eps>, and ending in a new super-final state that has unit final-probability and a unit-weight self-loop with '$' on its input and <eps> on its output. The reason we don't just add a loop to each final-state has to do with preserving stochasticity (see Preserving stochasticity and testing it). We keep the final-probability in all the original final-states rather than setting them to zero, so the resulting FST can accept zero '$' symbols at the end (in case we had no right context).

Definition at line 297 of file context-fst.cc.

References rnnlm::i.

Referenced by ComposeContext(), main(), and TrainingGraphCompiler::TrainingGraphCompiler().

                                                   {
  typedef StdArc Arc;
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Weight Weight;

  vector<StateId> final_states;
  for (StateIterator<MutableFst<Arc> > siter(*fst); !siter.Done(); siter.Next()) {
    StateId s = siter.Value();
    if (fst->Final(s) != Weight::Zero())  final_states.push_back(s);
  }

  StateId superfinal = fst->AddState();
  Arc arc(subseq_symbol, 0, Weight::One(), superfinal);
  fst->AddArc(superfinal, arc);  // loop at superfinal.
  fst->SetFinal(superfinal, Weight::One());

  for (size_t i = 0; i < final_states.size(); i++) {
    StateId s = final_states[i];
    fst->AddArc(s, Arc(subseq_symbol, 0, fst->Final(s), superfinal));
    // No, don't remove the final-weights of the original states..
    // this is so we can add the subsequential loop in cases where
    // there is no context, and it won't hurt.
    // fst->SetFinal(s, Weight::Zero());
    arc.nextstate = final_states[i];
  }
}

ApplyProbabilityScale()

void ApplyProbabilityScale	(	float	scale,
		MutableFst< Arc > *	fst
	)

ApplyProbabilityScale is applicable to FSTs in the log or tropical semiring.

It multiplies the arc and final weights by "scale" [this is not the Mul operation of the semiring, it's actual multiplication, which is equivalent to taking a power in the semiring].

Definition at line 771 of file fstext-utils-inl.h.

Referenced by kaldi::GetHmmAsFsa(), main(), and MinimizeEncoded().

                                                              {
  typedef typename Arc::Weight Weight;
  typedef typename Arc::StateId StateId;
  for (StateIterator<MutableFst<Arc> > siter(*fst);
       !siter.Done();
       siter.Next()) {
    StateId s = siter.Value();
    for (MutableArcIterator<MutableFst<Arc> > aiter(fst, s);
        !aiter.Done();
        aiter.Next()) {
      Arc arc = aiter.Value();
      arc.weight = Weight(arc.weight.Value() * scale);
      aiter.SetValue(arc);
    }
    if (fst->Final(s) != Weight::Zero())
      fst->SetFinal(s, Weight(fst->Final(s).Value() * scale));
  }
}

ApproxEqual() [1/2]

bool fst::ApproxEqual ( const LatticeWeightTpl< FloatType > &  w1, const LatticeWeightTpl< FloatType > &  w2, float  delta = kDelta  )

inline

Definition at line 389 of file lattice-weight.h.

References LatticeWeightTpl< FloatType >::Value1(), and LatticeWeightTpl< FloatType >::Value2().

Referenced by DeterminizerStar< F >::EpsilonClosure::AddOneElement(), ApproxEqual(), CompactLatticeWeightTest(), CompactLatticeMinimizer< Weight, IntType >::Equivalent(), IsStochasticFst(), LatticeWeightTest(), DeterminizerStar< F >::SubsetEqual::operator()(), LatticeDeterminizerPruned< Weight, IntType >::SubsetEqual::operator()(), LatticeDeterminizer< Weight, IntType >::SubsetEqual::operator()(), TestBackoffAndCache(), TestCompose(), TestRemoveEpsLocalSpecial(), TestRemoveUselessArcs(), and TestShortestPath().

                                              {
  if (w1.Value1() == w2.Value1() && w1.Value2() == w2.Value2()) return true;  // handles Zero().
  return (fabs((w1.Value1() + w1.Value2()) - (w2.Value1() + w2.Value2())) <= delta);
}

ApproxEqual() [2/2]

bool fst::ApproxEqual ( const CompactLatticeWeightTpl< WeightType, IntType > &  w1, const CompactLatticeWeightTpl< WeightType, IntType > &  w2, float  delta = kDelta  )

inline

Definition at line 570 of file lattice-weight.h.

References ApproxEqual(), CompactLatticeWeightTpl< WeightType, IntType >::String(), and CompactLatticeWeightTpl< WeightType, IntType >::Weight().

                                              {
  return (ApproxEqual(w1.Weight(), w2.Weight(), delta) && w1.String() == w2.String());
}

CastOrConvertToVectorFst()

VectorFst< StdArc > * CastOrConvertToVectorFst

(

Fst< StdArc > *

fst

)

Definition at line 94 of file kaldi-fst-io.cc.

References KALDI_ASSERT.

Referenced by main().

                                                              {
  // This version currently supports ConstFst<StdArc> or VectorFst<StdArc>
  std::string real_type = fst->Type();
  KALDI_ASSERT(real_type == "vector" || real_type == "const");
  if (real_type == "vector") {
    return dynamic_cast<VectorFst<StdArc> *>(fst);
  } else {
    // As the 'fst' can't cast to VectorFst, we create a new
    // VectorFst<StdArc> initialized by 'fst', and delete 'fst'.
    VectorFst<StdArc> *new_fst = new VectorFst<StdArc>(*fst);
    delete fst;
    return new_fst;
  }
}

CheckPhones()

static float fst::CheckPhones ( const VectorFst< Arc > &  linear_fst, const vector< typename Arc::Label > &  phone_ids, const vector< typename Arc::Label > &  disambig_ids, const vector< typename Arc::Label > &  phone_seq, const vector< vector< typename Arc::Label > > &  ilabel_info, int  N, int  P  )

static

Definition at line 71 of file context-fst-test.cc.

References GetLinearSymbolSequence(), rnnlm::i, kaldi::IsSorted(), and rnnlm::j.

                                        {
  typedef typename Arc::Label Label;
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Weight Weight;

  assert(kaldi::IsSorted(phone_ids));  // so we can do binary_search.


  vector<int32> input_syms;
  vector<int32> output_syms;
  Weight tot_cost;
  bool ans = GetLinearSymbolSequence(linear_fst,  &input_syms,
                                     &output_syms, &tot_cost);
  assert(ans);  // should be linear.

  vector<int32> phone_seq_check;
  for (size_t i = 0; i < output_syms.size(); i++)
    if (std::binary_search(phone_ids.begin(), phone_ids.end(), output_syms[i]))
      phone_seq_check.push_back(output_syms[i]);

  assert(phone_seq_check  == phone_seq);

  vector<vector<int32> > input_syms_long;
  for (size_t i = 0; i < input_syms.size(); i++) {
    Label isym = input_syms[i];
    if (ilabel_info[isym].size() == 0) continue;  // epsilon.
    if ( (ilabel_info[isym].size() == 1 &&
         ilabel_info[isym][0] <= 0) ) continue;  // disambig.
    input_syms_long.push_back(ilabel_info[isym]);
  }

  for (size_t i = 0; i < input_syms_long.size(); i++) {
    vector<int32> phone_context_window(N);  // phone at pos i will be at pos P in this window.
    int pos = ((int)i) - P;  // pos of first phone in window [ may be out of range] .
    for (int j = 0; j < N; j++, pos++) {
      if (static_cast<size_t>(pos) < phone_seq.size()) phone_context_window[j] = phone_seq[pos];
      else phone_context_window[j] = 0;  // 0 is a special symbol that context-dep-itf expects to see
      // when no phone is present due to out-of-window.  context-fst knows about this too.
    }
    assert(input_syms_long[i] == phone_context_window);
  }
  return tot_cost.Value();
}

ClearSymbols()

void ClearSymbols	(	bool	clear_input,
		bool	clear_output,
		MutableFst< Arc > *	fst
	)

ClearSymbols sets all the symbols on the input and/or output side of the FST to zero, as specified.

It does not alter the symbol tables.

Definition at line 742 of file fstext-utils-inl.h.

Referenced by MakeLoopFstCompare().

                                        {
  for (StateIterator<MutableFst<Arc> > siter(*fst);
       !siter.Done();
       siter.Next()) {
    typename Arc::StateId s = siter.Value();
    for (MutableArcIterator<MutableFst<Arc> > aiter(fst, s);
         !aiter.Done();
         aiter.Next()) {
      Arc arc = aiter.Value();
      bool change = false;
      if (clear_input && arc.ilabel != 0) {
        arc.ilabel = 0;
        change = true;
      }
      if (clear_output && arc.olabel != 0) {
        arc.olabel = 0;
        change = true;
      }
      if (change) {
        aiter.SetValue(arc);
      }
    }
  }
}

CompactLatticeHasAlignment()

bool CompactLatticeHasAlignment

(

const ExpandedFst< ArcTpl< CompactLatticeWeightTpl< Weight, Int > > > &

fst

)

Returns true if lattice has alignments, i.e.

it has any nonempty strings inside its weights.

Definition at line 244 of file lattice-utils-inl.h.

Referenced by LatticeScale().

                                                                            {
  typedef CompactLatticeWeightTpl<Weight, Int> W;
  typedef ArcTpl<W> Arc;
  typedef ExpandedFst<Arc> Fst;
  typedef typename Arc::StateId StateId;
  StateId num_states = fst.NumStates();
  for (StateId s = 0; s < num_states; s++) {
    for (ArcIterator<Fst> aiter(fst, s);
         !aiter.Done();
         aiter.Next()) {
      const Arc &arc = aiter.Value();
      if (!arc.weight.String().empty()) return true;
    }
    W final_weight = fst.Final(s);
    if (!final_weight.String().empty()) return true;
  }
  return false;
}

CompactLatticeWeightTest()

void fst::CompactLatticeWeightTest

(

)

Definition at line 126 of file lattice-weight-test.cc.

References ApproxEqual(), Compare(), Divide(), rnnlm::i, KALDI_ASSERT, CompactLatticeWeightTpl< WeightType, IntType >::Member(), CompactLatticeWeightTpl< WeightType, IntType >::One(), Plus(), CompactLatticeWeightTpl< WeightType, IntType >::Quantize(), RandomCompactLatticeWeight(), CompactLatticeWeightTpl< WeightType, IntType >::Read(), Times(), and CompactLatticeWeightTpl< WeightType, IntType >::Zero().

Referenced by main().

                                {
  for(int32 i = 0; i < 100; i++) {
    CompactLatticeWeight l1 = RandomCompactLatticeWeight(), l2 = RandomCompactLatticeWeight();
    CompactLatticeWeight l3 = Plus(l1, l2);
    CompactLatticeWeight l4 = Times(l1, l2);

    KALDI_ASSERT(Plus(l3, l3) == l3);
    KALDI_ASSERT(Plus(l1, l2) == Plus(l2, l1)); // commutativity of plus
    KALDI_ASSERT(Plus(l3, CompactLatticeWeight::Zero()) == l3); // x + 0 = x
    KALDI_ASSERT(Times(l3, CompactLatticeWeight::One()) == l3); // x * 1 = x
    KALDI_ASSERT(Times(l3, CompactLatticeWeight::Zero()) == CompactLatticeWeight::Zero()); // x * 0 = 0
    NaturalLess<CompactLatticeWeight> nl;
    bool a = nl(l1, l2);
    bool b = (Plus(l1, l2) == l1 && l1 != l2);
    KALDI_ASSERT(a == b);

    KALDI_ASSERT(Compare(l1, Plus(l1, l2)) != 1); // so do not have l1 > l1 + l2
    CompactLatticeWeight l5 = RandomCompactLatticeWeight(), l6 = RandomCompactLatticeWeight();
    KALDI_ASSERT(Times(Plus(l1, l2), Plus(l5, l6)) ==
                 Plus(Times(l1, l5), Plus(Times(l1, l6),
                 Plus(Times(l2, l5), Times(l2, l6))))); // * distributes over +
    KALDI_ASSERT(l1.Member() && l2.Member() && l3.Member() && l4.Member()
                 && l5.Member() && l6.Member());
    if (l2 != CompactLatticeWeight::Zero())  {
      KALDI_ASSERT(ApproxEqual(Divide(Times(l1, l2), l2, DIVIDE_RIGHT), l1)); // (a*b) / b = a if b != 0
      KALDI_ASSERT(ApproxEqual(Divide(Times(l2, l1), l2, DIVIDE_LEFT), l1)); // (a*b) / b = a if b != 0
    }
    KALDI_ASSERT(ApproxEqual(l1, l1.Quantize()));

    std::ostringstream s1;
    s1 << l1;
    std::istringstream s2(s1.str());
    s2 >> l2;
    KALDI_ASSERT(ApproxEqual(l1, l2));
    std::cout << s1.str() << '\n';

    {
      std::ostringstream s1b;
      l1.Write(s1b);
      std::istringstream s2b(s1b.str());
      l3.Read(s2b);
      KALDI_ASSERT(l1 == l3);
    }

    CompactLatticeWeightCommonDivisor divisor;
    std::cout << "l5 = " << l5 << '\n';
    std::cout << "l6 = " << l6 << '\n';
    l1 = divisor(l5, l6);
    std::cout << "div = " << l1 << '\n';
    if (l1 != CompactLatticeWeight::Zero()) {
      l2 = Divide(l5, l1, DIVIDE_LEFT);
      l3 = Divide(l6, l1, DIVIDE_LEFT);
      std::cout << "l2 = " << l2 << '\n';
      std::cout << "l3 = " << l3 << '\n';
      l4 = divisor(l2, l3); // make sure l2 is now one.
      std::cout << "l4 = " << l4 << '\n';
      KALDI_ASSERT(ApproxEqual(l4, CompactLatticeWeight::One()));
    } else {
      KALDI_ASSERT(l5 == CompactLatticeWeight::Zero()
                   && l6 == CompactLatticeWeight::Zero());
    }
  }
}

Compare() [1/3]

int fst::Compare ( const LatticeWeightTpl< FloatType > &  w1, const LatticeWeightTpl< FloatType > &  w2  )

inline

Compare returns -1 if w1 < w2, +1 if w1 > w2, and 0 if w1 == w2.

Definition at line 294 of file lattice-weight.h.

References LatticeWeightTpl< FloatType >::Value1(), and LatticeWeightTpl< FloatType >::Value2().

Referenced by CompactLatticeWeightTest(), Compare(), LatticeDeterminizerPruned< Weight, IntType >::Compare(), LatticeDeterminizer< Weight, IntType >::Compare(), PruneSpecialClass< Arc >::Done(), LatticeDeterminizerPruned< Weight, IntType >::EpsilonClosure(), LatticeDeterminizer< Weight, IntType >::EpsilonClosure(), LatticeWeightTest(), LatticeDeterminizer< Weight, IntType >::MakeSubsetUnique(), NaturalLess< LatticeWeightTpl< FloatType > >::operator()(), NaturalLess< LatticeWeightTpl< float > >::operator()(), NaturalLess< LatticeWeightTpl< double > >::operator()(), NaturalLess< CompactLatticeWeightTpl< LatticeWeightTpl< FloatType >, IntType > >::operator()(), NaturalLess< CompactLatticeWeightTpl< LatticeWeightTpl< float >, int32 > >::operator()(), NaturalLess< CompactLatticeWeightTpl< LatticeWeightTpl< double >, int32 > >::operator()(), PruneSpecialClass< Arc >::Task::operator<(), Plus(), LatticeDeterminizer< Weight, IntType >::ProcessFinal(), and PruneSpecialClass< Arc >::ProcessState().

                                                           {
  FloatType f1 = w1.Value1() + w1.Value2(),
      f2 = w2.Value1() + w2.Value2();
  if (f1 < f2) { return 1; } // having smaller cost means you're larger
  // in the semiring [higher probability]
  else if (f1 > f2) { return -1; }
  // mathematically we should be comparing (w1.value1_-w1.value2_ < w2.value1_-w2.value2_)
  // in the next line, but add w1.value1_+w1.value2_ = w2.value1_+w2.value2_ to both sides and
  // divide by two, and we get the simpler equivalent form w1.value1_ < w2.value1_.
  else if (w1.Value1() < w2.Value1()) { return 1; }
  else if (w1.Value1() > w2.Value1()) { return -1; }
  else { return 0; }
}

Compare() [2/3]

int fst::Compare ( const CompactLatticeWeightTpl< WeightType, IntType > &  w1, const CompactLatticeWeightTpl< WeightType, IntType > &  w2  )

inline

Definition at line 591 of file lattice-weight.h.

References Compare(), rnnlm::i, CompactLatticeWeightTpl< WeightType, IntType >::String(), and CompactLatticeWeightTpl< WeightType, IntType >::Weight().

                                                                           {
  int c1 = Compare(w1.Weight(), w2.Weight());
  if (c1 != 0) return c1;
  int l1 = w1.String().size(), l2 = w2.String().size();
  // Use opposite order on the string lengths, so that if the costs are the same,
  // the shorter string wins.
  if (l1 > l2) return -1;
  else if (l1 < l2) return 1;
  for(int i = 0; i < l1; i++) {
    if (w1.String()[i] < w2.String()[i]) return -1;
    else if (w1.String()[i] > w2.String()[i]) return 1;
  }
  return 0;
}

Compare() [3/3]

int fst::Compare ( const TropicalWeight &  w1, const TropicalWeight &  w2  )

inline

Definition at line 653 of file lattice-weight.h.

                                             {
  float f1 = w1.Value(), f2 = w2.Value();
  if (f1 == f2) return 0;
  else if (f1 > f2) return -1;
  else return 1;
}

ComposeContext() [1/2]

void fst::ComposeContext	(	const std::vector< int32 > &	disambig_syms,
		int32	context_width,
		int32	central_position,
		VectorFst< StdArc > *	ifst,
		VectorFst< StdArc > *	ofst,
		std::vector< std::vector< int32 > > *	ilabels_out,
		bool	project_ifst = false
	)

Used in the command-line tool fstcomposecontext.

It creates a context FST and composes it on the left with "ifst" to make "ofst". It outputs the label information to ilabels_out. "ifst" is mutable because we need to add the subsequential loop.

Parameters

[in]	disambig_syms	List of disambiguation symbols, e.g. the integer ids of #0, #1, #2 ... in the phones.txt.
[in]	context_width	Size of context window, e.g. 3 for triphone.
[in]	central_position	Central position in phonetic context window (zero-based index), e.g. 1 for triphone.
[in,out]	ifst	The FST we are composing with C (e.g. LG.fst), mustable because we need to add the subsequential loop to it.
[out]	ofst	Composed output FST (would be CLG.fst).
[out]	ilabels_out	Vector, indexed by ilabel of CLG.fst, providing information about the meaning of that ilabel; see "http://kaldi-asr.org/doc/tree_externals.html#tree_ilabel".
[in]	project_ifst	This is intended only to be set to true in the program 'fstmakecontextfst'... if true, it will project on the input after adding the subsequential loop to 'ifst', which allows us to reconstruct the context fst C.fst.

Definition at line 246 of file context-fst.cc.

References AddSubsequentialLoop(), ComposeDeterministicOnDemandInverse(), GetInputSymbols(), rnnlm::i, KALDI_ASSERT, and InverseContextFst::SwapIlabelInfo().

Referenced by main().

                                       {
  KALDI_ASSERT(ifst != NULL && ofst != NULL);
  KALDI_ASSERT(context_width > 0);
  KALDI_ASSERT(central_position >= 0);
  KALDI_ASSERT(central_position < context_width);

  vector<int32> disambig_syms(disambig_syms_in);
  std::sort(disambig_syms.begin(), disambig_syms.end());

  vector<int32> all_syms;
  GetInputSymbols(*ifst, false/*no eps*/, &all_syms);
  std::sort(all_syms.begin(), all_syms.end());
  vector<int32> phones;
  for (size_t i = 0; i < all_syms.size(); i++)
    if (!std::binary_search(disambig_syms.begin(),
                            disambig_syms.end(), all_syms[i]))
      phones.push_back(all_syms[i]);

  // Get subsequential symbol that does not clash with
  // any disambiguation symbol or symbol in the FST.
  int32 subseq_sym = 1;
  if (!all_syms.empty())
    subseq_sym = std::max(subseq_sym, all_syms.back() + 1);
  if (!disambig_syms.empty())
    subseq_sym = std::max(subseq_sym, disambig_syms.back() + 1);

  // if central_position == context_width-1, it's left-context, and no
  // subsequential symbol is needed.
  if (central_position != context_width-1) {
    AddSubsequentialLoop(subseq_sym, ifst);
    if (project_ifst) {
      fst::Project(ifst, fst::PROJECT_INPUT);
    }
  }

  InverseContextFst inv_c(subseq_sym, phones, disambig_syms,
                          context_width, central_position);

  // The following statement is equivalent to the following
  // (if FSTs had the '*' operator for composition):
  //   (*ofst) = inv(inv_c) * (*ifst)
  ComposeDeterministicOnDemandInverse(*ifst, &inv_c, ofst);

  inv_c.SwapIlabelInfo(ilabels_out);
}

ComposeContext() [2/2]

void fst::ComposeContext	(	const std::vector< int32 > &	disambig_syms,
		int32	context_width,
		int32	central_position,
		VectorFst< StdArc > *	ifst,
		VectorFst< StdArc > *	ofst,
		std::vector< std::vector< int32 > > *	ilabels_out,
		bool	project_ifst = false
	)

Used in the command-line tool fstcomposecontext.

It creates a context FST and composes it on the left with "ifst" to make "ofst". It outputs the label information to ilabels_out. "ifst" is mutable because we need to add the subsequential loop.

Parameters

[in]	disambig_syms	List of disambiguation symbols, e.g. the integer ids of #0, #1, #2 ... in the phones.txt.
[in]	context_width	Size of context window, e.g. 3 for triphone.
[in]	central_position	Central position in phonetic context window (zero-based index), e.g. 1 for triphone.
[in,out]	ifst	The FST we are composing with C (e.g. LG.fst), mustable because we need to add the subsequential loop to it.
[out]	ofst	Composed output FST (would be CLG.fst).
[out]	ilabels_out	Vector, indexed by ilabel of CLG.fst, providing information about the meaning of that ilabel; see "http://kaldi-asr.org/doc/tree_externals.html#tree_ilabel".
[in]	project_ifst	This is intended only to be set to true in the program 'fstmakecontextfst'... if true, it will project on the input after adding the subsequential loop to 'ifst', which allows us to reconstruct the context fst C.fst.

Definition at line 246 of file context-fst.cc.

References AddSubsequentialLoop(), ComposeDeterministicOnDemandInverse(), GetInputSymbols(), rnnlm::i, KALDI_ASSERT, and InverseContextFst::SwapIlabelInfo().

Referenced by main().

                                       {
  KALDI_ASSERT(ifst != NULL && ofst != NULL);
  KALDI_ASSERT(context_width > 0);
  KALDI_ASSERT(central_position >= 0);
  KALDI_ASSERT(central_position < context_width);

  vector<int32> disambig_syms(disambig_syms_in);
  std::sort(disambig_syms.begin(), disambig_syms.end());

  vector<int32> all_syms;
  GetInputSymbols(*ifst, false/*no eps*/, &all_syms);
  std::sort(all_syms.begin(), all_syms.end());
  vector<int32> phones;
  for (size_t i = 0; i < all_syms.size(); i++)
    if (!std::binary_search(disambig_syms.begin(),
                            disambig_syms.end(), all_syms[i]))
      phones.push_back(all_syms[i]);

  // Get subsequential symbol that does not clash with
  // any disambiguation symbol or symbol in the FST.
  int32 subseq_sym = 1;
  if (!all_syms.empty())
    subseq_sym = std::max(subseq_sym, all_syms.back() + 1);
  if (!disambig_syms.empty())
    subseq_sym = std::max(subseq_sym, disambig_syms.back() + 1);

  // if central_position == context_width-1, it's left-context, and no
  // subsequential symbol is needed.
  if (central_position != context_width-1) {
    AddSubsequentialLoop(subseq_sym, ifst);
    if (project_ifst) {
      fst::Project(ifst, fst::PROJECT_INPUT);
    }
  }

  InverseContextFst inv_c(subseq_sym, phones, disambig_syms,
                          context_width, central_position);

  // The following statement is equivalent to the following
  // (if FSTs had the '*' operator for composition):
  //   (*ofst) = inv(inv_c) * (*ifst)
  ComposeDeterministicOnDemandInverse(*ifst, &inv_c, ofst);

  inv_c.SwapIlabelInfo(ilabels_out);
}

ComposeContextLeftBiphone() [1/2]

void fst::ComposeContextLeftBiphone	(	int32	nonterm_phones_offset,
		const std::vector< int32 > &	disambig_syms,
		const VectorFst< StdArc > &	ifst,
		VectorFst< StdArc > *	ofst,
		std::vector< std::vector< int32 > > *	ilabels
	)

This is a variant of the function ComposeContext() which is to be used with our "grammar FST" framework (see The ContextFst object, i.e.

../doc/grammar.dox, for more details). This does not take the 'context_width' and 'central_position' arguments because they are assumed to be 2 and 1 respectively (meaning, left-biphone phonetic context).

This function creates a context FST and composes it on the left with "ifst" to make "ofst".

Parameters

[in]	nonterm_phones_offset	The integer id of the symbol #nonterm_bos in the phones.txt file. You can just set this to a large value (like 1 million) if you are not actually using nonterminals (e.g. for testing purposes).
[in]	disambig_syms	List of disambiguation symbols, e.g. the integer ids of #0, #1, #2 ... in the phones.txt.
[in,out]	ifst	The FST we are composing with C (e.g. LG.fst).
[out]	ofst	Composed output FST (would be CLG.fst).
[out]	ilabels	Vector, indexed by ilabel of CLG.fst, providing information about the meaning of that ilabel; see The ilabel_info object (http://kaldi-asr.org/doc/tree_externals.html#tree_ilabel) and also Special symbols in CLG.fst (http://kaldi-asr.org/doc/grammar#grammar_special_clg).

Definition at line 196 of file grammar-context-fst.cc.

References ComposeDeterministicOnDemandInverse(), GetInputSymbols(), rnnlm::i, and InverseLeftBiphoneContextFst::SwapIlabelInfo().

Referenced by GetEncodingMultiple(), and main().

                                           {

  vector<int32> disambig_syms(disambig_syms_in);
  std::sort(disambig_syms.begin(), disambig_syms.end());

  vector<int32> all_syms;
  GetInputSymbols(ifst, false/*no eps*/, &all_syms);
  std::sort(all_syms.begin(), all_syms.end());
  vector<int32> phones;
  for (size_t i = 0; i < all_syms.size(); i++)
    if (!std::binary_search(disambig_syms.begin(),
                            disambig_syms.end(), all_syms[i]) &&
        all_syms[i] < nonterm_phones_offset)
      phones.push_back(all_syms[i]);


  InverseLeftBiphoneContextFst inv_c(nonterm_phones_offset,
                                     phones, disambig_syms);

  // The following statement is equivalent to the following
  // (if FSTs had the '*' operator for composition):
  //   (*ofst) = inv(inv_c) * (*ifst)
  ComposeDeterministicOnDemandInverse(ifst, &inv_c, ofst);

  inv_c.SwapIlabelInfo(ilabels);
}

ComposeContextLeftBiphone() [2/2]

void fst::ComposeContextLeftBiphone	(	int32	nonterm_phones_offset,
		const std::vector< int32 > &	disambig_syms,
		const VectorFst< StdArc > &	ifst,
		VectorFst< StdArc > *	ofst,
		std::vector< std::vector< int32 > > *	ilabels
	)

This is a variant of the function ComposeContext() which is to be used with our "grammar FST" framework (see The ContextFst object, i.e.

../doc/grammar.dox, for more details). This does not take the 'context_width' and 'central_position' arguments because they are assumed to be 2 and 1 respectively (meaning, left-biphone phonetic context).

This function creates a context FST and composes it on the left with "ifst" to make "ofst".

Parameters

[in]	nonterm_phones_offset	The integer id of the symbol #nonterm_bos in the phones.txt file. You can just set this to a large value (like 1 million) if you are not actually using nonterminals (e.g. for testing purposes).
[in]	disambig_syms	List of disambiguation symbols, e.g. the integer ids of #0, #1, #2 ... in the phones.txt.
[in,out]	ifst	The FST we are composing with C (e.g. LG.fst).
[out]	ofst	Composed output FST (would be CLG.fst).
[out]	ilabels	Vector, indexed by ilabel of CLG.fst, providing information about the meaning of that ilabel; see The ilabel_info object (http://kaldi-asr.org/doc/tree_externals.html#tree_ilabel) and also Special symbols in CLG.fst (http://kaldi-asr.org/doc/grammar#grammar_special_clg).

Definition at line 196 of file grammar-context-fst.cc.

References ComposeDeterministicOnDemandInverse(), GetInputSymbols(), rnnlm::i, and InverseLeftBiphoneContextFst::SwapIlabelInfo().

Referenced by GetEncodingMultiple(), and main().

                                           {

  vector<int32> disambig_syms(disambig_syms_in);
  std::sort(disambig_syms.begin(), disambig_syms.end());

  vector<int32> all_syms;
  GetInputSymbols(ifst, false/*no eps*/, &all_syms);
  std::sort(all_syms.begin(), all_syms.end());
  vector<int32> phones;
  for (size_t i = 0; i < all_syms.size(); i++)
    if (!std::binary_search(disambig_syms.begin(),
                            disambig_syms.end(), all_syms[i]) &&
        all_syms[i] < nonterm_phones_offset)
      phones.push_back(all_syms[i]);


  InverseLeftBiphoneContextFst inv_c(nonterm_phones_offset,
                                     phones, disambig_syms);

  // The following statement is equivalent to the following
  // (if FSTs had the '*' operator for composition):
  //   (*ofst) = inv(inv_c) * (*ifst)
  ComposeDeterministicOnDemandInverse(ifst, &inv_c, ofst);

  inv_c.SwapIlabelInfo(ilabels);
}

ComputeStateInfo()

void ComputeStateInfo	(	const VectorFst< Arc > &	fst,
		std::vector< char > *	epsilon_info
	)

This function will set epsilon_info to have size equal to the NumStates() of the FST, containing a logical-or of the enum values kStateHasEpsilonArcsEntering, kStateHasNonEpsilonArcsEntering, kStateHasEpsilonArcsLeaving, and kStateHasNonEpsilonArcsLeaving.

The meaning should be obvious. Note: an epsilon arc is defined as an arc where ilabel == olabel == 0.

Definition at line 28 of file epsilon-property-inl.h.

References kStateHasEpsilonArcsEntering, kStateHasEpsilonArcsLeaving, kStateHasNonEpsilonArcsEntering, and kStateHasNonEpsilonArcsLeaving.

Referenced by kaldi::CreateFactorTransducer(), EnsureEpsilonProperty(), and TestEnsureEpsilonProperty().

                                                     {
  typedef typename Arc::StateId StateId;
  typedef VectorFst<Arc> Fst;
  epsilon_info->clear();
  epsilon_info->resize(fst.NumStates(), static_cast<char>(0));
  for (StateId s = 0; s < fst.NumStates(); s++) {
    for (ArcIterator<Fst> aiter(fst, s); !aiter.Done(); aiter.Next()) {
      const Arc &arc = aiter.Value();
      if (arc.ilabel == 0 && arc.olabel == 0) {
        (*epsilon_info)[arc.nextstate] |= static_cast<char>(kStateHasEpsilonArcsEntering);
        (*epsilon_info)[s] |= static_cast<char>(kStateHasEpsilonArcsLeaving);
      } else {
        (*epsilon_info)[arc.nextstate] |= static_cast<char>(kStateHasNonEpsilonArcsEntering);
        (*epsilon_info)[s] |= static_cast<char>(kStateHasNonEpsilonArcsLeaving);
      }
    }
  }
}

ConvertFstToLattice()

void ConvertFstToLattice	(	const ExpandedFst< ArcTpl< TropicalWeight > > &	ifst,
		MutableFst< ArcTpl< LatticeWeightTpl< Real > > > *	ofst
	)

Converts TropicalWeight to LatticeWeight (puts all the weight on the first float in the lattice's pair).

Definition at line 266 of file lattice-utils-inl.h.

Referenced by ConvertLattice().

                                                        {
  int32 num_states_cache = 50000;
  fst::CacheOptions cache_opts(true, num_states_cache);
  fst::MapFstOptions mapfst_opts(cache_opts);
  StdToLatticeMapper<Real> mapper;
  MapFst<StdArc, ArcTpl<LatticeWeightTpl<Real> >,
         StdToLatticeMapper<Real> > map_fst(ifst, mapper, mapfst_opts);
  *ofst = map_fst;
}

ConvertLattice() [1/7]

void ConvertLattice	(	const ExpandedFst< ArcTpl< Weight > > &	ifst,
		MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, Int > > > *	ofst,
		bool	invert = true
	)

Convert lattice from a normal FST to a CompactLattice FST.

This is a bit like converting to the Gallic semiring, except the semiring behaves in a different way (designed to take the best path). Note: the ilabels end up as the symbols on the arcs of the output acceptor, and the olabels go to the strings. To make it the other way around (useful for the speech-recognition application), set invert=true [the default].

Definition at line 33 of file lattice-utils-inl.h.

References Factor(), and KALDI_PARANOID_ASSERT.

Referenced by ConvertLattice(), kaldi::ConvertLatticeToUnweightedAcceptor(), kaldi::ConvertToCompactLattice(), kaldi::ConvertToLattice(), DiscriminativeExampleSplitter::CreateOutputLattice(), kaldi::DecodeUtteranceLatticeIncremental(), DiscriminativeExampleSplitter::DoExcise(), kaldi::nnet2::ExampleToPdfPost(), kaldi::GetDiagnosticsAndPrintOutput(), NnetDiscriminativeUpdater::LatticeComputations(), kaldi::LatticeToString(), main(), MinimumBayesRisk::MinimumBayesRisk(), DiscriminativeExampleSplitter::PrepareLattice(), kaldi::RandCompactLattice(), kaldi::SentenceLevelConfidence(), kaldi::TestCompactLatticeTableCross(), TestConvert2(), kaldi::TestLatticeTableCross(), kaldi::TestWordAlignedLattice(), and kaldi::TestWordAlignLatticeLexicon().

                 {
  typedef ArcTpl<Weight> Arc;
  typedef typename Arc::StateId StateId;
  typedef CompactLatticeWeightTpl<Weight, Int> CompactWeight;
  typedef ArcTpl<CompactWeight> CompactArc;

  VectorFst<ArcTpl<Weight> > ffst;
  std::vector<std::vector<Int> > labels;
  if (invert) // normal case: want the ilabels as sequences on the arcs of
    Factor(ifst, &ffst, &labels);  // the output... Factor makes seqs of
                                   // ilabels.
  else {
    VectorFst<ArcTpl<Weight> > invfst(ifst);
    Invert(&invfst);
    Factor(invfst, &ffst,  &labels);
  }

  TopSort(&ffst); // Put the states in ffst in topological order, which is
  // easier on the eye when reading the text-form lattices and corresponds to
  // what we get when we generate the lattices in the decoder.

  ofst->DeleteStates();

  // The states will be numbered exactly the same as the original FST.
  // Add the states to the new FST.
  StateId num_states = ffst.NumStates();
  for (StateId s = 0; s < num_states; s++) {
    StateId news = ofst->AddState();
    assert(news == s);
  }
  ofst->SetStart(ffst.Start());
  for (StateId s = 0; s < num_states; s++) {
    Weight final_weight = ffst.Final(s);
    if (final_weight != Weight::Zero()) {
      CompactWeight final_compact_weight(final_weight, std::vector<Int>());
      ofst->SetFinal(s, final_compact_weight);
    }
    for (ArcIterator<ExpandedFst<Arc> > iter(ffst, s);
         !iter.Done();
         iter.Next()) {
      const Arc &arc = iter.Value();
      KALDI_PARANOID_ASSERT(arc.weight != Weight::Zero());
      // note: zero-weight arcs not allowed anyway so weight should not be zero,
      // but no harm in checking.
      CompactArc compact_arc(arc.olabel, arc.olabel,
                             CompactWeight(arc.weight, labels[arc.ilabel]),
                             arc.nextstate);
      ofst->AddArc(s, compact_arc);
    }
  }
}

ConvertLattice() [2/7]

void fst::ConvertLattice	(	const ExpandedFst< ArcTpl< LatticeWeightTpl< float > > > &	ifst,
		MutableFst< ArcTpl< CompactLatticeWeightTpl< LatticeWeightTpl< double >, Int > > > *	ofst
	)

Definition at line 87 of file lattice-utils.h.

References ConvertLattice().

                                                                                                        {
  VectorFst<ArcTpl<CompactLatticeWeightTpl<LatticeWeightTpl<float>, Int> > > fst;
  ConvertLattice(ifst, &fst);
  ConvertLattice(fst, ofst);
}

ConvertLattice() [3/7]

void ConvertLattice	(	const ExpandedFst< ArcTpl< CompactLatticeWeightTpl< Weight, Int > > > &	ifst,
		MutableFst< ArcTpl< Weight > > *	ofst,
		bool	invert = true
	)

Convert lattice CompactLattice format to Lattice.

This is a bit like converting from the Gallic semiring. As for any CompactLattice, "ifst" must be an acceptor (i.e., ilabels and olabels should be identical). If invert=false, the labels on "ifst" become the ilabels on "ofst" and the strings in the weights of "ifst" becomes the olabels. If invert=true [default], this is reversed (useful for speech recognition lattices; our standard non-compact format has the words on the output side to match HCLG).

Definition at line 89 of file lattice-utils-inl.h.

References rnnlm::n, and kaldi::swap().

                 {
  typedef ArcTpl<Weight> Arc;
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Label Label;
  typedef CompactLatticeWeightTpl<Weight, Int> CompactWeight;
  typedef ArcTpl<CompactWeight> CompactArc;
  ofst->DeleteStates();
  // make the states in the new FST have the same numbers as
  // the original ones, and add chains of states as necessary
  // to encode the string-valued weights.
  StateId num_states = ifst.NumStates();
  for (StateId s = 0; s < num_states; s++) {
    StateId news = ofst->AddState();
    assert(news == s);
  }
  ofst->SetStart(ifst.Start());
  for (StateId s = 0; s < num_states; s++) {
    CompactWeight final_weight = ifst.Final(s);
    if (final_weight != CompactWeight::Zero()) {
      StateId cur_state = s;
      size_t string_length = final_weight.String().size();
      for (size_t n = 0; n < string_length; n++) {
        StateId next_state = ofst->AddState();
        Label ilabel = 0;
        Arc arc(ilabel, final_weight.String()[n],
                (n == 0 ? final_weight.Weight() : Weight::One()),
                next_state);
        if (invert) std::swap(arc.ilabel, arc.olabel);
        ofst->AddArc(cur_state, arc);
        cur_state = next_state;
      }
      ofst->SetFinal(cur_state,
                     string_length > 0 ? Weight::One() : final_weight.Weight());
    }
    for (ArcIterator<ExpandedFst<CompactArc> > iter(ifst, s);
         !iter.Done();
         iter.Next()) {
      const CompactArc &arc = iter.Value();
      size_t string_length = arc.weight.String().size();
      StateId cur_state = s;
      // for all but the last element in the string--
      // add a temporary state.
      for (size_t n = 0 ; n+1 < string_length; n++) {
        StateId next_state = ofst->AddState();
        Label ilabel = (n == 0 ? arc.ilabel : 0),
            olabel = static_cast<Label>(arc.weight.String()[n]);
        Weight weight = (n == 0 ? arc.weight.Weight() : Weight::One());
        Arc new_arc(ilabel, olabel, weight, next_state);
        if (invert) std::swap(new_arc.ilabel, new_arc.olabel);
        ofst->AddArc(cur_state, new_arc);
        cur_state = next_state;
      }
      Label ilabel = (string_length <= 1 ? arc.ilabel : 0),
          olabel = (string_length > 0 ? arc.weight.String()[string_length-1] : 0);
      Weight weight = (string_length <= 1 ? arc.weight.Weight() : Weight::One());
      Arc new_arc(ilabel, olabel, weight, arc.nextstate);
      if (invert) std::swap(new_arc.ilabel, new_arc.olabel);
      ofst->AddArc(cur_state, new_arc);
    }
  }
}

ConvertLattice() [4/7]

void fst::ConvertLattice	(	const ExpandedFst< ArcTpl< LatticeWeightTpl< double > > > &	ifst,
		MutableFst< ArcTpl< CompactLatticeWeightTpl< LatticeWeightTpl< float >, Int > > > *	ofst
	)

Definition at line 96 of file lattice-utils.h.

References ConvertLattice().

                                                                                                       {
  VectorFst<ArcTpl<CompactLatticeWeightTpl<LatticeWeightTpl<double>, Int> > > fst;
  ConvertLattice(ifst, &fst);
  ConvertLattice(fst, ofst);
}

ConvertLattice() [5/7]

void fst::ConvertLattice	(	const ExpandedFst< ArcTpl< CompactLatticeWeightTpl< LatticeWeightTpl< double >, Int > > > &	ifst,
		MutableFst< ArcTpl< LatticeWeightTpl< float > > > *	ofst
	)

Converts CompactLattice with double to Lattice with float.

Definition at line 105 of file lattice-utils.h.

References ConvertLattice().

                                                                         {
  VectorFst<ArcTpl<CompactLatticeWeightTpl<LatticeWeightTpl<float>, Int> > > fst;
  ConvertLattice(ifst, &fst);
  ConvertLattice(fst, ofst);
}

ConvertLattice() [6/7]

void fst::ConvertLattice	(	const ExpandedFst< ArcTpl< CompactLatticeWeightTpl< LatticeWeightTpl< float >, Int > > > &	ifst,
		MutableFst< ArcTpl< LatticeWeightTpl< double > > > *	ofst
	)

Converts CompactLattice with float to Lattice with double.

Definition at line 114 of file lattice-utils.h.

References ConvertFstToLattice(), and ConvertLattice().

                                                                          {
  VectorFst<ArcTpl<CompactLatticeWeightTpl<LatticeWeightTpl<double>, Int> > > fst;
  ConvertLattice(ifst, &fst);
  ConvertLattice(fst, ofst);
}

ConvertLattice() [7/7]

void ConvertLattice	(	const ExpandedFst< ArcTpl< WeightIn > > &	ifst,
		MutableFst< ArcTpl< WeightOut > > *	ofst
	)

Convert between CompactLattices and Lattices of different floating point types...

this works between any pair of weight types for which ConvertLatticeWeight is defined (c.f. lattice-weight.h), and also includes conversion from LatticeWeight to TropicalWeight.

Definition at line 157 of file lattice-utils-inl.h.

References ConvertLatticeWeight(), and KALDI_PARANOID_ASSERT.

                                          {
  typedef ArcTpl<WeightIn> ArcIn;
  typedef ArcTpl<WeightOut> ArcOut;
  typedef typename ArcIn::StateId StateId;
  ofst->DeleteStates();
  // The states will be numbered exactly the same as the original FST.
  // Add the states to the new FST.
  StateId num_states = ifst.NumStates();
  for (StateId s = 0; s < num_states; s++) {
    StateId news = ofst->AddState();
    assert(news == s);
  }
  ofst->SetStart(ifst.Start());
  for (StateId s = 0; s < num_states; s++) {
    WeightIn final_iweight = ifst.Final(s);
    if (final_iweight != WeightIn::Zero()) {
      WeightOut final_oweight;
      ConvertLatticeWeight(final_iweight, &final_oweight);
      ofst->SetFinal(s, final_oweight);
    }
    for (ArcIterator<ExpandedFst<ArcIn> > iter(ifst, s);
         !iter.Done();
         iter.Next()) {
      ArcIn arc = iter.Value();
      KALDI_PARANOID_ASSERT(arc.weight != WeightIn::Zero());
      ArcOut oarc;
      ConvertLatticeWeight(arc.weight, &oarc.weight);
      oarc.ilabel = arc.ilabel;
      oarc.olabel = arc.olabel;
      oarc.nextstate = arc.nextstate;
      ofst->AddArc(s, oarc);
    }
  }
}

ConvertLatticeWeight() [1/3]

void fst::ConvertLatticeWeight ( const LatticeWeightTpl< Float1 > &  w_in, LatticeWeightTpl< Float2 > *  w_out  )

inline

Define some ConvertLatticeWeight functions that are used in various lattice conversions...

make them all templates, some with no arguments, since some must be templates.

Definition at line 819 of file lattice-weight.h.

References LatticeWeightTpl< FloatType >::SetValue1(), LatticeWeightTpl< FloatType >::SetValue2(), LatticeWeightTpl< FloatType >::Value1(), and LatticeWeightTpl< FloatType >::Value2().

Referenced by ConvertLattice().

                                     {
  w_out->SetValue1(w_in.Value1());
  w_out->SetValue2(w_in.Value2());
}

ConvertLatticeWeight() [2/3]

void fst::ConvertLatticeWeight ( const CompactLatticeWeightTpl< LatticeWeightTpl< Float1 >, Int > &  w_in, CompactLatticeWeightTpl< LatticeWeightTpl< Float2 >, Int > *  w_out  )

inline

Definition at line 827 of file lattice-weight.h.

                                                                   {
  LatticeWeightTpl<Float2> weight2(w_in.Weight().Value1(),
                                   w_in.Weight().Value2());
  w_out->SetWeight(weight2);
  w_out->SetString(w_in.String());
}

ConvertLatticeWeight() [3/3]

void fst::ConvertLatticeWeight ( const LatticeWeightTpl< Float1 > &  w_in, TropicalWeightTpl< Float2 > *  w_out  )

inline

Definition at line 838 of file lattice-weight.h.

References Times(), LatticeWeightTpl< FloatType >::Value1(), and LatticeWeightTpl< FloatType >::Value2().

                                      {
  TropicalWeightTpl<Float2> w1(w_in.Value1());
  TropicalWeightTpl<Float2> w2(w_in.Value2());
  *w_out = Times(w1, w2);
}

ConvertNbestToVector()

void ConvertNbestToVector	(	const Fst< Arc > &	fst,
		std::vector< VectorFst< Arc > > *	fsts_out
	)

This function converts an FST with a special structure, which is output by the OpenFst functions ShortestPath and RandGen, and converts them into a std::vector of separate FSTs.

This special structure is that the only state that has more than one (arcs-out or final-prob) is the start state. fsts_out is resized to the appropriate size.

Definition at line 221 of file fstext-utils-inl.h.

References KALDI_ASSERT.

Referenced by main(), MinimizeEncoded(), NbestAsFsts(), and kaldi::TestWordAlignLatticeLexicon().

                                                                {
  typedef typename Arc::Weight Weight;
  typedef typename Arc::StateId StateId;
  fsts_out->clear();
  StateId start_state = fst.Start();
  if (start_state == kNoStateId) return; // No output.
  size_t n_arcs = fst.NumArcs(start_state);
  bool start_is_final = (fst.Final(start_state) != Weight::Zero());
  fsts_out->reserve(n_arcs + (start_is_final ? 1 : 0));

  if (start_is_final) {
    fsts_out->resize(fsts_out->size() + 1);
    StateId start_state_out = fsts_out->back().AddState();
    fsts_out->back().SetFinal(start_state_out, fst.Final(start_state));
  }

  for (ArcIterator<Fst<Arc> > start_aiter(fst, start_state);
       !start_aiter.Done();
       start_aiter.Next()) {
    fsts_out->resize(fsts_out->size() + 1);
    VectorFst<Arc> &ofst = fsts_out->back();
    const Arc &first_arc = start_aiter.Value();
    StateId cur_state = start_state,
        cur_ostate = ofst.AddState();
    ofst.SetStart(cur_ostate);
    StateId next_ostate = ofst.AddState();
    ofst.AddArc(cur_ostate, Arc(first_arc.ilabel, first_arc.olabel,
                                first_arc.weight, next_ostate));
    cur_state = first_arc.nextstate;
    cur_ostate = next_ostate;
    while (1) {
      size_t this_n_arcs = fst.NumArcs(cur_state);
      KALDI_ASSERT(this_n_arcs <= 1); // or it violates our assumptions
                                      // about the input.
      if (this_n_arcs == 1) {
        KALDI_ASSERT(fst.Final(cur_state) == Weight::Zero());
        // or problem with ShortestPath.
        ArcIterator<Fst<Arc> > aiter(fst, cur_state);
        const Arc &arc = aiter.Value();
        next_ostate = ofst.AddState();
        ofst.AddArc(cur_ostate, Arc(arc.ilabel, arc.olabel,
                                    arc.weight, next_ostate));
        cur_state = arc.nextstate;
        cur_ostate = next_ostate;
      } else {
        KALDI_ASSERT(fst.Final(cur_state) != Weight::Zero());
        // or problem with ShortestPath.
        ofst.SetFinal(cur_ostate, fst.Final(cur_state));
        break;
      }
    }
  }
}

ConvertToCost() [1/3]

double fst::ConvertToCost ( const LatticeWeightTpl< Float > &  w )

inline

Definition at line 847 of file lattice-weight.h.

References LatticeWeightTpl< FloatType >::Value1(), and LatticeWeightTpl< FloatType >::Value2().

Referenced by LatticeIncrementalDeterminizer::AddArcToClat(), kaldi::CompactLatticeLimitDepth(), kaldi::CompactLatticeShortestPath(), PrunedCompactLatticeComposer::ComputeBackwardCosts(), LatticeDeterminizerPruned< Weight, IntType >::ComputeBackwardWeight(), PrunedCompactLatticeComposer::ComputeForwardCosts(), kaldi::ComputeLatticeAlphasAndBetas(), PrunedCompactLatticeComposer::ComputeLatticeStateInfo(), LatticeDeterminizerPruned< Weight, IntType >::InitialToStateId(), kaldi::LatticeForwardBackward(), kaldi::LatticeForwardBackwardMpeVariants(), main(), ArcPosteriorComputer::OutputPosteriors(), LatticeIncrementalDeterminizer::ProcessArcsFromChunkStartState(), LatticeDeterminizerPruned< Weight, IntType >::ProcessFinal(), PrunedCompactLatticeComposer::ProcessQueueElement(), PrunedCompactLatticeComposer::ProcessTransition(), LatticeDeterminizerPruned< Weight, IntType >::ProcessTransition(), LatticeDeterminizerPruned< Weight, IntType >::ProcessTransitions(), kaldi::PruneLattice(), and kaldi::SentenceLevelConfidence().

                                                              {
  return static_cast<double>(w.Value1()) + static_cast<double>(w.Value2());
}

ConvertToCost() [2/3]

double fst::ConvertToCost ( const CompactLatticeWeightTpl< LatticeWeightTpl< Float >, Int > &  w )

inline

Definition at line 852 of file lattice-weight.h.

                                                                                            {
  return static_cast<double>(w.Weight().Value1()) + static_cast<double>(w.Weight().Value2());
}

ConvertToCost() [3/3]

double fst::ConvertToCost ( const TropicalWeightTpl< Float > &  w )

inline

Definition at line 857 of file lattice-weight.h.

                                                               {
  return w.Value();
}

CopyToVectorFst()

void CopyToVectorFst	(	GrammarFst *	grammar_fst,
		VectorFst< StdArc > *	vector_fst
	)

This function copies a GrammarFst to a VectorFst (intended mostly for testing and comparison purposes).

GrammarFst doesn't actually inherit from class Fst, so we can't just construct an FST from the GrammarFst.

grammar_fst gets expanded by this call, and although we could make it a const reference (because the ArcIterator does actually use const_cast), we make it a non-const pointer to emphasize that this call does change grammar_fst.

Definition at line 988 of file grammar-fst.cc.

References ArcIterator< GrammarFst >::Done(), GrammarFst::Final(), GrammarFstArc::ilabel, ArcIterator< GrammarFst >::Next(), GrammarFstArc::nextstate, GrammarFstArc::olabel, GrammarFst::Start(), ArcIterator< GrammarFst >::Value(), and GrammarFstArc::weight.

Referenced by main().

                                                    {
  typedef GrammarFstArc::StateId GrammarStateId;  // int64
  typedef StdArc::StateId StdStateId;  // int
  typedef StdArc::Label Label;
  typedef StdArc::Weight Weight;

  std::vector<std::pair<GrammarStateId, StdStateId> > queue;
  std::unordered_map<GrammarStateId, StdStateId> state_map;

  vector_fst->DeleteStates();
  state_map[grammar_fst->Start()] = vector_fst->AddState();  // state 0.
  vector_fst->SetStart(0);

  queue.push_back(
      std::pair<GrammarStateId, StdStateId>(grammar_fst->Start(), 0));

  while (!queue.empty()) {
    std::pair<GrammarStateId, StdStateId> p = queue.back();
    queue.pop_back();
    GrammarStateId grammar_state = p.first;
    StdStateId std_state = p.second;
    vector_fst->SetFinal(std_state, grammar_fst->Final(grammar_state));
    ArcIterator<GrammarFst> aiter(*grammar_fst, grammar_state);
    for (; !aiter.Done(); aiter.Next()) {
      const GrammarFstArc &grammar_arc = aiter.Value();
      StdArc std_arc;
      std_arc.ilabel = grammar_arc.ilabel;
      std_arc.olabel = grammar_arc.olabel;
      std_arc.weight = grammar_arc.weight;
      GrammarStateId next_grammar_state = grammar_arc.nextstate;
      StdStateId next_std_state;
      std::unordered_map<GrammarStateId, StdStateId>::const_iterator
          state_iter = state_map.find(next_grammar_state);
      if (state_iter == state_map.end()) {
        next_std_state = vector_fst->AddState();
        state_map[next_grammar_state] = next_std_state;
        queue.push_back(std::pair<GrammarStateId, StdStateId>(
            next_grammar_state, next_std_state));
      } else {
        next_std_state = state_iter->second;
      }
      std_arc.nextstate = next_std_state;
      vector_fst->AddArc(std_state, std_arc);
    }
  }
}

CreateBackoffFst()

StdVectorFst* fst::CreateBackoffFst

(

)

Definition at line 64 of file deterministic-fst-test.cc.

Referenced by TestBackoffAndCache(), and TestCompose().

                                 {
  StdVectorFst *fst = new StdVectorFst();
  fst->AddState();   // state 0
  fst->SetStart(0);
  fst->AddArc(0, StdArc(10, 10, 0.0, 1));

  fst->AddState();    // state 1
  fst->AddArc(1, StdArc(12, 12, 0.0, 4));
  fst->AddArc(1, StdArc(0,0,  0.1,2));  // backoff from 1 to 2

  fst->AddState();    // state 2
  fst->AddArc(2, StdArc(13, 13, 0.2, 4));
  fst->AddArc(2, StdArc(0,0,  0.3,3));  // backoff from 2 to 3

  fst->AddState();     // state 3
  fst->AddArc(3, StdArc(14, 14, 0.4, 4));

  fst->AddState();    // state 4
  fst->AddArc(4, StdArc(15, 15, 0.5, 5));

  fst->AddState();     // state 5
  fst->SetFinal(5, 0.6);

  return fst;
}

CreateFactorFst()

void CreateFactorFst	(	const std::vector< std::vector< I > > &	sequences,
		MutableFst< Arc > *	fst
	)

The function CreateFactorFst will create an FST that expands out the "factors" that are the indices of the "sequences" array, into linear sequences of symbols.

There is a single start and end state (state 0), and for each nonzero index i into the array "sequences", there is an arc from state 0 that has output-label i, and enters a chain of states with output epsilons and input labels corresponding to the remaining elements of the sequences, terminating again in state 0. This FST is output-deterministic and sorted on olabel. Composing an FST on the left with the output of this function, should be the same as calling "ExpandInputSequences". Use TableCompose (see table-matcher.h) for efficiency.

Definition at line 250 of file factor-inl.h.

References rnnlm::i, and KALDI_ASSERT_IS_INTEGER_TYPE.

Referenced by Factor(), and TestFactor().

                                           {
  KALDI_ASSERT_IS_INTEGER_TYPE(I);
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Label Label;
  typedef typename Arc::Weight Weight;

  assert(fst != NULL);
  fst->DeleteStates();
  StateId loopstate = fst->AddState();
  assert(loopstate == 0);
  fst->SetStart(0);
  fst->SetFinal(0, Weight::One());
  if (sequences.size() != 0) assert(sequences[0].size() == 0);  // can't replace epsilon...

  for (Label olabel = 1; olabel < static_cast<Label>(sequences.size()); olabel++) {
    size_t len = sequences[olabel].size();
    if (len == 0) {
      Arc arc(0, olabel, Weight::One(), loopstate);
      fst->AddArc(loopstate, arc);
    } else {
      StateId curstate = loopstate;
      for (size_t i = 0; i < len; i++) {
        StateId nextstate = (i == len-1 ? loopstate : fst->AddState());
        Arc arc(sequences[olabel][i], (i == 0 ? olabel : 0), Weight::One(), nextstate);
        fst->AddArc(curstate, arc);
        curstate = nextstate;
      }
    }
  }
  fst->SetProperties(kOLabelSorted, kOLabelSorted);
}

CreateILabelInfoSymbolTable() [1/2]

SymbolTable* fst::CreateILabelInfoSymbolTable	(	const std::vector< std::vector< int32 > > &	ilabel_info,
		const SymbolTable &	phones_symtab,
		std::string	separator,
		std::string	disambig_prefix
	)

The following function is mainly of use for printing and debugging.

Definition at line 345 of file context-fst.cc.

References rnnlm::i, rnnlm::j, KALDI_ASSERT, and KALDI_ERR.

Referenced by main().

                                                                     {  // e.g. separator = "/", initial-disambig="#-1"
  KALDI_ASSERT(!info.empty() && info[0].empty());
  SymbolTable *ans = new SymbolTable("ilabel-info-symtab");
  int64 s = ans->AddSymbol(phones_symtab.Find(static_cast<int64>(0)));
  assert(s == 0);
  for (size_t i = 1; i < info.size(); i++) {
    if (info[i].size() == 0) {
      KALDI_ERR << "Invalid ilabel-info";
    }
    if (info[i].size() == 1 &&
       info[i][0] <= 0) {
      if (info[i][0] == 0) {  // special symbol at start that we want to call #-1.
        s = ans->AddSymbol(initial_disambig);
        if (s != i) {
          KALDI_ERR << "Disambig symbol " << initial_disambig
                    << " already in vocab";
        }
      } else {
        std::string disambig_sym = phones_symtab.Find(-info[i][0]);
        if (disambig_sym == "") {
          KALDI_ERR << "Disambig symbol " << -info[i][0]
                    << " not in phone symbol-table";
        }
        s = ans->AddSymbol(disambig_sym);
        if (s != i) {
          KALDI_ERR << "Disambig symbol " << disambig_sym
                    << " already in vocab";
        }
      }
    } else {
      // is a phone-context-window.
      std::string newsym;
      for (size_t j = 0; j < info[i].size(); j++) {
        std::string phonesym = phones_symtab.Find(info[i][j]);
        if (phonesym == "") {
          KALDI_ERR << "Symbol " << info[i][j]
                    << " not in phone symbol-table";
        }
        if (j != 0) newsym += separator;
        newsym += phonesym;
      }
      int64 s = ans->AddSymbol(newsym);
      if (s != static_cast<int64>(i)) {
        KALDI_ERR << "Some problem with duplicate symbols";
      }
    }
  }
  return ans;
}

CreateILabelInfoSymbolTable() [2/2]

SymbolTable* fst::CreateILabelInfoSymbolTable	(	const vector< vector< int32 > > &	info,
		const SymbolTable &	phones_symtab,
		std::string	separator,
		std::string	initial_disambig
	)

The following function is mainly of use for printing and debugging.

Definition at line 345 of file context-fst.cc.

References rnnlm::i, rnnlm::j, KALDI_ASSERT, and KALDI_ERR.

Referenced by main().

                                                                     {  // e.g. separator = "/", initial-disambig="#-1"
  KALDI_ASSERT(!info.empty() && info[0].empty());
  SymbolTable *ans = new SymbolTable("ilabel-info-symtab");
  int64 s = ans->AddSymbol(phones_symtab.Find(static_cast<int64>(0)));
  assert(s == 0);
  for (size_t i = 1; i < info.size(); i++) {
    if (info[i].size() == 0) {
      KALDI_ERR << "Invalid ilabel-info";
    }
    if (info[i].size() == 1 &&
       info[i][0] <= 0) {
      if (info[i][0] == 0) {  // special symbol at start that we want to call #-1.
        s = ans->AddSymbol(initial_disambig);
        if (s != i) {
          KALDI_ERR << "Disambig symbol " << initial_disambig
                    << " already in vocab";
        }
      } else {
        std::string disambig_sym = phones_symtab.Find(-info[i][0]);
        if (disambig_sym == "") {
          KALDI_ERR << "Disambig symbol " << -info[i][0]
                    << " not in phone symbol-table";
        }
        s = ans->AddSymbol(disambig_sym);
        if (s != i) {
          KALDI_ERR << "Disambig symbol " << disambig_sym
                    << " already in vocab";
        }
      }
    } else {
      // is a phone-context-window.
      std::string newsym;
      for (size_t j = 0; j < info[i].size(); j++) {
        std::string phonesym = phones_symtab.Find(info[i][j]);
        if (phonesym == "") {
          KALDI_ERR << "Symbol " << info[i][j]
                    << " not in phone symbol-table";
        }
        if (j != 0) newsym += separator;
        newsym += phonesym;
      }
      int64 s = ans->AddSymbol(newsym);
      if (s != static_cast<int64>(i)) {
        KALDI_ERR << "Some problem with duplicate symbols";
      }
    }
  }
  return ans;
}

CreateMapFst()

void CreateMapFst	(	const std::vector< I > &	symbol_map,
		MutableFst< Arc > *	fst
	)

CreateMapFst will create an FST representing this symbol_map.

The FST has a single loop state with single-arc loops with isymbol = symbol_map[i], osymbol = i. The resulting FST applies this map to the input symbols of something we compose with it on the right. Must have symbol_map[0] == 0.

Definition at line 285 of file factor-inl.h.

References KALDI_ASSERT_IS_INTEGER_TYPE.

Referenced by main().

                                        {
  KALDI_ASSERT_IS_INTEGER_TYPE(I);
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Label Label;
  typedef typename Arc::Weight Weight;

  assert(fst != NULL);
  fst->DeleteStates();
  StateId loopstate = fst->AddState();
  assert(loopstate == 0);
  fst->SetStart(0);
  fst->SetFinal(0, Weight::One());
  assert(symbol_map.empty() || symbol_map[0] == 0);  // FST cannot map epsilon to something else.
  for (Label olabel = 1; olabel < static_cast<Label>(symbol_map.size()); olabel++) {
    Arc arc(symbol_map[olabel], olabel, Weight::One(), loopstate);
    fst->AddArc(loopstate, arc);
  }
}

CreateNewSymbols()

void CreateNewSymbols	(	SymbolTable *	input_sym_table,
		int	nSym,
		std::string	prefix,
		std::vector< Label > *	symsOut
	)

Definition at line 581 of file pre-determinize-inl.h.

References rnnlm::i.

Referenced by TestAddSelfLoops().

                                                                                         {
  // Creates nSym new symbols named (prefix)0, (prefix)1 and so on.
  // Crashes if it cannot create them because one or more of them were in the symbol
  // table already.
  assert(symsOut && symsOut->size() == 0);
  for (int i = 0;i < nSym;i++) {
    std::stringstream ss; ss << prefix << i;
    std::string str = ss.str();
    if (input_sym_table->Find(str) != -1) {  // should not be present.
    }
    assert(symsOut);
    symsOut->push_back( (Label) input_sym_table->AddSymbol(str));
  }
}

CreateResultFst()

StdVectorFst* fst::CreateResultFst

(

)

Definition at line 91 of file deterministic-fst-test.cc.

Referenced by TestBackoffAndCache(), and TestCompose().

                                {
  StdVectorFst *fst = new StdVectorFst();
  fst->AddState();   // state 0
  fst->SetStart(0);
  fst->AddArc(0, StdArc(10, 10, 0.0, 1));

  fst->AddState();    // state 1
  fst->AddArc(1, StdArc(12, 12, 0.0, 4));
  fst->AddArc(1, StdArc(13,13,0.3,4));  // went through 1 backoff
  fst->AddArc(1, StdArc(14,14,0.8,4));  // went through 2 backoffs

  fst->AddState();    // state 2
  fst->AddState();    // state 3

  fst->AddState();    // state 4
  fst->AddArc(4, StdArc(15, 15, 0.5, 5));

  fst->AddState();     // state 5
  fst->SetFinal(5, 0.6);

  return fst;
}

CreateSuperFinal()

Arc::StateId CreateSuperFinal

(

MutableFst< Arc > *

fst

)

Definition at line 687 of file pre-determinize-inl.h.

Referenced by LatticeLexiconWordAligner::LatticeLexiconWordAligner(), LatticePhoneAligner::LatticePhoneAligner(), LatticeWordAligner::LatticeWordAligner(), main(), PreDeterminize(), and MinimumBayesRisk::PrepareLatticeAndInitStats().

                                                           {
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Weight Weight;
  assert(fst != NULL);
  StateId num_states = fst->NumStates();
  StateId num_final = 0;
  std::vector<StateId> final_states;
  for (StateId s = 0; s < num_states; s++) {
    if (fst->Final(s) != Weight::Zero()) {
      num_final++;
      final_states.push_back(s);
    }
  }
  if (final_states.size() == 1) {
    if (fst->Final(final_states[0]) == Weight::One()) {
      ArcIterator<MutableFst<Arc> > iter(*fst, final_states[0]);
      if (iter.Done()) {
        // We already have a final state w/ no transitions out and unit weight.
        // So we're done.
        return final_states[0];
      }
    }
  }

  StateId final_state = fst->AddState();
  fst->SetFinal(final_state, Weight::One());
  for (size_t idx = 0; idx < final_states.size(); idx++) {
    StateId s = final_states[idx];
    Weight weight = fst->Final(s);
    fst->SetFinal(s, Weight::Zero());
    Arc arc;
    arc.ilabel = 0;
    arc.olabel = 0;
    arc.nextstate = final_state;
    arc.weight = weight;
    fst->AddArc(s, arc);
  }
  return final_state;
}

DefaultLatticeScale()

std::vector<std::vector<double> > fst::DefaultLatticeScale ( )

inline

Returns a default 2x2 matrix scaling factor for LatticeWeight.

Definition at line 130 of file lattice-utils.h.

Referenced by ScaleLattice(), and TestScalePair().

                                                           {
  std::vector<std::vector<double> > ans(2);
  ans[0].resize(2, 0.0);
  ans[1].resize(2, 0.0);
  ans[0][0] = ans[1][1] = 1.0;
  return ans;
}

DeleteISymbols()

int64 DeleteISymbols	(	MutableFst< Arc > *	fst,
		std::vector< typename Arc::Label >	isyms
	)

Definition at line 651 of file pre-determinize-inl.h.

References rnnlm::i.

Referenced by TestDeterminize(), TestMinimize(), and TestPreDeterminize().

                                                                               {

  // We could do this using the Mapper concept, but this is much easier to understand.

  typedef typename Arc::Label Label;
  typedef typename Arc::StateId StateId;

  int64 num_deleted = 0;

  if (isyms.size() == 0) return 0;
  Label  isyms_min = *std::min_element(isyms.begin(), isyms.end()),
         isyms_max = *std::max_element(isyms.begin(), isyms.end());
  bool isyms_consecutive = (isyms_max+1-isyms_min == static_cast<Label>(isyms.size()));
  std::set<Label> isyms_set;
  if (!isyms_consecutive)
    for (size_t i = 0;i < isyms.size();i++)
      isyms_set.insert(isyms[i]);

  for (StateIterator<MutableFst<Arc> > siter(*fst); ! siter.Done(); siter.Next()) {
    StateId state = siter.Value();
    for (MutableArcIterator<MutableFst<Arc> > aiter(fst, state); ! aiter.Done(); aiter.Next()) {
      const Arc &arc = aiter.Value();
      if (arc.ilabel >= isyms_min && arc.ilabel <= isyms_max) {
        if (isyms_consecutive || isyms_set.count(arc.ilabel) != 0) {
          num_deleted++;
          Arc mod_arc (arc);
          mod_arc.ilabel = 0;  // change label to epsilon.
          aiter.SetValue(mod_arc);
        }
      }
    }
  }
  return num_deleted;
}

DeleteTestFst()

void fst::DeleteTestFst

(

StdVectorFst *

fst

)

Definition at line 114 of file deterministic-fst-test.cc.

                                      {
  delete fst;
}

DeterminizeInLog()

void fst::DeterminizeInLog ( VectorFst< StdArc > *  fst )

inline

Definition at line 388 of file fstext-utils-inl.h.

Referenced by main().

                                              {
  // DeterminizeInLog determinizes 'fst' in the log semiring.

  ArcSort(fst, ILabelCompare<StdArc>());  // helps DeterminizeStar to be faster.
  VectorFst<LogArc> *fst_log = new VectorFst<LogArc>;  // Want to determinize in log semiring.
  Cast(*fst, fst_log);
  VectorFst<StdArc> tmp;
  *fst = tmp;  // make fst empty to free up memory. [actually may make no difference..]
  VectorFst<LogArc> *fst_det_log = new VectorFst<LogArc>;
  Determinize(*fst_log, fst_det_log);
  Cast(*fst_det_log, fst);
  delete fst_log;
  delete fst_det_log;
}

DeterminizeLatticeDeletePhones()

template void fst::DeterminizeLatticeDeletePhones	(	ArcTpl< kaldi::LatticeWeight >::Label	first_phone_label,
		MutableFst< ArcTpl< kaldi::LatticeWeight > > *	fst
	)

DeterminizeLatticePhonePruned< kaldi::LatticeWeight, kaldi::int32 >() [1/2]

template bool fst::DeterminizeLatticePhonePruned< kaldi::LatticeWeight, kaldi::int32 >	(	const kaldi::TransitionModel &	trans_model,
		const ExpandedFst< kaldi::LatticeArc > &	ifst,
		double	prune,
		MutableFst< kaldi::CompactLatticeArc > *	ofst,
		DeterminizeLatticePhonePrunedOptions	opts
	)

DeterminizeLatticePhonePruned< kaldi::LatticeWeight, kaldi::int32 >() [2/2]

template bool fst::DeterminizeLatticePhonePruned< kaldi::LatticeWeight, kaldi::int32 >	(	const kaldi::TransitionModel &	trans_model,
		MutableFst< kaldi::LatticeArc > *	ifst,
		double	prune,
		MutableFst< kaldi::CompactLatticeArc > *	ofst,
		DeterminizeLatticePhonePrunedOptions	opts
	)

DeterminizeLatticePhonePrunedFirstPass()

bool fst::DeterminizeLatticePhonePrunedFirstPass	(	const kaldi::TransitionModel &	trans_model,
		double	beam,
		MutableFst< ArcTpl< Weight > > *	fst,
		const DeterminizeLatticePrunedOptions &	opts
	)

This function does a first pass determinization with phone symbols inserted at phone boundary.

It uses a transition model to work out the transition-id to phone map. First, phones will be inserted into the word level lattice. Second, determinization will be applied on top of the phone + word lattice. Finally, the inserted phones will be removed, converting the lattice back to a word level lattice. The output lattice of this pass is not deterministic, since we remove the phone symbols as a last step. It is supposed to be followed by another pass of determinization at the word level. It could also be useful for some other applications such as fMLLR estimation, confidence estimation, discriminative training, etc.

Definition at line 1393 of file determinize-lattice-pruned.cc.

References DeterminizeLatticeDeletePhones(), and DeterminizeLatticeInsertPhones().

                                                 {
  // First, insert the phones.
  typename ArcTpl<Weight>::Label first_phone_label =
      DeterminizeLatticeInsertPhones(trans_model, fst);
  TopSort(fst);

  // Second, do determinization with phone inserted.
  bool ans = DeterminizeLatticePruned<Weight>(*fst, beam, fst, opts);

  // Finally, remove the inserted phones.
  DeterminizeLatticeDeletePhones(first_phone_label, fst);
  TopSort(fst);

  return ans;
}

DeterminizeLatticePruned< kaldi::LatticeWeight >() [1/2]

template bool fst::DeterminizeLatticePruned< kaldi::LatticeWeight >	(	const ExpandedFst< kaldi::LatticeArc > &	ifst,
		double	prune,
		MutableFst< kaldi::CompactLatticeArc > *	ofst,
		DeterminizeLatticePrunedOptions	opts
	)

DeterminizeLatticePruned< kaldi::LatticeWeight >() [2/2]

template bool fst::DeterminizeLatticePruned< kaldi::LatticeWeight >	(	const ExpandedFst< kaldi::LatticeArc > &	ifst,
		double	prune,
		MutableFst< kaldi::LatticeArc > *	ofst,
		DeterminizeLatticePrunedOptions	opts
	)

DeterminizeStarInLog()

void DeterminizeStarInLog ( VectorFst< StdArc > *  fst, float  delta, bool *  debug_ptr, int  max_states  )

inline

Definition at line 371 of file fstext-utils-inl.h.

References DeterminizeStar().

Referenced by TrainingGraphCompiler::CompileGraph(), TrainingGraphCompiler::CompileGraphs(), and main().

                                                                                                {
  // DeterminizeStarInLog determinizes 'fst' in the log semiring, using
  // the DeterminizeStar algorithm (which also removes epsilons).

  ArcSort(fst, ILabelCompare<StdArc>());  // helps DeterminizeStar to be faster.
  VectorFst<LogArc> *fst_log = new VectorFst<LogArc>;  // Want to determinize in log semiring.
  Cast(*fst, fst_log);
  VectorFst<StdArc> tmp;
  *fst = tmp;  // make fst empty to free up memory. [actually may make no difference..]
  VectorFst<LogArc> *fst_det_log = new VectorFst<LogArc>;
  DeterminizeStar(*fst_log, fst_det_log, delta, debug_ptr, max_states);
  Cast(*fst_det_log, fst);
  delete fst_log;
  delete fst_det_log;
}

Divide() [1/5]

ArcticWeightTpl<T> fst::Divide ( const ArcticWeightTpl< T > &  w1, const ArcticWeightTpl< T > &  w2, DivideType  typ = DIVIDE_ANY  )

inline

Definition at line 125 of file arctic-weight.h.

                                                                {
  T f1 = w1.Value(), f2 = w2.Value();
  if (f2 == -std::numeric_limits<T>::infinity())
    return std::numeric_limits<T>::quiet_NaN();
  else if (f1 == -std::numeric_limits<T>::infinity())
    return -std::numeric_limits<T>::infinity();
  else
    return ArcticWeightTpl<T>(f1 - f2);
}

Divide() [2/5]

ArcticWeightTpl<float> fst::Divide ( const ArcticWeightTpl< float > &  w1, const ArcticWeightTpl< float > &  w2, DivideType  typ = DIVIDE_ANY  )

inline

Definition at line 137 of file arctic-weight.h.

                                                                    {
  return Divide<float>(w1, w2, typ);
}

Divide() [3/5]

ArcticWeightTpl<double> fst::Divide ( const ArcticWeightTpl< double > &  w1, const ArcticWeightTpl< double > &  w2, DivideType  typ = DIVIDE_ANY  )

inline

Definition at line 143 of file arctic-weight.h.

                                                                     {
  return Divide<double>(w1, w2, typ);
}

Divide() [4/5]

LatticeWeightTpl<FloatType> fst::Divide ( const LatticeWeightTpl< FloatType > &  w1, const LatticeWeightTpl< FloatType > &  w2, DivideType  typ = DIVIDE_ANY  )

inline

Definition at line 370 of file lattice-weight.h.

References KALDI_WARN, LatticeWeightTpl< FloatType >::Value1(), LatticeWeightTpl< FloatType >::Value2(), and LatticeWeightTpl< FloatType >::Zero().

Referenced by CompactLatticeWeightTest(), Divide(), LatticeWeightTest(), LatticeDeterminizerPruned< Weight, IntType >::NormalizeSubset(), LatticeDeterminizer< Weight, IntType >::NormalizeSubset(), DeterminizerStar< F >::ProcessTransition(), PushCompactLatticeWeights(), RemoveEpsLocalClass< Arc, ReweightPlus >::RemoveEpsPattern1(), RemoveEpsLocalClass< Arc, ReweightPlus >::Reweight(), and TestRemoveEpsLocalSpecial().

                                                                       {
  typedef FloatType T;
  T a = w1.Value1() - w2.Value1(), b = w1.Value2() - w2.Value2();
  if (a != a || b != b || a == -std::numeric_limits<T>::infinity()
     || b == -std::numeric_limits<T>::infinity()) {
    KALDI_WARN << "LatticeWeightTpl::Divide, NaN or invalid number produced. "
               << "[dividing by zero?]  Returning zero";
    return LatticeWeightTpl<T>::Zero();
  }
  if (a == std::numeric_limits<T>::infinity() ||
     b == std::numeric_limits<T>::infinity())
    return LatticeWeightTpl<T>::Zero(); // not a valid number if only one is infinite.
  return LatticeWeightTpl<T>(a, b);
}

Divide() [5/5]

CompactLatticeWeightTpl<WeightType, IntType> fst::Divide ( const CompactLatticeWeightTpl< WeightType, IntType > &  w1, const CompactLatticeWeightTpl< WeightType, IntType > &  w2, DivideType  div = DIVIDE_ANY  )

inline

Definition at line 689 of file lattice-weight.h.

References Divide(), KALDI_ERR, CompactLatticeWeightTpl< WeightType, IntType >::String(), CompactLatticeWeightTpl< WeightType, IntType >::Weight(), and CompactLatticeWeightTpl< WeightType, IntType >::Zero().

                                                                                       {
  if (w1.Weight() == WeightType::Zero()) {
    if (w2.Weight() != WeightType::Zero()) {
      return CompactLatticeWeightTpl<WeightType, IntType>::Zero();
    } else {
      KALDI_ERR << "Division by zero [0/0]";
    }
  } else if (w2.Weight() == WeightType::Zero()) {
    KALDI_ERR << "Error: division by zero";
  }
  WeightType w = Divide(w1.Weight(), w2.Weight());

  const std::vector<IntType> v1 = w1.String(), v2 = w2.String();
  if (v2.size() > v1.size()) {
    KALDI_ERR << "Cannot divide, length mismatch";
  }
  typename std::vector<IntType>::const_iterator v1b = v1.begin(),
      v1e = v1.end(), v2b = v2.begin(), v2e = v2.end();
  if (div == DIVIDE_LEFT) {
    if (!std::equal(v2b, v2e, v1b)) { // v2 must be identical to first part of v1.
      KALDI_ERR << "Cannot divide, data mismatch";
    }
    return CompactLatticeWeightTpl<WeightType, IntType>(
        w, std::vector<IntType>(v1b+(v2e-v2b), v1e)); // return last part of v1.
  } else if (div == DIVIDE_RIGHT) {
    if (!std::equal(v2b, v2e, v1e-(v2e-v2b))) { // v2 must be identical to last part of v1.
      KALDI_ERR << "Cannot divide, data mismatch";
    }
    return CompactLatticeWeightTpl<WeightType, IntType>(
        w, std::vector<IntType>(v1b, v1e-(v2e-v2b))); // return first part of v1.

  } else {
    KALDI_ERR << "Cannot divide CompactLatticeWeightTpl with DIVIDE_ANY";
  }
  return CompactLatticeWeightTpl<WeightType,IntType>::Zero(); // keep compiler happy.
}

EnsureEpsilonProperty()

void EnsureEpsilonProperty

(

VectorFst< Arc > *

fst

)

This function modifies the fst (while maintaining equivalence) in such a way that, after the modification, all states of the FST which have epsilon-arcs entering them, have no non-epsilon arcs entering them, and all states which have epsilon-arcs leaving them, have no non-epsilon arcs leaving them.

It does this by creating extra states and adding extra epsilon transitions. An epsilon arc is defined as an arc where both the ilabel and the olabel are epsilons. This function may fail with KALDI_ASSERT for certain cyclic FSTs, but is safe in the acyclic case.

new_state_vec is for those states that have both epsilon and non-epsilon arcs entering. For these states, we'll create a new state for the non-epsilon arcs to enter and put it in this array, and we'll put an epsilon transition from the new state to the old state.

First modify arcs to point to states in new_state_vec when necessary.

Now handle the situation where states have both epsilon and non-epsilon arcs leaving.

Definition at line 49 of file epsilon-property-inl.h.

References ComputeStateInfo(), kStateHasEpsilonArcsEntering, kStateHasEpsilonArcsLeaving, kStateHasNonEpsilonArcsEntering, and kStateHasNonEpsilonArcsLeaving.

Referenced by main(), and TestEnsureEpsilonProperty().

                                                {

  typedef typename Arc::StateId StateId;
  typedef typename Arc::Weight Weight;
  typedef VectorFst<Arc> Fst;
  std::vector<char> epsilon_info;
  ComputeStateInfo(*fst, &epsilon_info);


  StateId num_states_old = fst->NumStates();
  StateId non_coaccessible_state = fst->AddState();

  std::vector<StateId> new_state_vec(num_states_old, kNoStateId);
  for (StateId s = 0; s < num_states_old; s++) {
    if ((epsilon_info[s] & kStateHasEpsilonArcsEntering) != 0 &&
        (epsilon_info[s] & kStateHasNonEpsilonArcsEntering) != 0) {
      assert(s != fst->Start()); // a type of cyclic FST we can't handle
                                 // easily.
      StateId new_state = fst->AddState();
      new_state_vec[s] = new_state;
      fst->AddArc(new_state, Arc(0, 0, Weight::One(), s));
    }
  }

  for (StateId s = 0; s < num_states_old; s++) {
    for (MutableArcIterator<Fst> aiter(fst, s);
         !aiter.Done(); aiter.Next()) {
      Arc arc = aiter.Value();
      if (arc.ilabel != 0 || arc.olabel != 0) { // non-epsilon arc
        StateId replacement_state;
        if (arc.nextstate >= 0 && arc.nextstate < num_states_old &&
            (replacement_state = new_state_vec[arc.nextstate]) !=
             kNoStateId) {
          arc.nextstate = replacement_state;
          aiter.SetValue(arc);
        }
      }
    }
  }

  for (StateId s = 0; s < num_states_old; s++) {
    if ((epsilon_info[s] & kStateHasEpsilonArcsLeaving) != 0 &&
        (epsilon_info[s] & kStateHasNonEpsilonArcsLeaving) != 0) {
      // state has non-epsilon and epsilon arcs leaving.
      // create a new state and move the non-epsilon arcs to leave
      // from there instead.
      StateId new_state = fst->AddState();
      for (MutableArcIterator<Fst> aiter(fst, s); !aiter.Done();
           aiter.Next()) {
        Arc arc = aiter.Value();
        if (arc.ilabel != 0 || arc.olabel != 0) { // non-epsilon arc.
          assert(arc.nextstate != s); // we don't handle cyclic FSTs.
          // move this arc to leave from the new state:
          fst->AddArc(new_state, arc); 
          arc.nextstate = non_coaccessible_state;
          aiter.SetValue(arc); // invalidate the arc, Connect() will remove it.
        }
      }
      // Create an epsilon arc to the new state.
      fst->AddArc(s, Arc(0, 0, Weight::One(), new_state));
    }
  }
  Connect(fst); // Removes arcs to the non-coaccessible state.
}

EqualAlign()

bool EqualAlign	(	const Fst< Arc > &	ifst,
		typename Arc::StateId	length,
		int	rand_seed,
		MutableFst< Arc > *	ofst,
		int	num_retries = 10
	)

EqualAlign is similar to RandGen, but it generates a sequence with exactly "length" input symbols.

It returns true on success, false on failure (failure is partly random but should never happen in practice for normal speech models.) It generates a random path through the input FST, finds out which subset of the states it visits along the way have self-loops with inupt symbols on them, and outputs a path with exactly enough self-loops to have the requested number of input symbols. Note that EqualAlign does not use the probabilities on the FST. It just uses equal probabilities in the first stage of selection (since the output will anyway not be a truly random sample from the FST). The input fst "ifst" must be connected or this may enter an infinite loop.

Definition at line 803 of file fstext-utils-inl.h.

References FindSelfLoopWithILabel(), rnnlm::i, rnnlm::j, KALDI_ASSERT, KALDI_WARN, and kaldi::RandInt().

Referenced by main(), MinimizeEncoded(), and TestEqualAlign().

                                 {
  srand(rand_seed);
  KALDI_ASSERT(ofst->NumStates() == 0);  // make sure ofst empty.
  // make sure all states can reach final-state (or this algorithm may enter
  // infinite loop.
  KALDI_ASSERT(ifst.Properties(kCoAccessible, true) == kCoAccessible);

  typedef typename Arc::StateId StateId;
  typedef typename Arc::Weight Weight;

  if (ifst.Start() == kNoStateId) {
    KALDI_WARN << "Empty input fst.";
    return false;
  }
  // First select path through ifst.
  std::vector<StateId> path;
  std::vector<size_t> arc_offsets;  // arc taken out of each state.
  std::vector<int> nof_ilabels;

  StateId num_ilabels = 0;
  int retry_no = 0;

  // Under normal circumstances, this will be one-pass-only process
  // Multiple tries might be needed in special cases, typically when
  // the number of frames is close to number of transitions from
  // the start node to the final node. It usually happens for really
  // short utterances
  do {
    num_ilabels = 0;
    arc_offsets.clear();
    path.clear();
    path.push_back(ifst.Start());

    while (1) {
      // Select either an arc or final-prob.
      StateId s = path.back();
      size_t num_arcs = ifst.NumArcs(s);
      size_t num_arcs_tot = num_arcs;
      if (ifst.Final(s) != Weight::Zero()) num_arcs_tot++;
      // kaldi::RandInt is a bit like Rand(), but gets around situations
      // where RAND_MAX is very small.
      // Change this to Rand() % num_arcs_tot if compile issues arise
      size_t arc_offset = static_cast<size_t>(kaldi::RandInt(0, num_arcs_tot-1));

      if (arc_offset < num_arcs) {  // an actual arc.
        ArcIterator<Fst<Arc> > aiter(ifst, s);
        aiter.Seek(arc_offset);
        const Arc &arc = aiter.Value();
        if (arc.nextstate == s) {
          continue;  // don't take this self-loop arc
        } else {
          arc_offsets.push_back(arc_offset);
          path.push_back(arc.nextstate);
          if (arc.ilabel != 0) num_ilabels++;
        }
      } else {
        break;  // Chose final-prob.
      }
    }

    nof_ilabels.push_back(num_ilabels);
  } while (( ++retry_no < num_retries) && (num_ilabels > length));

  if (num_ilabels > length) {
    std::stringstream ilabel_vec;
    std::copy(nof_ilabels.begin(), nof_ilabels.end(),
          std::ostream_iterator<int>(ilabel_vec, ","));
    std::string s = ilabel_vec.str();
    s.erase(s.end() - 1);
    KALDI_WARN << "EqualAlign: the randomly constructed paths lengths: " << s;
    KALDI_WARN << "EqualAlign: utterance has too few frames " << length
               << " to align.";
    return false;  // can't make it shorter by adding self-loops!.
  }

  StateId num_self_loops = 0;
  std::vector<ssize_t> self_loop_offsets(path.size());
  for (size_t i = 0; i < path.size(); i++)
    if ( (self_loop_offsets[i] = FindSelfLoopWithILabel(ifst, path[i]))
         != static_cast<ssize_t>(-1) )
      num_self_loops++;

  if (num_self_loops == 0
      && num_ilabels < length) {
    KALDI_WARN << "No self-loops on chosen path; cannot match length.";
    return false;  // no self-loops to make it longer.
  }

  StateId num_extra = length - num_ilabels;  // Number of self-loops we need.

  StateId min_num_loops = 0;
  if (num_extra != 0) min_num_loops = num_extra / num_self_loops;  // prevent div by zero.
  StateId num_with_one_more_loop = num_extra - (min_num_loops*num_self_loops);
  KALDI_ASSERT(num_with_one_more_loop < num_self_loops || num_self_loops == 0);

  ofst->AddState();
  ofst->SetStart(0);
  StateId cur_state = 0;
  StateId counter = 0;  // tell us when we should stop adding one more loop.
  for (size_t i = 0; i < path.size(); i++) {
    // First, add any self-loops that are necessary.
    StateId num_loops = 0;
    if (self_loop_offsets[i] != static_cast<ssize_t>(-1)) {
      num_loops = min_num_loops + (counter < num_with_one_more_loop ? 1 : 0);
      counter++;
    }
    for (StateId j = 0; j < num_loops; j++) {
      ArcIterator<Fst<Arc> > aiter(ifst, path[i]);
      aiter.Seek(self_loop_offsets[i]);
      Arc arc = aiter.Value();
      KALDI_ASSERT(arc.nextstate == path[i]
             && arc.ilabel != 0);  // make sure self-loop with ilabel.
      StateId next_state = ofst->AddState();
      ofst->AddArc(cur_state, Arc(arc.ilabel, arc.olabel, arc.weight, next_state));
      cur_state = next_state;
    }
    if (i+1 < path.size()) {  // add forward transition.
      ArcIterator<Fst<Arc> > aiter(ifst, path[i]);
      aiter.Seek(arc_offsets[i]);
      Arc arc = aiter.Value();
      KALDI_ASSERT(arc.nextstate == path[i+1]);
      StateId next_state = ofst->AddState();
      ofst->AddArc(cur_state, Arc(arc.ilabel, arc.olabel, arc.weight, next_state));
      cur_state = next_state;
    } else {  // add final-prob.
      Weight weight = ifst.Final(path[i]);
      KALDI_ASSERT(weight != Weight::Zero());
      ofst->SetFinal(cur_state, weight);
    }
  }
  return true;
}

ExpandInputSequences()

void ExpandInputSequences	(	const std::vector< std::vector< I > > &	sequences,
		MutableFst< Arc > *	fst
	)

ExpandInputSequences expands out the input symbols into sequences of input symbols.

It creates linear chains of states for each arc that had >1 augmented symbol on it. It also sets the input symbol table to NULL, since in case you did have a symbol table there it would no longer be valid. It leaves any weight and output symbols on the first arc of the chain.

Definition at line 163 of file factor-inl.h.

References KALDI_ASSERT_IS_INTEGER_TYPE, and rnnlm::n.

Referenced by TestFactor().

                                                {
  KALDI_ASSERT_IS_INTEGER_TYPE(I);
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Label Label;
  typedef typename Arc::Weight Weight;
  fst->SetInputSymbols(NULL);
  size_t size = sequences.size();
  if (sequences.size() > 0) assert(sequences[0].size() == 0);  // should be eps.
  StateId num_states_at_start = fst->NumStates();
  for (StateId s = 0; s < num_states_at_start; s++) {
    StateId num_arcs = fst->NumArcs(s);
    for (StateId aidx = 0; aidx < num_arcs; aidx++) {
      ArcIterator<MutableFst<Arc> > aiter(*fst, s);
      aiter.Seek(aidx);
      Arc arc = aiter.Value();

      Label ilabel = arc.ilabel;
      Label dest_state = arc.nextstate;
      if (ilabel != 0) {  // non-eps [nothing to do if eps]...
        assert(ilabel < static_cast<Label>(size));
        size_t len = sequences[ilabel].size();
        if (len <= 1) {
          if (len == 0) arc.ilabel = 0;
          else arc.ilabel = sequences[ilabel][0];
          MutableArcIterator<MutableFst<Arc> > mut_aiter(fst, s);
          mut_aiter.Seek(aidx);
          mut_aiter.SetValue(arc);
        } else {  // len>=2.  Must create new states...
          StateId curstate = -1;  // keep compiler happy: this value never used.
          for (size_t n = 0; n < len; n++) {  // adding/modifying "len" arcs.
            StateId nextstate;
            if (n < len-1) {
              nextstate = fst->AddState();
              assert(nextstate >= num_states_at_start);
            } else nextstate = dest_state;  // going back to original arc's
            // destination.
            if (n == 0) {
              arc.ilabel = sequences[ilabel][0];
              arc.nextstate = nextstate;
              MutableArcIterator<MutableFst<Arc> > mut_aiter(fst, s);
              mut_aiter.Seek(aidx);
              mut_aiter.SetValue(arc);
            } else {
              arc.ilabel = sequences[ilabel][n];
              arc.olabel = 0;
              arc.weight = Weight::One();
              arc.nextstate = nextstate;
              fst->AddArc(curstate, arc);
            }
            curstate = nextstate;
          }
        }
      }
    }
  }
}

Factor() [1/2]

void Factor	(	const Fst< Arc > &	fst,
		MutableFst< Arc > *	ofst,
		std::vector< std::vector< I > > *	symbols
	)

Factor identifies linear chains of states with an olabel (if any) only on the first arc of the chain, and possibly a sequence of ilabels; it outputs an FST with different symbols on the input that represent sequences of the original input symbols; it outputs the mapping from the new symbol to sequences of original symbols, as "symbols" [zero is reserved for epsilon].

As a side effect it also sorts the FST in depth-first order. Factor will usually do the best job when the olabels have been pushed to the left, i.e. if you make a call like

Push<Arc, REWEIGHT_TO_INITIAL>(fsta, &fstb, kPushLabels);

This is because it only creates a chain with olabels on the first arc of the chain (or a chain with no olabels). [it's possible to construct cases where pushing makes things worse, though]. After Factor, the composition of *ofst with the result of calling CreateFactorFst(*symbols) should be equivalent to fst. Alternatively, calling ExpandInputSequences with ofst and *symbols would produce something equivalent to fst.

Definition at line 69 of file factor-inl.h.

References GetStateProperties(), rnnlm::i, KALDI_ASSERT_IS_INTEGER_TYPE, kStateArcsIn, kStateArcsOut, kStateIlabelsOut, and Times().

Referenced by ConvertLattice(), Factor(), and TestFactor().

                                                      {
  KALDI_ASSERT_IS_INTEGER_TYPE(I);
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Label Label;
  typedef typename Arc::Weight Weight;
  assert(symbols_out != NULL);
  ofst->DeleteStates();
  if (fst.Start() < 0) return;  // empty FST.
  std::vector<StateId> order;
  DfsOrderVisitor<Arc> dfs_order_visitor(&order);
  DfsVisit(fst, &dfs_order_visitor);
  assert(order.size() > 0);
  StateId max_state = *(std::max_element(order.begin(), order.end()));
  std::vector<StatePropertiesType> state_properties;
  GetStateProperties(fst, max_state, &state_properties);

  std::vector<bool> remove(max_state+1);  // if true, will remove this state.

  // Now identify states that will be removed (made the middle of a chain).
  // The basic rule is that if the FstStateProperties equals
  // (kStateArcsIn|kStateArcsOut) or (kStateArcsIn|kStateArcsOut|kStateIlabelsOut),
  // then it is in the middle of a chain.  This eliminates state with
  // multiple input or output arcs, final states, and states with arcs out
  // that have olabels [we assume these are pushed to the left, so occur on the
  // 1st arc of a chain.

  for (StateId i = 0; i <= max_state; i++)
    remove[i] = (state_properties[i] == (kStateArcsIn|kStateArcsOut)
                 || state_properties[i] == (kStateArcsIn|kStateArcsOut|kStateIlabelsOut));
  std::vector<StateId> state_mapping(max_state+1, kNoStateId);

  typedef unordered_map<std::vector<I>, Label, kaldi::VectorHasher<I> > SymbolMapType;
  SymbolMapType symbol_mapping;
  Label symbol_counter = 0;
  {
    std::vector<I> eps;
    symbol_mapping[eps] = symbol_counter++;
  }
  std::vector<I> this_sym;  // a temporary used inside the loop.
  for (size_t i = 0; i < order.size(); i++) {
    StateId state = order[i];
    if (!remove[state]) {  // Process this state...
      StateId &new_state = state_mapping[state];
      if (new_state == kNoStateId) new_state = ofst->AddState();
      for (ArcIterator<Fst<Arc> > aiter(fst, state); !aiter.Done(); aiter.Next()) {
        Arc arc = aiter.Value();
        if (arc.ilabel == 0) this_sym.clear();
        else {
          this_sym.resize(1);
          this_sym[0] = arc.ilabel;
        }
        while (remove[arc.nextstate]) {
          ArcIterator<Fst<Arc> > aiter2(fst, arc.nextstate);
          assert(!aiter2.Done());
          const Arc &nextarc = aiter2.Value();
          arc.weight = Times(arc.weight, nextarc.weight);
          assert(nextarc.olabel == 0);
          if (nextarc.ilabel != 0) this_sym.push_back(nextarc.ilabel);
          assert(static_cast<Label>(static_cast<I>(nextarc.ilabel))
                 == nextarc.ilabel); // check within integer range.
          arc.nextstate = nextarc.nextstate;
        }
        StateId &new_nextstate = state_mapping[arc.nextstate];
        if (new_nextstate == kNoStateId) new_nextstate = ofst->AddState();
        arc.nextstate = new_nextstate;
        if (symbol_mapping.count(this_sym) != 0) arc.ilabel = symbol_mapping[this_sym];
        else arc.ilabel = symbol_mapping[this_sym] = symbol_counter++;
        ofst->AddArc(new_state, arc);
      }
      if (fst.Final(state) != Weight::Zero())
        ofst->SetFinal(new_state, fst.Final(state));
    }
  }
  ofst->SetStart(state_mapping[fst.Start()]);

  // Now output the symbol sequences.
  symbols_out->resize(symbol_counter);
  for (typename SymbolMapType::const_iterator iter = symbol_mapping.begin();
      iter != symbol_mapping.end(); ++iter) {
    (*symbols_out)[iter->second] = iter->first;
  }
}

Factor() [2/2]

void Factor	(	const Fst< Arc > &	fst,
		MutableFst< Arc > *	ofst1,
		MutableFst< Arc > *	ofst2
	)

This is a more conventional interface of Factor that outputs the result as two FSTs.

Definition at line 154 of file factor-inl.h.

References CreateFactorFst(), and Factor().

                                    {
  typedef typename Arc::Label Label;
  std::vector<std::vector<Label> > symbols;
  Factor(fst, ofst2, &symbols);
  CreateFactorFst(symbols, ofst1);
}

FileExists()

bool fst::FileExists

(

std::string

strFilename

)

Definition at line 31 of file deterministic-fst-test.cc.

                                       {
  struct stat stFileInfo;
  bool blnReturn;
  int intStat;

  // Attempt to get the file attributes
  intStat = stat(strFilename.c_str(), &stFileInfo);
  if (intStat == 0) {
    // We were able to get the file attributes
    // so the file obviously exists.
    blnReturn = true;
  } else {
    // We were not able to get the file attributes.
    // This may mean that we don't have permission to
    // access the folder which contains this file. If you
    // need to do that level of checking, lookup the
    // return values of stat which will give you
    // more details on why stat failed.
    blnReturn = false;
  }

  return blnReturn;
}

FindSelfLoopWithILabel()

ssize_t fst::FindSelfLoopWithILabel	(	const Fst< Arc > &	fst,
		typename Arc::StateId	s
	)

Definition at line 794 of file fstext-utils-inl.h.

Referenced by EqualAlign().

                                                                           {
  for (ArcIterator<Fst<Arc> > aiter(fst, s); !aiter.Done(); aiter.Next())
    if (aiter.Value().nextstate == s
       && aiter.Value().ilabel != 0) return static_cast<ssize_t>(aiter.Position());
  return static_cast<ssize_t>(-1);
}

FollowingInputSymbolsAreSame()

bool FollowingInputSymbolsAreSame	(	bool	end_is_epsilon,
		const Fst< Arc > &	fst
	)

Returns true if and only if the FST is such that the input symbols on arcs exiting any given state all have the same value.

If end_is_epsilon, treat end-state as an epsilon output arc [i.e. ensure end-states cannot have non-epsilon output transitions.]

Definition at line 497 of file fstext-utils-inl.h.

References FollowingInputSymbolsAreSameClass().

Referenced by MinimizeEncoded(), and TestMakeSymbolsSame().

                                                                            {
  IdentityFunction<typename Arc::Label> f;
  return FollowingInputSymbolsAreSameClass(end_is_epsilon, fst, f);
}

FollowingInputSymbolsAreSameClass()

bool FollowingInputSymbolsAreSameClass	(	bool	end_is_epsilon,
		const Fst< Arc > &	fst,
		const F &	f
	)

Definition at line 504 of file fstext-utils-inl.h.

Referenced by FollowingInputSymbolsAreSame(), MinimizeEncoded(), and TestMakeSymbolsSameClass().

                                                                                             {
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Weight Weight;
  typedef typename F::Result ClassType;
  const ClassType noClass = f(kNoLabel), epsClass = f(0);
  for (StateIterator<Fst<Arc> > siter(fst); !siter.Done(); siter.Next()) {
    StateId s = siter.Value();
    ClassType c = noClass;
    for (ArcIterator<Fst<Arc> > aiter(fst, s); !aiter.Done(); aiter.Next()) {
      const Arc &arc = aiter.Value();
      if (c == noClass)
        c = f(arc.ilabel);
      else
        if (c != f(arc.ilabel))
          return false;
    }
    if (end_is_epsilon && c != noClass &&
       c != epsClass && fst.Final(s) != Weight::Zero())
      return false;
  }
  return true;
}

GenAcceptorFromSequence()

static VectorFst<Arc>* fst::GenAcceptorFromSequence ( const vector< typename Arc::Label > &  symbols, float  cost  )

static

Definition at line 34 of file context-fst-test.cc.

References rnnlm::i, and kaldi::Rand().

                                                                                                     {
  typedef typename Arc::Weight Weight;
  typedef typename Arc::StateId StateId;

  vector<float> split_cost(symbols.size()+1, 0.0);  // for #-arcs + end-state.
  {  // compute split_cost.  it must sum to "cost".
    std::set<int32> indices;
    size_t num_indices = 1 + (kaldi::Rand() % split_cost.size());
    while (indices.size() < num_indices) indices.insert(kaldi::Rand() % split_cost.size());
    for (std::set<int32>::iterator iter = indices.begin(); iter != indices.end(); ++iter) {
      split_cost[*iter] = cost / num_indices;
    }
  }

  VectorFst<Arc> *fst = new VectorFst<Arc>();
  StateId cur_state = fst->AddState();
  fst->SetStart(cur_state);
  for (size_t i = 0; i < symbols.size(); i++) {
    StateId next_state = fst->AddState();
    Arc arc;
    arc.ilabel = symbols[i];
    arc.olabel = symbols[i];
    arc.nextstate = next_state;
    arc.weight = (Weight) split_cost[i];
    fst->AddArc(cur_state, arc);
    cur_state = next_state;

  }
  fst->SetFinal(cur_state, (Weight)split_cost[symbols.size()]);
  return fst;
}

GenRandPhoneSeq()

static VectorFst<Arc>* fst::GenRandPhoneSeq ( vector< typename Arc::Label > &  phone_syms, vector< typename Arc::Label > &  disambig_syms, typename Arc::Label  subsequential_symbol, int  num_subseq_syms, float  seq_prob, vector< typename Arc::Label > *  phoneseq_out  )

static

Definition at line 124 of file context-fst-test.cc.

References rnnlm::i, KALDI_ASSERT, kaldi::Rand(), and kaldi::RandUniform().

                                                                                {
  KALDI_ASSERT(phoneseq_out != NULL);
  typedef typename Arc::Label Label;
  // Generate an FST that is a random phone sequence, ending
  // with "num_subseq_syms" subsequential symbols.  It will
  // have disambiguation symbols randomly interspersed throughout.
  // The number of phones is random (possibly zero).
  size_t len = (kaldi::Rand() % 4) * (kaldi::Rand() % 3);  // up to 3*2=6 phones.
  float disambig_prob = 0.33;
  phoneseq_out->clear();
  vector<Label> syms;  // the phones
  for (size_t i = 0; i < len; i++) {
    while (kaldi::RandUniform() < disambig_prob) syms.push_back(disambig_syms[kaldi::Rand() % disambig_syms.size()]);
    Label phone_id = phone_syms[kaldi::Rand() % phone_syms.size()];
    phoneseq_out->push_back(phone_id);  // record in output the underlying phone sequence.
    syms.push_back(phone_id);
  }
  for (size_t i = 0; static_cast<int32>(i) < num_subseq_syms; i++) {
    while (kaldi::RandUniform() < disambig_prob) syms.push_back(disambig_syms[kaldi::Rand() % disambig_syms.size()]);
    syms.push_back(subsequential_symbol);
  }
  while (kaldi::RandUniform() < disambig_prob) syms.push_back(disambig_syms[kaldi::Rand() % disambig_syms.size()]);

  // OK, now have the symbols of the FST as a vector.
  return GenAcceptorFromSequence<Arc>(syms, seq_prob);
}

GetEncodingMultiple()

int32 fst::GetEncodingMultiple ( int32  nonterm_phones_offset )

inline

Definition at line 90 of file grammar-context-fst.h.

References ComposeContextLeftBiphone(), and kNontermMediumNumber.

Referenced by GrammarFst::DecodeSymbol(), GrammarFst::ExpandState(), GrammarFstPreparer::FixArcsToFinalStates(), GrammarFstPreparer::GetCategoryOfArc(), kaldi::GetHTransducer(), GrammarFstPreparer::IsEntryState(), GrammarFstPreparer::MaybeAddFinalProbToState(), and GrammarFstPreparer::NeedEpsilons().

                                                              {
  int32 medium_number = static_cast<int32>(kNontermMediumNumber);
  return medium_number *
      ((nonterm_phones_offset + medium_number) / medium_number);
}

GetInputSymbols()

void GetInputSymbols	(	const Fst< Arc > &	fst,
		bool	include_eps,
		std::vector< I > *	symbols
	)

GetInputSymbols gets the list of symbols on the input of fst (including epsilon, if include_eps == true), as a sorted, unique list.

Definition at line 97 of file fstext-utils-inl.h.

References kaldi::CopySetToVector(), KALDI_ASSERT, and KALDI_ASSERT_IS_INTEGER_TYPE.

Referenced by ComposeContext(), ComposeContextLeftBiphone(), kaldi::CreateEditDistance(), kaldi::GetRandomAlignmentForPhone(), and TestMakeLinearAcceptor().

                                            {
  KALDI_ASSERT_IS_INTEGER_TYPE(I);
  unordered_set<I> all_syms;
  for (StateIterator<Fst<Arc> > siter(fst); !siter.Done(); siter.Next()) {
    typename Arc::StateId s = siter.Value();
    for (ArcIterator<Fst<Arc> > aiter(fst, s); !aiter.Done();  aiter.Next()) {
      const Arc &arc = aiter.Value();
      all_syms.insert(arc.ilabel);
    }
  }
  // Remove epsilon, if instructed.
  if (!include_eps && all_syms.count(0) != 0)
    all_syms.erase(0);
  KALDI_ASSERT(symbols != NULL);
  kaldi::CopySetToVector(all_syms, symbols);
  std::sort(symbols->begin(), symbols->end());
}

GetLinearSymbolSequence()

bool GetLinearSymbolSequence	(	const Fst< Arc > &	fst,
		std::vector< I > *	isymbols_out,
		std::vector< I > *	osymbols_out,
		typename Arc::Weight *	tot_weight_out
	)

GetLinearSymbolSequence gets the symbol sequence from a linear FST.

If the FST is not just a linear sequence, it returns false. If it is a linear sequence (including the empty FST), it returns true. In this case it outputs the symbol sequences as "isymbols_out" and "osymbols_out" (removing epsilons), and the total weight as "tot_weight". The total weight will be Weight::Zero() if the FST is empty. If any of the output pointers are NULL, it does not create that output.

Definition at line 178 of file fstext-utils-inl.h.

References Times().

Referenced by kaldi::AlignUtteranceWrapper(), CheckPhones(), kaldi::DecodeUtterance(), DecodeUtterance(), kaldi::DecodeUtteranceLatticeFaster(), kaldi::DecodeUtteranceLatticeIncremental(), kaldi::DecodeUtteranceLatticeSimple(), OnlineFasterDecoder::EndOfUtterance(), kaldi::GetDiagnosticsAndPrintOutput(), kaldi::LatticeToString(), main(), kaldi::MaybeDoSanityCheck(), MinimizeEncoded(), MinimumBayesRisk::MinimumBayesRisk(), NnetBatchDecoder::ProcessOutputUtterance(), TestEqualAlign(), TestMakeLinearAcceptor(), and DecodeUtteranceLatticeFasterClass::~DecodeUtteranceLatticeFasterClass().

                                                                 {
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Weight Weight;

  Weight tot_weight = Weight::One();
  std::vector<I> ilabel_seq;
  std::vector<I> olabel_seq;

  StateId cur_state = fst.Start();
  if (cur_state == kNoStateId) {  // empty sequence.
    if (isymbols_out != NULL) isymbols_out->clear();
    if (osymbols_out != NULL) osymbols_out->clear();
    if (tot_weight_out != NULL) *tot_weight_out = Weight::Zero();
    return true;
  }
  while (1) {
    Weight w = fst.Final(cur_state);
    if (w != Weight::Zero()) {  // is final..
      tot_weight = Times(w, tot_weight);
      if (fst.NumArcs(cur_state) != 0) return false;
      if (isymbols_out != NULL) *isymbols_out = ilabel_seq;
      if (osymbols_out != NULL) *osymbols_out = olabel_seq;
      if (tot_weight_out != NULL) *tot_weight_out = tot_weight;
      return true;
    } else {
      if (fst.NumArcs(cur_state) != 1) return false;

      ArcIterator<Fst<Arc> > iter(fst, cur_state);  // get the only arc.
      const Arc &arc = iter.Value();
      tot_weight = Times(arc.weight, tot_weight);
      if (arc.ilabel != 0) ilabel_seq.push_back(arc.ilabel);
      if (arc.olabel != 0) olabel_seq.push_back(arc.olabel);
      cur_state = arc.nextstate;
    }
  }
}

GetOutputSymbols()

void GetOutputSymbols	(	const Fst< Arc > &	fst,
		bool	include_eps,
		std::vector< I > *	symbols
	)

GetOutputSymbols gets the list of symbols on the output of fst (including epsilon, if include_eps == true)

Definition at line 76 of file fstext-utils-inl.h.

References kaldi::CopySetToVector(), KALDI_ASSERT, and KALDI_ASSERT_IS_INTEGER_TYPE.

Referenced by kaldi::CreateEditDistance().

                                             {
  KALDI_ASSERT_IS_INTEGER_TYPE(I);
  std::set<I> all_syms;
  for (StateIterator<Fst<Arc> > siter(fst); !siter.Done(); siter.Next()) {
    typename Arc::StateId s = siter.Value();
    for (ArcIterator<Fst<Arc> > aiter(fst, s); !aiter.Done();  aiter.Next()) {
      const Arc &arc = aiter.Value();
      all_syms.insert(arc.olabel);
    }
  }

  // Remove epsilon, if instructed.
  if (!include_eps && !all_syms.empty() && *all_syms.begin() == 0)
    all_syms.erase(0);
  KALDI_ASSERT(symbols != NULL);
  kaldi::CopySetToVector(all_syms, symbols);
}

GetStateProperties()

void GetStateProperties	(	const Fst< Arc > &	fst,
		typename Arc::StateId	max_state,
		std::vector< StatePropertiesType > *	props
	)

This function works out various properties of the states in the FST, using the bit properties defined in StatePropertiesEnum.

Definition at line 37 of file factor-inl.h.

References kStateArcsIn, kStateArcsOut, kStateFinal, kStateIlabelsOut, kStateInitial, kStateMultipleArcsIn, kStateMultipleArcsOut, and kStateOlabelsOut.

Referenced by Factor().

                                                               {
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Weight Weight;
  assert(props != NULL);
  props->clear();
  if (fst.Start() < 0) return;  // Empty fst.
  props->resize(max_state+1, 0);
  assert(fst.Start() <= max_state);
  (*props)[fst.Start()] |= kStateInitial;
  for (StateId s = 0; s <= max_state; s++) {
    StatePropertiesType &s_info = (*props)[s];
    for (ArcIterator<Fst<Arc> > aiter(fst, s); !aiter.Done(); aiter.Next()) {
      const Arc &arc = aiter.Value();
      if (arc.ilabel != 0) s_info |= kStateIlabelsOut;
      if (arc.olabel != 0) s_info |= kStateOlabelsOut;
      StateId nexts = arc.nextstate;
      assert(nexts <= max_state);  // or input was invalid.
      StatePropertiesType &nexts_info = (*props)[nexts];
      if (s_info&kStateArcsOut) s_info |= kStateMultipleArcsOut;
      s_info |= kStateArcsOut;
      if (nexts_info&kStateArcsIn) nexts_info |= kStateMultipleArcsIn;
      nexts_info |= kStateArcsIn;
    }
    if (fst.Final(s) != Weight::Zero())  s_info |= kStateFinal;
  }
}

GetSymbols()

void GetSymbols	(	const SymbolTable &	symtab,
		bool	include_eps,
		std::vector< I > *	syms_out
	)

Definition at line 329 of file fstext-utils-inl.h.

References KALDI_ASSERT.

Referenced by main().

                                        {
  KALDI_ASSERT(syms_out != NULL);
  syms_out->clear();
  for (SymbolTableIterator iter(symtab);
      !iter.Done();
      iter.Next()) {
    if (include_eps || iter.Value() != 0) {
      syms_out->push_back(iter.Value());
      KALDI_ASSERT(syms_out->back() == iter.Value());  // an integer-range thing.
    }
  }
}

GraphLatticeScale()

std::vector<std::vector<double> > fst::GraphLatticeScale ( double  lmwt )

inline

Definition at line 147 of file lattice-utils.h.

Referenced by main().

                                                                    {
  std::vector<std::vector<double> > ans(2);
  ans[0].resize(2, 0.0);
  ans[1].resize(2, 0.0);
  ans[0][0] = lmwt;
  ans[1][1] = 1.0;
  return ans;
}

HighestNumberedInputSymbol()

Arc::Label HighestNumberedInputSymbol

(

const Fst< Arc > &

fst

)

Returns the highest numbered input symbol id of the FST (or zero for an empty FST.

Definition at line 54 of file fstext-utils-inl.h.

Referenced by DeterminizeLatticeInsertPhones(), main(), SafeDeterminizeMinimizeWrapper(), SafeDeterminizeWrapper(), TestDeterminizeStarInLog(), and TestPreDeterminize().

                                                                  {
  typename Arc::Label ans = 0;
  for (StateIterator<Fst<Arc> > siter(fst); !siter.Done(); siter.Next()) {
    typename Arc::StateId s = siter.Value();
    for (ArcIterator<Fst<Arc> > aiter(fst, s); !aiter.Done();  aiter.Next()) {
      const Arc &arc = aiter.Value();
      ans = std::max(ans, arc.ilabel);
    }
  }
  return ans;
}

HighestNumberedOutputSymbol()

Arc::Label HighestNumberedOutputSymbol

(

const Fst< Arc > &

fst

)

Returns the highest numbered output symbol id of the FST (or zero for an empty FST.

Definition at line 41 of file fstext-utils-inl.h.

Referenced by LatticeWordAligner::LatticeWordAligner().

                                                                   {
  typename Arc::Label ans = 0;
  for (StateIterator<Fst<Arc> > siter(fst); !siter.Done(); siter.Next()) {
    typename Arc::StateId s = siter.Value();
    for (ArcIterator<Fst<Arc> > aiter(fst, s); !aiter.Done();  aiter.Next()) {
      const Arc &arc = aiter.Value();
      ans = std::max(ans, arc.olabel);
    }
  }
  return ans;
}

InputDeterminizeSingleState() [1/2]

static void fst::InputDeterminizeSingleState ( StdArc::StateId  s, VectorFst< StdArc > *  fst  )

static

Definition at line 31 of file fstdeterminizestart.cc.

References rnnlm::i, and kaldi::LogAdd().

                                                         {
  bool was_input_deterministic = true;
  typedef StdArc Arc;
  typedef Arc::StateId StateId;
  typedef Arc::Label Label;
  typedef Arc::Weight Weight;

  struct InfoForIlabel {
    std::vector<size_t> arc_indexes;  // indexes of all arcs with this ilabel
    float tot_cost;  // total cost of all arcs leaving state s for this
                     // ilabel, summed as if they were negative log-probs.
    StateId new_state;  // state-id of new state, if any, that we have created
                        // to remove duplicate symbols with this ilabel.
    InfoForIlabel(): new_state(-1) { }
  };

  std::unordered_map<Label, InfoForIlabel> label_map;

  size_t arc_index = 0;
  for (ArcIterator<VectorFst<Arc> > aiter(*fst, s);
       !aiter.Done(); aiter.Next(), ++arc_index) {
    const Arc &arc = aiter.Value();
    InfoForIlabel &info = label_map[arc.ilabel];
    if (info.arc_indexes.empty()) {
      info.tot_cost = arc.weight.Value();
    } else {
      info.tot_cost = -kaldi::LogAdd(-info.tot_cost, -arc.weight.Value());
      was_input_deterministic = false;
    }
    info.arc_indexes.push_back(arc_index);
  }

  if (was_input_deterministic)
    return;  // Nothing to do.

  // 'new_arcs' will contain the modified list of arcs
  // leaving state s
  std::vector<Arc> new_arcs;
  new_arcs.reserve(arc_index);
  arc_index = 0;
  for (ArcIterator<VectorFst<Arc> > aiter(*fst, s);
       !aiter.Done(); aiter.Next(), ++arc_index) {
    const Arc &arc = aiter.Value();
    Label ilabel = arc.ilabel;
    InfoForIlabel &info = label_map[ilabel];
    if (info.arc_indexes.size() == 1) {
      new_arcs.push_back(arc);  // no changes needed
    } else {
      if (info.new_state < 0) {
        info.new_state = fst->AddState();
        // add arc from state 's' to newly created state.
        new_arcs.push_back(Arc(ilabel, 0, Weight(info.tot_cost),
                               info.new_state));
      }
      // add arc from new state to original destination of this arc.
      fst->AddArc(info.new_state, Arc(0, arc.olabel,
                                      Weight(arc.weight.Value() - info.tot_cost),
                                      arc.nextstate));
    }
  }
  fst->DeleteArcs(s);
  for (size_t i = 0; i < new_arcs.size(); i++)
    fst->AddArc(s, new_arcs[i]);
}

InputDeterminizeSingleState() [2/2]

static void fst::InputDeterminizeSingleState ( StdArc::StateId  s, VectorFst< StdArc > *  fst  )

static

This utility function input-determinizes a specified state s of the FST 'fst'.

(This input-determinizes while treating epsilon as a real symbol, although for the application we expect to use it, there won't be epsilons).

What this function does is: for any symbol i that appears as the ilabel of more than one arc leaving state s of FST 'fst', it creates an additional state, it creates a new state t with epsilon-input transitions leaving it for each of those multiple arcs leaving state s; it deletes the original arcs leaving state s; and it creates a single arc leaving state s to the newly created state with the ilabel i on it. It sets the weights as necessary to preserve equivalence and also to ensure that if, prior to this modification, the FST was stochastic when cast to the log semiring (see IsStochasticInLog()), it still will be. I.e. when interpreted as negative logprobs, the weight from state s to t would be the sum of the weights on the original arcs leaving state s.

This is used as a very cheap solution when preparing FSTs for the grammar decoder, to ensure that there is only one entry-state to the sub-FST for each phonetic left-context; this keeps the grammar-FST code (i.e. the code that stitches them together) simple. Of course it will tend to introduce unnecessary epsilons, and if we were careful we might be able to remove some of those, but this wouldn't have a substantial impact on overall decoder performance so we don't bother.

Definition at line 472 of file grammar-fst.cc.

References rnnlm::i, and kaldi::LogAdd().

Referenced by main(), and GrammarFstPreparer::Prepare().

                                                                {
  bool was_input_deterministic = true;
  typedef StdArc Arc;
  typedef Arc::StateId StateId;
  typedef Arc::Label Label;
  typedef Arc::Weight Weight;

  struct InfoForIlabel {
    std::vector<size_t> arc_indexes;  // indexes of all arcs with this ilabel
    float tot_cost;  // total cost of all arcs leaving state s for this
                     // ilabel, summed as if they were negative log-probs.
    StateId new_state;  // state-id of new state, if any, that we have created
                        // to remove duplicate symbols with this ilabel.
    InfoForIlabel(): new_state(-1) { }
  };

  std::unordered_map<Label, InfoForIlabel> label_map;

  size_t arc_index = 0;
  for (ArcIterator<VectorFst<Arc> > aiter(*fst, s);
       !aiter.Done(); aiter.Next(), ++arc_index) {
    const Arc &arc = aiter.Value();
    InfoForIlabel &info = label_map[arc.ilabel];
    if (info.arc_indexes.empty()) {
      info.tot_cost = arc.weight.Value();
    } else {
      info.tot_cost = -kaldi::LogAdd(-info.tot_cost, -arc.weight.Value());
      was_input_deterministic = false;
    }
    info.arc_indexes.push_back(arc_index);
  }

  if (was_input_deterministic)
    return;  // Nothing to do.

  // 'new_arcs' will contain the modified list of arcs
  // leaving state s
  std::vector<Arc> new_arcs;
  new_arcs.reserve(arc_index);
  arc_index = 0;
  for (ArcIterator<VectorFst<Arc> > aiter(*fst, s);
       !aiter.Done(); aiter.Next(), ++arc_index) {
    const Arc &arc = aiter.Value();
    Label ilabel = arc.ilabel;
    InfoForIlabel &info = label_map[ilabel];
    if (info.arc_indexes.size() == 1) {
      new_arcs.push_back(arc);  // no changes needed
    } else {
      if (info.new_state < 0) {
        info.new_state = fst->AddState();
        // add arc from state 's' to newly created state.
        new_arcs.push_back(Arc(ilabel, 0, Weight(info.tot_cost),
                               info.new_state));
      }
      // add arc from new state to original destination of this arc.
      fst->AddArc(info.new_state, Arc(0, arc.olabel,
                                      Weight(arc.weight.Value() - info.tot_cost),
                                      arc.nextstate));
    }
  }
  fst->DeleteArcs(s);
  for (size_t i = 0; i < new_arcs.size(); i++)
    fst->AddArc(s, new_arcs[i]);
}

IsStochasticFst() [1/2]

bool IsStochasticFst ( const Fst< LogArc > &  fst, float  delta, LogArc::Weight *  min_sum, LogArc::Weight *  max_sum  )

inline

Definition at line 1173 of file fstext-utils-inl.h.

References ApproxEqual(), and Plus().

Referenced by IsStochasticFstInLog(), main(), MinimizeEncoded(), RhoCompose(), and TestRemoveEpsLocalSpecial().

                                            {
  typedef LogArc Arc;
  typedef Arc::StateId StateId;
  typedef Arc::Weight Weight;
  bool first_time = true;
  bool ans = true;
  if (min_sum) *min_sum = LogArc::Weight::One();
  if (max_sum) *max_sum = LogArc::Weight::One();
  for (StateIterator<Fst<Arc> > siter(fst); !siter.Done(); siter.Next()) {
    StateId s = siter.Value();
    Weight sum = fst.Final(s);
    for (ArcIterator<Fst<Arc> > aiter(fst, s); !aiter.Done(); aiter.Next()) {
      const Arc &arc = aiter.Value();
      sum = Plus(sum, arc.weight);
    }
    if (!ApproxEqual(Weight::One(), sum, delta)) ans = false;
    if (first_time) {
      first_time = false;
      if (max_sum) *max_sum = sum;
      if (min_sum) *min_sum = sum;
    } else {
      // note that max and min are reversed from their normal
      // meanings here (max and min w.r.t. the underlying probabilities).
      if (max_sum && sum.Value() < max_sum->Value()) *max_sum = sum;
      if (min_sum && sum.Value() > min_sum->Value()) *min_sum = sum;
    }
  }
  if (first_time) {  // just avoid NaNs if FST was empty.
    if (max_sum) *max_sum = Weight::One();
    if (min_sum) *min_sum = Weight::One();
  }
  return ans;
}

IsStochasticFst() [2/2]

bool IsStochasticFst ( const Fst< Arc > &  fst, float  delta = kDelta, typename Arc::Weight *  min_sum = NULL, typename Arc::Weight *  max_sum = NULL  )

inline

This function returns true if, in the semiring of the FST, the sum (within the semiring) of all the arcs out of each state in the FST is one, to within delta.

After MakeStochasticFst, this should be true (for a connected FST).

Parameters

fst	[in] the FST that we are testing.
delta	[in] the tolerance to within which we test equality to 1.
min_sum	[out] if non, NULL, contents will be set to the minimum sum of weights.
max_sum	[out] if non, NULL, contents will be set to the maximum sum of weights.

Returns

Returns true if the FST is stochastic, and false otherwise.

Definition at line 1135 of file fstext-utils-inl.h.

References ApproxEqual(), and Plus().

                                                  {
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Weight Weight;
  NaturalLess<Weight> nl;
  bool first_time = true;
  bool ans = true;
  if (min_sum) *min_sum = Arc::Weight::One();
  if (max_sum) *max_sum = Arc::Weight::One();
  for (StateIterator<Fst<Arc> > siter(fst); !siter.Done(); siter.Next()) {
    StateId s = siter.Value();
    Weight sum = fst.Final(s);
    for (ArcIterator<Fst<Arc> > aiter(fst, s); !aiter.Done(); aiter.Next()) {
      const Arc &arc = aiter.Value();
      sum = Plus(sum, arc.weight);
    }
    if (!ApproxEqual(Weight::One(), sum, delta)) ans = false;
    if (first_time) {
      first_time = false;
      if (max_sum) *max_sum = sum;
      if (min_sum) *min_sum = sum;
    } else {
      if (max_sum && nl(*max_sum, sum)) *max_sum = sum;
      if (min_sum && nl(sum, *min_sum)) *min_sum = sum;
    }
  }
  if (first_time) {  // just avoid NaNs if FST was empty.
    if (max_sum) *max_sum = Weight::One();
    if (min_sum) *min_sum = Weight::One();
  }
  return ans;
}

IsStochasticFstInLog()

bool IsStochasticFstInLog ( const Fst< StdArc > &  fst, float  delta, StdArc::Weight *  min_sum, StdArc::Weight *  max_sum  )

inline

Definition at line 1215 of file fstext-utils-inl.h.

References IsStochasticFst(), and KALDI_ERR.

Referenced by main(), MinimizeEncoded(), and TestPushSpecial().

                                                 {
  bool ans = false;
  LogArc::Weight log_min = LogArc::Weight::One(),
    log_max = LogArc::Weight::Zero();
  if (fst.Type() == "const") {
    ConstFst<LogArc> logfst;
    Cast(dynamic_cast<const ConstFst<StdArc>&>(fst), &logfst);
    ans = IsStochasticFst(logfst, delta, &log_min, &log_max);
  } else if (fst.Type() == "vector") {
    VectorFst<LogArc> logfst;
    Cast(dynamic_cast<const VectorFst<StdArc>&>(fst), &logfst);
    ans = IsStochasticFst(logfst, delta, &log_min, &log_max);
  } else {
    KALDI_ERR << "This version currently supports ConstFst<StdArc> "
              << "or VectorFst<StdArc>";
  }
  if (min_sum) *min_sum = StdArc::Weight(log_min.Value());
  if (max_sum) *max_sum = StdArc::Weight(log_max.Value());
  return ans;
}

LatticeScale()

std::vector<std::vector<double> > fst::LatticeScale ( double  lmwt, double  acwt  )

inline

Definition at line 156 of file lattice-utils.h.

References CompactLatticeHasAlignment(), RemoveAlignmentsFromCompactLattice(), and ScaleLattice().

Referenced by main().

                                                                            {
  std::vector<std::vector<double> > ans(2);
  ans[0].resize(2, 0.0);
  ans[1].resize(2, 0.0);
  ans[0][0] = lmwt;
  ans[1][1] = acwt;
  return ans;
}

LatticeWeightTest()

void fst::LatticeWeightTest

(

)

Definition at line 64 of file lattice-weight-test.cc.

References ApproxEqual(), kaldi::AssertEqual(), Compare(), Divide(), rnnlm::i, KALDI_ASSERT, LatticeWeightTpl< FloatType >::Member(), LatticeWeightTpl< BaseFloat >::One(), Plus(), LatticeWeightTpl< FloatType >::Quantize(), RandomLatticeWeight(), LatticeWeightTpl< FloatType >::Read(), LatticeWeightTpl< FloatType >::Reverse(), Times(), LatticeWeightTpl< FloatType >::Value1(), LatticeWeightTpl< FloatType >::Value2(), and LatticeWeightTpl< BaseFloat >::Zero().

Referenced by main().

                         {
  for(int32 i = 0; i < 100; i++) {
    LatticeWeight l1 = RandomLatticeWeight(), l2 = RandomLatticeWeight();
    LatticeWeight l3 = Plus(l1, l2);
    LatticeWeight l4 = Times(l1, l2);
    BaseFloat f1 = l1.Value1() + l1.Value2(), f2 = l2.Value1() + l2.Value2(), f3 = l3.Value1() + l3.Value2(),
        f4 = l4.Value1() + l4.Value2();
    kaldi::AssertEqual(std::min(f1, f2), f3);
    kaldi::AssertEqual(f1 + f2, f4);

    KALDI_ASSERT(Plus(l3, l3) == l3);
    KALDI_ASSERT(Plus(l1, l2) == Plus(l2, l1)); // commutativity of plus
    KALDI_ASSERT(Times(l1, l2) == Times(l2, l1)); // commutativity of Times (true for this semiring, not always)
    KALDI_ASSERT(Plus(l3, LatticeWeight::Zero()) == l3); // x + 0 = x
    KALDI_ASSERT(Times(l3, LatticeWeight::One()) == l3); // x * 1 = x
    KALDI_ASSERT(Times(l3, LatticeWeight::Zero()) == LatticeWeight::Zero()); // x * 0 = 0

    KALDI_ASSERT(l3.Reverse().Reverse() == l3);

    NaturalLess<LatticeWeight> nl;
    bool a = nl(l1, l2);
    bool b = (Plus(l1, l2) == l1 && l1 != l2);
    KALDI_ASSERT(a == b);

    KALDI_ASSERT(Compare(l1, Plus(l1, l2)) != 1); // so do not have l1 > l1 + l2
    LatticeWeight l5 = RandomLatticeWeight(), l6 = RandomLatticeWeight();
    {
      LatticeWeight wa = Times(Plus(l1, l2), Plus(l5, l6)),
          wb =  Plus(Times(l1, l5), Plus(Times(l1, l6),
                                        Plus(Times(l2, l5), Times(l2, l6))));
      if (!ApproxEqual(wa, wb)) {
        std::cout << "l1 = " << l1 << ", l2 = " << l2
                  << ", l5 = " << l5 << ", l6 = " << l6 << "\n";
        std::cout << "ERROR: " << wa << " != " <<  wb << "\n";
      }
      // KALDI_ASSERT(Times(Plus(l1, l2), Plus(l5, l6))
      // == Plus(Times(l1, l5), Plus(Times(l1,l6),
      // Plus(Times(l2, l5), Times(l2, l6))))); // * distributes over +
    }
    KALDI_ASSERT(l1.Member() && l2.Member() && l3.Member() && l4.Member()
                 && l5.Member() && l6.Member());
    if (l2 != LatticeWeight::Zero())
      KALDI_ASSERT(ApproxEqual(Divide(Times(l1, l2), l2), l1)); // (a*b) / b = a if b != 0
    KALDI_ASSERT(ApproxEqual(l1, l1.Quantize()));

    std::ostringstream s1;
    s1 << l1;
    std::istringstream s2(s1.str());
    s2 >> l2;
    KALDI_ASSERT(ApproxEqual(l1, l2, 0.001));
    std::cout << s1.str() << '\n';
    {
      std::ostringstream s1b;
      l1.Write(s1b);
      std::istringstream s2b(s1b.str());
      l3.Read(s2b);
      KALDI_ASSERT(l1 == l3);
    }
  }
}

MakeFollowingInputSymbolsSame()

void MakeFollowingInputSymbolsSame	(	bool	end_is_epsilon,
		MutableFst< Arc > *	fst
	)

MakeFollowingInputSymbolsSame ensures that all arcs exiting any given fst state have the same input symbol.

It does this by detecting states that have differing input symbols on arcs that exit it, and inserting, for each of the following arcs with non-epsilon input symbol, a new dummy state that has an input-epsilon link from the fst state. The output symbol and weight stay on the link to the dummy state (in order to keep the FST output-deterministic and stochastic, if it already was). If end_is_epsilon, treat "being a final-state" like having an epsilon output link.

Definition at line 610 of file fstext-utils-inl.h.

References MakeFollowingInputSymbolsSameClass().

Referenced by MinimizeEncoded(), and TestMakeSymbolsSame().

                                                                              {
  IdentityFunction<typename Arc::Label> f;
  MakeFollowingInputSymbolsSameClass(end_is_epsilon, fst, f);
}

MakeFollowingInputSymbolsSameClass()

void MakeFollowingInputSymbolsSameClass	(	bool	end_is_epsilon,
		MutableFst< Arc > *	fst,
		const F &	f
	)

As MakeFollowingInputSymbolsSame, but takes a functor object that maps labels to classes.

Definition at line 616 of file fstext-utils-inl.h.

References rnnlm::i, and rnnlm::j.

Referenced by kaldi::AddSelfLoopsNoReorder(), MakeFollowingInputSymbolsSame(), MinimizeEncoded(), and TestMakeSymbolsSameClass().

                                                                                               {
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Weight Weight;
  typedef typename F::Result ClassType;
  std::vector<StateId> bad_states;
  ClassType noClass = f(kNoLabel);
  ClassType epsClass = f(0);
  for (StateIterator<Fst<Arc> > siter(*fst); !siter.Done(); siter.Next()) {
    StateId s = siter.Value();
    ClassType c = noClass;
    bool bad = false;
    for (ArcIterator<Fst<Arc> > aiter(*fst, s); !aiter.Done(); aiter.Next()) {
      const Arc &arc = aiter.Value();
      if (c == noClass)
        c = f(arc.ilabel);
      else
        if (c != f(arc.ilabel)) {
          bad = true;
          break;
        }
    }
    if (end_is_epsilon && c != noClass &&
       c != epsClass && fst->Final(s) != Weight::Zero())
      bad = true;
    if (bad)
      bad_states.push_back(s);
  }
  std::vector<Arc> my_arcs;
  for (size_t i = 0; i < bad_states.size(); i++) {
    StateId s = bad_states[i];
    my_arcs.clear();
    for (ArcIterator<MutableFst<Arc> > aiter(*fst, s); !aiter.Done(); aiter.Next())
      my_arcs.push_back(aiter.Value());

    for (size_t j = 0; j < my_arcs.size(); j++) {
      Arc &arc = my_arcs[j];
      if (arc.ilabel != 0) {
        StateId newstate = fst->AddState();
        // Create a new state for each non-eps arc in original FST, out of each bad state.
        // Not as optimal as it could be, but does avoid some complicated weight-pushing
        // issues in which, to maintain stochasticity, we would have to know which semiring
        // we want to maintain stochasticity in.
        fst->AddArc(newstate, Arc(arc.ilabel, 0, Weight::One(), arc.nextstate));
        MutableArcIterator<MutableFst<Arc> > maiter(fst, s);
        maiter.Seek(j);
        maiter.SetValue(Arc(0, arc.olabel, arc.weight, newstate));
      }
    }
  }
}

MakeLinearAcceptor()

void MakeLinearAcceptor	(	const std::vector< I > &	labels,
		MutableFst< Arc > *	ofst
	)

Creates unweighted linear acceptor from symbol sequence.

Definition at line 311 of file fstext-utils-inl.h.

References rnnlm::i.

Referenced by TrainingGraphCompiler::CompileGraphFromText(), TrainingGraphCompiler::CompileGraphsFromText(), main(), MinimizeEncoded(), and TestMakeLinearAcceptor().

                                                                           {
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Weight Weight;

  ofst->DeleteStates();
  StateId cur_state = ofst->AddState();
  ofst->SetStart(cur_state);
  for (size_t i = 0; i < labels.size(); i++) {
    StateId next_state = ofst->AddState();
    Arc arc(labels[i], labels[i], Weight::One(), next_state);
    ofst->AddArc(cur_state, arc);
    cur_state = next_state;
  }
  ofst->SetFinal(cur_state, Weight::One());
}

MakeLinearAcceptorWithAlternatives()

void MakeLinearAcceptorWithAlternatives	(	const std::vector< std::vector< I > > &	labels,
		MutableFst< Arc > *	ofst
	)

Creates an unweighted acceptor with a linear structure, with alternatives at each position.

Epsilon is treated like a normal symbol here. Each position in "labels" must have at least one alternative.

Definition at line 290 of file fstext-utils-inl.h.

References rnnlm::i, rnnlm::j, and KALDI_ASSERT.

Referenced by MinimizeEncoded().

                                                               {
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Weight Weight;

  ofst->DeleteStates();
  StateId cur_state = ofst->AddState();
  ofst->SetStart(cur_state);
  for (size_t i = 0; i < labels.size(); i++) {
    KALDI_ASSERT(labels[i].size() != 0);
    StateId next_state = ofst->AddState();
    for (size_t j = 0; j < labels[i].size(); j++) {
      Arc arc(labels[i][j], labels[i][j], Weight::One(), next_state);
      ofst->AddArc(cur_state, arc);
    }
    cur_state = next_state;
  }
  ofst->SetFinal(cur_state, Weight::One());
}

MakeLoopFst()

VectorFst< Arc > * MakeLoopFst

(

const std::vector< const ExpandedFst< Arc > * > &

fsts

)

MakeLoopFst creates an FST that has a state that is both initial and final (weight == Weight::One()), and for each non-NULL pointer fsts[i], it has an arc out whose output-symbol is i and which goes to a sub-graph whose input language is equivalent to fsts[i], where the final-state becomes a transition to the loop-state.

Each fst in "fsts" should be an acceptor. The fst MakeLoopFst returns is output-deterministic, but not output-epsilon free necessarily, and arcs are sorted on output label. Note: if some of the pointers in the input vector "fsts" have the same value, "MakeLoopFst" uses this to speed up the computation. Formally: suppose I is the set of indexes i such that fsts[i] != NULL. Let L[i] be the language that the acceptor fsts[i] accepts. Let the language K be the set of input-output pairs i:l such that i in I and l in L[i]. Then the FST returned by MakeLoopFst accepts the language K*, where * is the Kleene closure (CLOSURE_STAR) of K. We could have implemented this via a combination of "project", "concat", "union" and "closure". But that FST would have been less well optimized and would have a lot of final-states.

Definition at line 669 of file fstext-utils-inl.h.

References rnnlm::i, and KALDI_ASSERT.

Referenced by kaldi::GetHTransducer(), MinimizeEncoded(), and TestMakeLoopFst().

                                                                             {
  typedef typename Arc::Weight Weight;
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Label Label;

  VectorFst<Arc> *ans = new VectorFst<Arc>;
  StateId loop_state = ans->AddState();  // = 0.
  ans->SetStart(loop_state);
  ans->SetFinal(loop_state, Weight::One());

  // "cache" is used as an optimization when some of the pointers in "fsts"
  // may have the same value.
  unordered_map<const ExpandedFst<Arc> *, Arc> cache;

  for (Label i = 0; i < static_cast<Label>(fsts.size()); i++) {
    const ExpandedFst<Arc> *fst = fsts[i];
    if (fst == NULL) continue;
    { // optimization with cache: helpful if some members of "fsts" may
      // contain the same pointer value (e.g. in GetHTransducer).
      typename unordered_map<const ExpandedFst<Arc> *, Arc>::iterator
          iter = cache.find(fst);
      if (iter != cache.end()) {
        Arc arc = iter->second;
        arc.olabel = i;
        ans->AddArc(0, arc);
        continue;
      }
    }

    KALDI_ASSERT(fst->Properties(kAcceptor, true) == kAcceptor);  // expect acceptor.

    StateId fst_num_states = fst->NumStates();
    StateId fst_start_state = fst->Start();

    if (fst_start_state == kNoStateId)
      continue;  // empty fst.

    bool share_start_state =
        fst->Properties(kInitialAcyclic, true) == kInitialAcyclic
        && fst->NumArcs(fst_start_state) == 1
        && fst->Final(fst_start_state) == Weight::Zero();

    std::vector<StateId> state_map(fst_num_states);  // fst state -> ans state
    for (StateId s = 0; s < fst_num_states; s++) {
      if (s == fst_start_state && share_start_state) state_map[s] = loop_state;
      else state_map[s] = ans->AddState();
    }
    if (!share_start_state) {
      Arc arc(0, i, Weight::One(), state_map[fst_start_state]);
      cache[fst] = arc;
      ans->AddArc(0, arc);
    }
    for (StateId s = 0; s < fst_num_states; s++) {
      // Add arcs out of state s.
      for (ArcIterator<ExpandedFst<Arc> > aiter(*fst, s); !aiter.Done(); aiter.Next()) {
        const Arc &arc = aiter.Value();
        Label olabel = (s == fst_start_state && share_start_state ? i : 0);
        Arc newarc(arc.ilabel, olabel, arc.weight, state_map[arc.nextstate]);
        ans->AddArc(state_map[s], newarc);
        if (s == fst_start_state && share_start_state)
          cache[fst] = newarc;
      }
      if (fst->Final(s) != Weight::Zero()) {
        KALDI_ASSERT(!(s == fst_start_state && share_start_state));
        ans->AddArc(state_map[s], Arc(0, 0, fst->Final(s), loop_state));
      }
    }
  }
  return ans;
}

MakeLoopFstCompare()

VectorFst<Arc>* fst::MakeLoopFstCompare

(

const vector< const ExpandedFst< Arc > *> &

fsts

)

Definition at line 281 of file fstext-utils-test.cc.

References ClearSymbols(), fst::pre_determinize_helpers::Closure(), and rnnlm::i.

Referenced by TestMakeLoopFst().

                                                                                 {
  VectorFst<Arc> *ans = new VectorFst<Arc>;
  typedef typename Arc::Label Label;
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Weight Weight;

  for (Label i = 0; i <  fsts.size(); i++) {
    if (fsts[i] != NULL) {
      VectorFst<Arc> i_fst;  // accepts symbol i on output.
      i_fst.AddState(); i_fst.AddState();
      i_fst.SetStart(0); i_fst.SetFinal(1, Weight::One());
      i_fst.AddArc(0, Arc(0, i, Weight::One(), 1));
      VectorFst<Arc> other_fst(*(fsts[i]));  // copy it.
      ClearSymbols(false, true, &other_fst);  // Clear output symbols so symbols
      // are on input side.
      Concat(&i_fst, other_fst);  // now i_fst is "i_fst [concat] other_fst".
      Union(ans, i_fst);
    }
  }
  Closure(ans, CLOSURE_STAR);
  return ans;
}

MakePrecedingInputSymbolsSame()

void MakePrecedingInputSymbolsSame	(	bool	start_is_epsilon,
		MutableFst< Arc > *	fst
	)

MakePrecedingInputSymbolsSame ensures that all arcs entering any given fst state have the same input symbol.

It does this by detecting states that have differing input symbols going in, and inserting, for each of the preceding arcs with non-epsilon input symbol, a new dummy state that has an epsilon link to the fst state. If "start_is_epsilon", ensure that start-state can have only epsilon-links into it.

Definition at line 528 of file fstext-utils-inl.h.

References MakePrecedingInputSymbolsSameClass().

Referenced by MinimizeEncoded(), and TestMakeSymbolsSame().

                                                                                {
  IdentityFunction<typename Arc::Label> f;
  MakePrecedingInputSymbolsSameClass(start_is_epsilon, fst, f);
}

MakePrecedingInputSymbolsSameClass()

void MakePrecedingInputSymbolsSameClass	(	bool	start_is_epsilon,
		MutableFst< Arc > *	fst,
		const F &	f
	)

As MakePrecedingInputSymbolsSame, but takes a functor object that maps labels to classes.

Definition at line 534 of file fstext-utils-inl.h.

References ConstIntegerSet< I >::count(), rnnlm::i, and KALDI_ASSERT.

Referenced by kaldi::AddSelfLoopsReorder(), MakePrecedingInputSymbolsSame(), MinimizeEncoded(), and TestMakeSymbolsSameClass().

                                                                                                 {
  typedef typename F::Result ClassType;
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Weight Weight;
  std::vector<ClassType> classes;
  ClassType noClass = f(kNoLabel);
  ClassType epsClass = f(0);
  if (start_is_epsilon) {  // treat having-start-state as epsilon in-transition.
    StateId start_state = fst->Start();
    if (start_state < 0 || start_state == kNoStateId) // empty FST.
      return;
    classes.resize(start_state+1, noClass);
    classes[start_state] = epsClass;
  }

  // Find bad states (states with multiple input-symbols into them).
  std::set<StateId> bad_states;  // states that we need to change.
  for (StateIterator<Fst<Arc> > siter(*fst); !siter.Done(); siter.Next()) {
    StateId s = siter.Value();
    for (ArcIterator<Fst<Arc> > aiter(*fst, s); !aiter.Done(); aiter.Next()) {
      const Arc &arc = aiter.Value();
      if (classes.size() <= static_cast<size_t>(arc.nextstate))
        classes.resize(arc.nextstate+1, noClass);
      if (classes[arc.nextstate] == noClass)
        classes[arc.nextstate] = f(arc.ilabel);
      else
        if (classes[arc.nextstate] != f(arc.ilabel))
          bad_states.insert(arc.nextstate);
    }
  }
  if (bad_states.empty()) return;  // Nothing to do.
  kaldi::ConstIntegerSet<StateId> bad_states_ciset(bad_states);  // faster lookup.

  // Work out list of arcs we have to change as (state, arc-offset).
  // Can't do the actual changes in this pass, since we have to add new
  // states which invalidates the iterators.
  std::vector<std::pair<StateId, size_t> > arcs_to_change;
  for (StateIterator<Fst<Arc> > siter(*fst); !siter.Done(); siter.Next()) {
    StateId s = siter.Value();
    for (ArcIterator<Fst<Arc> > aiter(*fst, s); !aiter.Done(); aiter.Next()) {
      const Arc &arc = aiter.Value();
      if (arc.ilabel != 0 &&
         bad_states_ciset.count(arc.nextstate) != 0)
        arcs_to_change.push_back(std::make_pair(s, aiter.Position()));
    }
  }
  KALDI_ASSERT(!arcs_to_change.empty());  // since !bad_states.empty().

  std::map<std::pair<StateId, ClassType>, StateId> state_map;
  // state_map is a map from (bad-state, input-symbol-class) to dummy-state.

  for (size_t i = 0; i < arcs_to_change.size(); i++) {
    StateId s = arcs_to_change[i].first;
    ArcIterator<MutableFst<Arc> > aiter(*fst, s);
    aiter.Seek(arcs_to_change[i].second);
    Arc arc = aiter.Value();

    // Transition is non-eps transition to "bad" state.  Introduce new state (or find
    // existing one).
    std::pair<StateId, ClassType> p(arc.nextstate, f(arc.ilabel));
    if (state_map.count(p) == 0) {
      StateId newstate = state_map[p] = fst->AddState();
      fst->AddArc(newstate, Arc(0, 0, Weight::One(), arc.nextstate));
    }
    StateId dst_state = state_map[p];
    arc.nextstate = dst_state;

    // Initialize the MutableArcIterator only now, as the call to NewState()
    // may have invalidated the first arc iterator.
    MutableArcIterator<MutableFst<Arc> > maiter(fst, s);
    maiter.Seek(arcs_to_change[i].second);
    maiter.SetValue(arc);
  }
}

MapInputSymbols()

void MapInputSymbols	(	const std::vector< I > &	symbol_mapping,
		MutableFst< Arc > *	fst
	)

Definition at line 168 of file fstext-utils-inl.h.

References KALDI_ASSERT_IS_INTEGER_TYPE.

Referenced by MinimizeEncoded(), and TestFactor().

                                           {
  KALDI_ASSERT_IS_INTEGER_TYPE(I);
  // false == don't copy the "symbol_mapping", retain pointer--
  // safe since short-lived object.
  MapInputSymbolsMapper<Arc, I> mapper(symbol_mapping, false);
  Map(fst, mapper);
}

MinimizeCompactLattice()

bool MinimizeCompactLattice	(	MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, IntType > > > *	clat,
		float	delta = fst::kDelta
	)

This function minimizes the compact lattice.

It is to be called after determinization (see ./determinize-lattice-pruned.h) and pushing (see ./push-lattice.h). If the lattice is not determinized and pushed this function will not combine as many states as it could, but it won't crash. Returns true on success, and false if it failed due to topological sorting failing. The output will be topologically sorted.

Definition at line 274 of file minimize-lattice.cc.

References CompactLatticeMinimizer< Weight, IntType >::Minimize().

Referenced by main(), DeterminizeLatticeTask::operator()(), and kaldi::TestMinimizeCompactLattice().

                 {
  CompactLatticeMinimizer<Weight, IntType> minimizer(clat, delta);
  return minimizer.Minimize();
}

MinimizeCompactLattice< kaldi::LatticeWeight, kaldi::int32 >()

template bool fst::MinimizeCompactLattice< kaldi::LatticeWeight, kaldi::int32 >	(	MutableFst< kaldi::CompactLatticeArc > *	clat,
		float	delta
	)

MinimizeEncoded()

void fst::MinimizeEncoded	(	VectorFst< Arc > *	fst,
		float	delta = kDelta
	)

Definition at line 114 of file fstext-utils.h.

References ApplyProbabilityScale(), ConvertNbestToVector(), EqualAlign(), FollowingInputSymbolsAreSame(), FollowingInputSymbolsAreSameClass(), GetLinearSymbolSequence(), IsStochasticFst(), IsStochasticFstInLog(), MakeFollowingInputSymbolsSame(), MakeFollowingInputSymbolsSameClass(), MakeLinearAcceptor(), MakeLinearAcceptorWithAlternatives(), MakeLoopFst(), MakePrecedingInputSymbolsSame(), MakePrecedingInputSymbolsSameClass(), MapInputSymbols(), rnnlm::n, NbestAsFsts(), PhiCompose(), PrecedingInputSymbolsAreSame(), PrecedingInputSymbolsAreSameClass(), PropagateFinal(), RemoveSomeInputSymbols(), RemoveUselessArcs(), RemoveWeights(), RhoCompose(), SafeDeterminizeMinimizeWrapper(), SafeDeterminizeMinimizeWrapperInLog(), and SafeDeterminizeWrapper().

Referenced by TrainingGraphCompiler::CompileGraph(), TrainingGraphCompiler::CompileGraphs(), main(), SafeDeterminizeMinimizeWrapper(), and SafeDeterminizeMinimizeWrapperInLog().

                                                                {

  Map(fst, QuantizeMapper<Arc>(delta));
  EncodeMapper<Arc> encoder(kEncodeLabels | kEncodeWeights, ENCODE);
  Encode(fst, &encoder);
  internal::AcceptorMinimize(fst);
  Decode(fst, encoder);
}

NbestAsFsts()

void NbestAsFsts	(	const Fst< Arc > &	fst,
		size_t	n,
		std::vector< VectorFst< Arc > > *	fsts_out
	)

Takes the n-shortest-paths (using ShortestPath), but outputs the result as a vector of up to n fsts.

This function will size the "fsts_out" vector to however many paths it got (which will not exceed n). n must be >= 1.

Definition at line 279 of file fstext-utils-inl.h.

References ConvertNbestToVector(), and KALDI_ASSERT.

Referenced by MinimizeEncoded(), kaldi::SentenceLevelConfidence(), and TestMakeLinearAcceptor().

                                                       {
  KALDI_ASSERT(n > 0);
  KALDI_ASSERT(fsts_out != NULL);
  VectorFst<Arc> nbest_fst;
  ShortestPath(fst, &nbest_fst, n);
  ConvertNbestToVector(nbest_fst, fsts_out);
}

NumArcs()

Arc::StateId NumArcs

(

const ExpandedFst< Arc > &

fst

)

Returns the total number of arcs in an FST.

Definition at line 67 of file fstext-utils-inl.h.

Referenced by kaldi::DeterminizeLatticeWrapper(), main(), and TrivialFactorWeightFstImpl< A, F >::NumArcs().

                                                         {
  typedef typename Arc::StateId StateId;
  StateId num_arcs = 0;
  for (StateId s = 0; s < fst.NumStates(); s++)
    num_arcs += fst.NumArcs(s);
  return num_arcs;
}

operator!=() [1/2]

bool fst::operator!= ( const LatticeWeightTpl< FloatType > &  wa, const LatticeWeightTpl< FloatType > &  wb  )

inline

Definition at line 277 of file lattice-weight.h.

References LatticeWeightTpl< FloatType >::Value1(), and LatticeWeightTpl< FloatType >::Value2().

                                                              {
  // Volatile qualifier thwarts over-aggressive compiler optimizations
  // that lead to problems esp. with NaturalLess().
  volatile FloatType va1 = wa.Value1(), va2 = wa.Value2(),
      vb1 = wb.Value1(), vb2 = wb.Value2();
  return (va1 != vb1 || va2 != vb2);
}

operator!=() [2/2]

bool fst::operator!= ( const CompactLatticeWeightTpl< WeightType, IntType > &  w1, const CompactLatticeWeightTpl< WeightType, IntType > &  w2  )

inline

Definition at line 564 of file lattice-weight.h.

References CompactLatticeWeightTpl< WeightType, IntType >::String(), and CompactLatticeWeightTpl< WeightType, IntType >::Weight().

                                                                               {
  return (w1.Weight() != w2.Weight() || w1.String() != w2.String());
}

operator<<() [1/2]

std::ostream & operator<< ( std::ostream &  strm, const LatticeWeightTpl< FloatType > &  w  )

inline

Definition at line 397 of file lattice-weight.h.

References LatticeWeightTpl< FloatType >::WriteFloatType().

                                                                                       {
  LatticeWeightTpl<FloatType>::WriteFloatType(strm, w.Value1());
  CHECK(FLAGS_fst_weight_separator.size() == 1);
  strm << FLAGS_fst_weight_separator[0]; // comma by default;
  // may or may not be settable from Kaldi programs.
  LatticeWeightTpl<FloatType>::WriteFloatType(strm, w.Value2());
  return strm;
}

operator<<() [2/2]

std::ostream& fst::operator<< ( std::ostream &  strm, const CompactLatticeWeightTpl< WeightType, IntType > &  w  )

inline

Definition at line 729 of file lattice-weight.h.

References rnnlm::i.

                                                                                                        {
  strm << w.Weight();
  CHECK(FLAGS_fst_weight_separator.size() == 1);
  strm << FLAGS_fst_weight_separator[0]; // comma by default.
  for(size_t i = 0; i < w.String().size(); i++) {
    strm << w.String()[i];
    if (i+1 < w.String().size())
      strm << kStringSeparator; // '_'; defined in string-weight.h in OpenFst code.
  }
  return strm;
}

operator==() [1/2]

bool fst::operator== ( const LatticeWeightTpl< FloatType > &  wa, const LatticeWeightTpl< FloatType > &  wb  )

inline

Definition at line 267 of file lattice-weight.h.

References LatticeWeightTpl< FloatType >::Value1(), and LatticeWeightTpl< FloatType >::Value2().

Referenced by DiscriminativeSupervision::DiscriminativeSupervision(), and ArpaLmCompilerImplInterface::~ArpaLmCompilerImplInterface().

                                                              {
  // Volatile qualifier thwarts over-aggressive compiler optimizations
  // that lead to problems esp. with NaturalLess().
  volatile FloatType va1 = wa.Value1(), va2 = wa.Value2(),
      vb1 = wb.Value1(), vb2 = wb.Value2();
  return (va1 == vb1 && va2 == vb2);
}

operator==() [2/2]

bool fst::operator== ( const CompactLatticeWeightTpl< WeightType, IntType > &  w1, const CompactLatticeWeightTpl< WeightType, IntType > &  w2  )

inline

Definition at line 558 of file lattice-weight.h.

References CompactLatticeWeightTpl< WeightType, IntType >::String(), and CompactLatticeWeightTpl< WeightType, IntType >::Weight().

                                                                               {
  return (w1.Weight() == w2.Weight() && w1.String() == w2.String());
}

operator>>() [1/2]

std::istream & operator>> ( std::istream &  strm, LatticeWeightTpl< FloatType > &  w  )

inline

Definition at line 407 of file lattice-weight.h.

References LatticeWeightTpl< FloatType >::ReadNoParen().

                                                                                  {
  CHECK(FLAGS_fst_weight_separator.size() == 1);
  // separator defaults to ','
  return w1.ReadNoParen(strm, FLAGS_fst_weight_separator[0]);
}

operator>>() [2/2]

std::istream& fst::operator>> ( std::istream &  strm, CompactLatticeWeightTpl< WeightType, IntType > &  w  )

inline

Definition at line 742 of file lattice-weight.h.

References rnnlm::i, CompactLatticeWeightTpl< WeightType, IntType >::SetString(), and CompactLatticeWeightTpl< WeightType, IntType >::SetWeight().

                                                                                                  {
  std::string s;
  strm >> s;
  if (strm.fail()) {
    return strm;
  }
  CHECK(FLAGS_fst_weight_separator.size() == 1);
  size_t pos = s.find_last_of(FLAGS_fst_weight_separator); // normally ","
  if (pos == std::string::npos) {
    strm.clear(std::ios::badbit);
    return strm;
  }
  // get parts of str before and after the separator (default: ',');
  std::string s1(s, 0, pos), s2(s, pos+1);
  std::istringstream strm1(s1);
  WeightType weight;
  strm1 >> weight;
  w.SetWeight(weight);
  if (strm1.fail() || !strm1.eof()) {
    strm.clear(std::ios::badbit);
    return strm;
  }
  // read string part.
  std::vector<IntType> string;
  const char *c = s2.c_str();
  while(*c != '\0') {
    if (*c == kStringSeparator) // '_'
      c++;
    char *c2;
    long int i = strtol(c, &c2, 10);
    if (c2 == c || static_cast<long int>(static_cast<IntType>(i)) != i) {
      strm.clear(std::ios::badbit);
      return strm;
    }
    c = c2;
    string.push_back(static_cast<IntType>(i));
  }
  w.SetString(string);
  return strm;
}

PenalizeArcsWithSomeInputSymbols()

void fst::PenalizeArcsWithSomeInputSymbols	(	const std::vector< I > &	symbols_in,
		float	penalty,
		VectorFst< Arc > *	fst
	)

Definition at line 58 of file fstrmsymbols.cc.

References ConstIntegerSet< I >::count(), and Times().

Referenced by main().

                                                           {
  typedef typename Arc::StateId StateId;
  typedef typename Arc::Label Label;
  typedef typename Arc::Weight Weight;

  Weight penalty_weight(penalty);

  kaldi::ConstIntegerSet<I> symbol_set(symbols_in);

  StateId num_states = fst->NumStates();
  for (StateId s = 0; s < num_states; s++) {
    for (MutableArcIterator<VectorFst<Arc> > iter(fst, s);
         !iter.Done(); iter.Next()) {
      if (symbol_set.count(iter.Value().ilabel) != 0) {
        Arc arc = iter.Value();
        arc.weight = Times(arc.weight, penalty_weight);
        iter.SetValue(arc);
      }
    }
  }
}

PhiCompose()

void PhiCompose	(	const Fst< Arc > &	fst1,
		const Fst< Arc > &	fst2,
		typename Arc::Label	phi_label,
		MutableFst< Arc > *	ofst
	)

Definition at line 1021 of file fstext-utils-inl.h.

References KALDI_ASSERT.

Referenced by main(), and MinimizeEncoded().

                                       {
  KALDI_ASSERT(phi_label != kNoLabel); // just use regular compose in this case.
  typedef Fst<Arc> F;
  typedef PhiMatcher<SortedMatcher<F> > PM;
  CacheOptions base_opts;
  base_opts.gc_limit = 0; // Cache only the last state for fastest copy.
  // ComposeFstImplOptions templated on matcher for fst1, matcher for fst2.
  // The matcher for fst1 doesn't matter; we'll use fst2's matcher.
  ComposeFstImplOptions<SortedMatcher<F>, PM> impl_opts(base_opts);

  // the false below is something called phi_loop which is something I don't
  // fully understand, but I don't think we want it.

  // These pointers are taken ownership of, by ComposeFst.
  PM *phi_matcher =
      new PM(fst2, MATCH_INPUT, phi_label, false);
  SortedMatcher<F> *sorted_matcher =
      new SortedMatcher<F>(fst1, MATCH_NONE); // tell it
  // not to use this matcher, as this would mean we would
  // not follow phi transitions.
  impl_opts.matcher1 = sorted_matcher;
  impl_opts.matcher2 = phi_matcher;
  *ofst = ComposeFst<Arc>(fst1, fst2, impl_opts);
  Connect(ofst);
}

Plus() [1/5]

ArcticWeightTpl<T> fst::Plus ( const ArcticWeightTpl< T > &  w1, const ArcticWeightTpl< T > &  w2  )

inline

Definition at line 87 of file arctic-weight.h.

                                                               {
  return w1.Value() > w2.Value() ? w1 : w2;
}

Plus() [2/5]

ArcticWeightTpl<float> fst::Plus ( const ArcticWeightTpl< float > &  w1, const ArcticWeightTpl< float > &  w2  )

inline

Definition at line 92 of file arctic-weight.h.

                                                                       {
  return Plus<float>(w1, w2);
}

Plus() [3/5]

ArcticWeightTpl<double> fst::Plus ( const ArcticWeightTpl< double > &  w1, const ArcticWeightTpl< double > &  w2  )

inline

Definition at line 97 of file arctic-weight.h.

                                                                         {
  return Plus<double>(w1, w2);
}

Plus() [4/5]

LatticeWeightTpl<FloatType> fst::Plus ( const LatticeWeightTpl< FloatType > &  w1, const LatticeWeightTpl< FloatType > &  w2  )

inline

Definition at line 311 of file lattice-weight.h.

References Compare().

Referenced by DeterminizerStar< F >::EpsilonClosure::AddOneElement(), CompactLatticeWeightTest(), DeterminizerStar< F >::EpsilonClosure::GetEpsilonClosure(), IsStochasticFst(), LatticeWeightTest(), LatticeDeterminizerPruned< Weight, IntType >::NormalizeSubset(), LatticeDeterminizer< Weight, IntType >::NormalizeSubset(), ReweightPlusDefault< Weight >::operator()(), ReweightPlusLogArc::operator()(), CompactLatticeWeightCommonDivisorTpl< BaseWeightType, IntType >::operator()(), LatticePhoneAligner::ProcessFinal(), LatticeWordAligner::ProcessFinal(), DeterminizerStar< F >::ProcessFinal(), DeterminizerStar< F >::ProcessTransition(), PushCompactLatticeWeights(), RemoveEpsLocalClass< Arc, ReweightPlus >::RemoveEpsPattern1(), RemoveEpsLocalClass< Arc, ReweightPlus >::RemoveEpsPattern2(), LatticeIncrementalDeterminizer::SetFinalCosts(), kaldi::TestPushCompactLatticeWeights(), TestRemoveEpsLocalSpecial(), and kaldi::UnitTestAddOuterProductPlusMinus().

                                                                               {
  return (Compare(w1, w2) >= 0 ? w1 : w2);
}

Plus() [5/5]

CompactLatticeWeightTpl<WeightType, IntType> fst::Plus ( const CompactLatticeWeightTpl< WeightType, IntType > &  w1, const CompactLatticeWeightTpl< WeightType, IntType > &  w2  )

inline

Definition at line 664 of file lattice-weight.h.

References Compare().

                                                            {
  return (Compare(w1, w2) >= 0 ? w1 : w2);
}

PrecedingInputSymbolsAreSame()

bool PrecedingInputSymbolsAreSame	(	bool	start_is_epsilon,
		const Fst< Arc > &	fst
	)

Returns true if and only if the FST is such that the input symbols on arcs entering any given state all have the same value.

if "start_is_epsilon", treat start-state as an epsilon input arc [i.e. ensure only epsilon can enter start-state].

Definition at line 460 of file fstext-utils-inl.h.

References PrecedingInputSymbolsAreSameClass().

Referenced by MinimizeEncoded(), and TestMakeSymbolsSame().

                                                                              {
  IdentityFunction<typename Arc::Label> f;
  return PrecedingInputSymbolsAreSameClass(start_is_epsilon, fst, f);
}

PrecedingInputSymbolsAreSameClass()

bool PrecedingInputSymbolsAreSameClass	(	bool	start_is_epsilon,
		const Fst< Arc > &	fst,
		const F &