All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
fst Namespace Reference

Namespaces

 pre_determinize_helpers
 

Classes

class  ArcIterator< ContextFst< A > >
 
class  ArcIterator< TrivialFactorWeightFst< A, F > >
 
class  ArcticWeightTpl
 
class  BackoffDeterministicOnDemandFst
 This class wraps a conventional Fst, representing a language model, in the interface for "BackoffDeterministicOnDemandFst". More...
 
class  CacheDeterministicOnDemandFst
 
class  CompactLatticeMinimizer
 
class  CompactLatticePusher
 
class  CompactLatticeWeightCommonDivisorTpl
 
class  CompactLatticeWeightTpl
 
class  ComposeDeterministicOnDemandFst
 
class  ContextFst
 
class  ContextFstImpl
 
class  ContextMatcher
 
class  DeterministicOnDemandFst
 class DeterministicOnDemandFst is an "FST-like" base-class. More...
 
struct  DeterminizeLatticeOptions
 
struct  DeterminizeLatticePhonePrunedOptions
 
struct  DeterminizeLatticePrunedOptions
 
class  DeterminizerStar
 
class  DfsOrderVisitor
 
struct  IdentityFunction
 
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< FloatType >, IntType > >
 
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  StateIterator< ContextFst< A > >
 
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
 FactorWeightFst takes as template parameter a FactorIterator as defined above. More...
 
class  TrivialFactorWeightFstImpl
 
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
}
 

Functions

template<class Arc >
void AddSubsequentialLoop (typename Arc::Label subseq_symbol, MutableFst< Arc > *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...
 
template<class I >
void WriteILabelInfo (std::ostream &os, bool binary, const vector< vector< I > > &info)
 Useful utility function for writing these vectors to disk. More...
 
template<class I >
void ReadILabelInfo (std::istream &is, bool binary, vector< vector< I > > *info)
 Useful utility function for reading these vectors from disk. More...
 
template<class I >
SymbolTable * CreateILabelInfoSymbolTable (const vector< vector< I > > &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 vector< int32 > &disambig_syms, int N, int P, VectorFst< StdArc > *ifst, VectorFst< StdArc > *ofst, vector< vector< int32 > > *ilabels_out)
 Used in the command-line tool fstcomposecontext. More...
 
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)
 
template<class Arc >
static void TestContextFst (bool verbose, bool use_matcher)
 
template<class Arc , class LabelT >
void ComposeContextFst (const ContextFst< Arc, LabelT > &ifst1, const Fst< Arc > &ifst2, MutableFst< Arc > *ofst, const ComposeOptions &opts=ComposeOptions())
 
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 (string strFilename)
 
StdVectorFstCreateBackoffFst ()
 
StdVectorFstCreateResultFst ()
 
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, 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, vector< 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 vector< 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 vector< 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 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, 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, 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 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 vector< I > &symbol_mapping, MutableFst< Arc > *fst)
 
template<class Arc , class I >
bool GetLinearSymbolSequence (const Fst< Arc > &fst, vector< I > *isymbols_out, vector< I > *osymbols_out, typename Arc::Weight *tot_weight_out)
 GetLinearSymbolSequence gets the symbol sequence from a linear FST. More...
 
template<class Arc , class I >
bool GetLinearSymbolSequences (const Fst< Arc > &fst, vector< vector< I > > *isymbols_out, vector< vector< I > > *osymbols_out, vector< typename Arc::Weight > *tot_weight_out)
 GetLinearSymbolSequence gets the symbol sequences and weights from an FST as output by the ShortestPath algorithm (called with some parameter n), which has up to n arcs out from the start state, and if you follow one of the arcs you enter a linear sequence of states. More...
 
template<class Arc >
void ConvertNbestToVector (const Fst< Arc > &fst, 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 vector of separate FSTs. More...
 
template<class Arc >
void NbestAsFsts (const Fst< Arc > &fst, size_t n, 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 vector< 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 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, 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 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 VectorFst< StdArc > &fst, float delta, StdArc::Weight *min_sum, StdArc::Weight *max_sum)
 Tests whether a tropical FST is stochastic in the log semiring (casts it and does the check.) More...
 
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)
 
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)
 
void ReadFstKaldi (std::string rxfilename, fst::StdVectorFst *ofst)
 
void WriteFstKaldi (const VectorFst< StdArc > &fst, std::string wxfilename)
 
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 vector< 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...
 
vector< vector< double > > DefaultLatticeScale ()
 Returns a default 2x2 matrix scaling factor for LatticeWeight. More...
 
vector< vector< double > > AcousticLatticeScale (double acwt)
 
vector< vector< double > > GraphLatticeScale (double lmwt)
 
vector< 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 >
ostream & operator<< (ostream &strm, const LatticeWeightTpl< FloatType > &w)
 
template<class FloatType >
istream & operator>> (istream &strm, LatticeWeightTpl< FloatType > &w)
 
template<class FloatType , class ScaleFloatType >
LatticeWeightTpl< FloatType > ScaleTupleWeight (const LatticeWeightTpl< FloatType > &w, const vector< vector< ScaleFloatType > > &scale)
 
template<class FloatType , class ScaleFloatType >
PairWeight< TropicalWeightTpl
< FloatType >
, TropicalWeightTpl< FloatType > > 
ScaleTupleWeight (const PairWeight< TropicalWeightTpl< FloatType >, TropicalWeightTpl< FloatType > > &w, const vector< 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 >
ostream & operator<< (ostream &strm, const CompactLatticeWeightTpl< WeightType, IntType > &w)
 
template<class WeightType , class IntType >
istream & operator>> (istream &strm, CompactLatticeWeightTpl< WeightType, IntType > &w)
 
template<class Weight , class IntType , class ScaleFloatType >
CompactLatticeWeightTpl
< Weight, IntType > 
ScaleTupleWeight (const CompactLatticeWeightTpl< Weight, IntType > &w, const vector< 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, vector< Int > *symsOut)
 
template<class Label >
void CreateNewSymbols (SymbolTable *input_sym_table, int nSym, std::string prefix, vector< Label > *symsOut)
 
template<class Arc >
void AddSelfLoops (MutableFst< Arc > *fst, vector< typename Arc::Label > &isyms, 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, 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<typename L >
bool ContextExpandLeaves (const kaldi::ContextDependencyInterface &ctx_dep, const vector< L > &phones, const vector< L > &disambig_syms, const vector< vector< L > > &symbol_map_in, vector< vector< L > > *symbol_map_out, vector< L > *aug_to_leaf_out, vector< L > *aug_to_phone_out)
 ContextExpandLeaves transforms the sequences of phones on the input of C, into sequences of states. More...
 
template<class Arc >
void DfsSort (MutableFst< Arc > *fst)
 DfsSort sorts the states in an FST in depth-first-search order. More...
 
template<class Arc >
VectorFst< Arc > * MakeRemapper (const SymbolTable *isymbols, const SymbolTable *osymbols)
 The following function doesn't exactly belong here. 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 ()
 
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)
 
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)
 
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)
 

Typedef Documentation

typedef ArcticWeightTpl<float> ArcticWeight

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

typedef float BaseFloat

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

typedef fst::StdArc::Label Label

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

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

typedef fst::StdArc::StateId StateId

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

typedef unsigned char StatePropertiesType

Definition at line 122 of file factor.h.

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

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

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

typedef fst::StdArc::Weight Weight

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

Enumeration Type Documentation

anonymous enum
Enumerator
kStateHasEpsilonArcsEntering 
kStateHasNonEpsilonArcsEntering 
kStateHasEpsilonArcsLeaving 
kStateHasNonEpsilonArcsLeaving 

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

Enumerator
kStateFinal 
kStateInitial 
kStateArcsIn 
kStateMultipleArcsIn 
kStateArcsOut 
kStateMultipleArcsOut 
kStateOlabelsOut 
kStateIlabelsOut 

Definition at line 112 of file factor.h.

Function Documentation

vector<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::DecodeUtteranceLatticeSimple(), main(), DeterminizeLatticeTask::operator()(), DecodeUtteranceLatticeFasterClass::operator()(), and DiscriminativeSupervisionSplitter::PrepareLattice().

138  {
139  vector<vector<double> > ans(2);
140  ans[0].resize(2, 0.0);
141  ans[1].resize(2, 0.0);
142  ans[0][0] = 1.0;
143  ans[1][1] = acwt;
144  return ans;
145 }
void AddSelfLoops ( MutableFst< Arc > *  fst,
vector< typename Arc::Label > &  isyms,
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().

600  {
601  assert(fst != NULL);
602  assert(isyms.size() == osyms.size());
603  typedef typename Arc::Label Label;
604  typedef typename Arc::StateId StateId;
605  typedef typename Arc::Weight Weight;
606  size_t n = isyms.size();
607  if (n == 0) return; // Nothing to do.
608 
609  // {
610  // the following declarations and statements are for quick detection of these
611  // symbols, which is purely for debugging/checking purposes.
612  Label isyms_min = *std::min_element(isyms.begin(), isyms.end()),
613  isyms_max = *std::max_element(isyms.begin(), isyms.end()),
614  osyms_min = *std::min_element(osyms.begin(), osyms.end()),
615  osyms_max = *std::max_element(osyms.begin(), osyms.end());
616  std::set<Label> isyms_set, osyms_set;
617  for (size_t i = 0;i < isyms.size();i++) {
618  assert(isyms[i] > 0 && osyms[i] > 0); // should not have epsilon or invalid symbols.
619  isyms_set.insert(isyms[i]);
620  osyms_set.insert(osyms[i]);
621  }
622  assert(isyms_set.size() == n && osyms_set.size() == n);
623  // } end block.
624 
625  for (StateIterator<MutableFst<Arc> > siter(*fst); ! siter.Done(); siter.Next()) {
626  StateId state = siter.Value();
627  bool this_state_needs_self_loops = (fst->Final(state) != Weight::Zero());
628  for (ArcIterator<MutableFst<Arc> > aiter(*fst, state); ! aiter.Done(); aiter.Next()) {
629  const Arc &arc = aiter.Value();
630  // If one of the following asserts fails, it means that the input FST already had the symbols
631  // we are inserting. This is contrary to the preconditions of this algorithm.
632  assert(!(arc.ilabel>=isyms_min && arc.ilabel<=isyms_max && isyms_set.count(arc.ilabel) != 0));
633  assert(!(arc.olabel>=osyms_min && arc.olabel<=osyms_max && osyms_set.count(arc.olabel) != 0));
634  if (arc.olabel != 0) // Has non-epsilon output label -> need self loops.
635  this_state_needs_self_loops = true;
636  }
637  if (this_state_needs_self_loops) {
638  for (size_t i = 0;i < n;i++) {
639  Arc arc;
640  arc.ilabel = isyms[i];
641  arc.olabel = osyms[i];
642  arc.weight = Weight::One();
643  arc.nextstate = state;
644  fst->AddArc(state, arc);
645  }
646  }
647  }
648 }
fst::StdArc::StateId StateId
Definition: graph.dox:21
struct rnnlm::@11::@12 n
fst::StdArc::Label Label
fst::StdArc::Weight Weight
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 841 of file fstext-utils-inl.h.

Referenced by kaldi::GetHmmAsFst(), and main().

841  {
842  typedef typename Arc::Weight Weight;
843  typedef typename Arc::StateId StateId;
844  for (StateIterator<MutableFst<Arc> > siter(*fst);
845  !siter.Done();
846  siter.Next()) {
847  StateId s = siter.Value();
848  for (MutableArcIterator<MutableFst<Arc> > aiter(fst, s);
849  !aiter.Done();
850  aiter.Next()) {
851  Arc arc = aiter.Value();
852  arc.weight = Weight(arc.weight.Value() * scale);
853  aiter.SetValue(arc);
854  }
855  if (fst->Final(s) != Weight::Zero())
856  fst->SetFinal(s, Weight(fst->Final(s).Value() * scale));
857  }
858 }
fst::StdArc::StateId StateId
Definition: graph.dox:21
fst::StdArc::Weight Weight
bool fst::ApproxEqual ( const LatticeWeightTpl< FloatType > &  w1,
const LatticeWeightTpl< FloatType > &  w2,
float  delta = kDelta 
)
inline
bool fst::ApproxEqual ( const CompactLatticeWeightTpl< WeightType, IntType > &  w1,
const CompactLatticeWeightTpl< WeightType, IntType > &  w2,
float  delta = kDelta 
)
inline

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

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

542  {
543  return (ApproxEqual(w1.Weight(), w2.Weight(), delta) && w1.String() == w2.String());
544 }
bool ApproxEqual(const CompactLatticeWeightTpl< WeightType, IntType > &w1, const CompactLatticeWeightTpl< WeightType, IntType > &w2, float delta=kDelta)
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 70 of file context-fst-test.cc.

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

75  {
76  typedef typename Arc::Label Label;
77  typedef typename Arc::StateId StateId;
78  typedef typename Arc::Weight Weight;
79 
80  assert(kaldi::IsSorted(phone_ids)); // so we can do binary_search.
81 
82 
83  vector<int32> input_syms;
84  vector<int32> output_syms;
85  Weight tot_cost;
86  bool ans = GetLinearSymbolSequence(linear_fst, &input_syms,
87  &output_syms, &tot_cost);
88  assert(ans); // should be linear.
89 
90  vector<int32> phone_seq_check;
91  for (size_t i = 0; i < output_syms.size(); i++)
92  if (std::binary_search(phone_ids.begin(), phone_ids.end(), output_syms[i]))
93  phone_seq_check.push_back(output_syms[i]);
94 
95  assert(phone_seq_check == phone_seq);
96 
97  vector<vector<int32> > input_syms_long;
98  for (size_t i = 0; i < input_syms.size(); i++) {
99  Label isym = input_syms[i];
100  if (ilabel_info[isym].size() == 0) continue; // epsilon.
101  if ( (ilabel_info[isym].size() == 1 &&
102  ilabel_info[isym][0] <= 0) ) continue; // disambig.
103  input_syms_long.push_back(ilabel_info[isym]);
104  }
105 
106  for (size_t i = 0; i < input_syms_long.size(); i++) {
107  vector<int32> phone_context_window(N); // phone at pos i will be at pos P in this window.
108  int pos = ((int)i) - P; // pos of first phone in window [ may be out of range] .
109  for (int j = 0; j < N; j++, pos++) {
110  if (static_cast<size_t>(pos) < phone_seq.size()) phone_context_window[j] = phone_seq[pos];
111  else phone_context_window[j] = 0; // 0 is a special symbol that context-dep-itf expects to see
112  // when no phone is present due to out-of-window. context-fst knows about this too.
113  }
114  assert(input_syms_long[i] == phone_context_window);
115  }
116  return tot_cost.Value();
117 }
fst::StdArc::StateId StateId
bool GetLinearSymbolSequence(const Fst< Arc > &fst, vector< I > *isymbols_out, vector< I > *osymbols_out, typename Arc::Weight *tot_weight_out)
GetLinearSymbolSequence gets the symbol sequence from a linear FST.
fst::StdArc::Label Label
fst::StdArc::Weight Weight
bool IsSorted(const std::vector< T > &vec)
Returns true if the vector is sorted.
Definition: stl-utils.h:59
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 812 of file fstext-utils-inl.h.

Referenced by MakeLoopFstCompare().

814  {
815  for (StateIterator<MutableFst<Arc> > siter(*fst);
816  !siter.Done();
817  siter.Next()) {
818  typename Arc::StateId s = siter.Value();
819  for (MutableArcIterator<MutableFst<Arc> > aiter(fst, s);
820  !aiter.Done();
821  aiter.Next()) {
822  Arc arc = aiter.Value();
823  bool change = false;
824  if (clear_input && arc.ilabel != 0) {
825  arc.ilabel = 0;
826  change = true;
827  }
828  if (clear_output && arc.olabel != 0) {
829  arc.olabel = 0;
830  change = true;
831  }
832  if (change) {
833  aiter.SetValue(arc);
834  }
835  }
836  }
837 }
fst::StdArc::StateId StateId
Definition: graph.dox:21
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.

245  {
246  typedef CompactLatticeWeightTpl<Weight, Int> W;
247  typedef ArcTpl<W> Arc;
248  typedef ExpandedFst<Arc> Fst;
249  typedef typename Arc::StateId StateId;
250  StateId num_states = fst.NumStates();
251  for (StateId s = 0; s < num_states; s++) {
252  for (ArcIterator<Fst> aiter(fst, s);
253  !aiter.Done();
254  aiter.Next()) {
255  const Arc &arc = aiter.Value();
256  if (!arc.weight.String().empty()) return true;
257  }
258  W final_weight = fst.Final(s);
259  if (!final_weight.String().empty()) return true;
260  }
261  return false;
262 }
fst::StdArc::StateId StateId
Definition: graph.dox:21
void fst::CompactLatticeWeightTest ( )

Definition at line 123 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().

123  {
124  for(int32 i = 0; i < 100; i++) {
126  CompactLatticeWeight l3 = Plus(l1, l2);
127  CompactLatticeWeight l4 = Times(l1, l2);
128 
129  KALDI_ASSERT(Plus(l3, l3) == l3);
130  KALDI_ASSERT(Plus(l1, l2) == Plus(l2, l1)); // commutativity of plus
131  KALDI_ASSERT(Plus(l3, CompactLatticeWeight::Zero()) == l3); // x + 0 = x
132  KALDI_ASSERT(Times(l3, CompactLatticeWeight::One()) == l3); // x * 1 = x
133  KALDI_ASSERT(Times(l3, CompactLatticeWeight::Zero()) == CompactLatticeWeight::Zero()); // x * 0 = 0
134  NaturalLess<CompactLatticeWeight> nl;
135  bool a = nl(l1, l2);
136  bool b = (Plus(l1, l2) == l1 && l1 != l2);
137  KALDI_ASSERT(a == b);
138 
139  KALDI_ASSERT(Compare(l1, Plus(l1, l2)) != 1); // so do not have l1 > l1 + l2
141  KALDI_ASSERT(Times(Plus(l1, l2), Plus(l5, l6)) ==
142  Plus(Times(l1, l5), Plus(Times(l1, l6),
143  Plus(Times(l2, l5), Times(l2, l6))))); // * distributes over +
144  KALDI_ASSERT(l1.Member() && l2.Member() && l3.Member() && l4.Member()
145  && l5.Member() && l6.Member());
146  if (l2 != CompactLatticeWeight::Zero()) {
147  KALDI_ASSERT(ApproxEqual(Divide(Times(l1, l2), l2, DIVIDE_RIGHT), l1)); // (a*b) / b = a if b != 0
148  KALDI_ASSERT(ApproxEqual(Divide(Times(l2, l1), l2, DIVIDE_LEFT), l1)); // (a*b) / b = a if b != 0
149  }
150  KALDI_ASSERT(ApproxEqual(l1, l1.Quantize()));
151 
152  std::ostringstream s1;
153  s1 << l1;
154  std::istringstream s2(s1.str());
155  s2 >> l2;
156  KALDI_ASSERT(ApproxEqual(l1, l2));
157  std::cout << s1.str() << '\n';
158 
159  {
160  std::ostringstream s1b;
161  l1.Write(s1b);
162  std::istringstream s2b(s1b.str());
163  l3.Read(s2b);
164  KALDI_ASSERT(l1 == l3);
165  }
166 
168  std::cout << "l5 = " << l5 << '\n';
169  std::cout << "l6 = " << l6 << '\n';
170  l1 = divisor(l5, l6);
171  std::cout << "div = " << l1 << '\n';
172  if (l1 != CompactLatticeWeight::Zero()) {
173  l2 = Divide(l5, l1, DIVIDE_LEFT);
174  l3 = Divide(l6, l1, DIVIDE_LEFT);
175  std::cout << "l2 = " << l2 << '\n';
176  std::cout << "l3 = " << l3 << '\n';
177  l4 = divisor(l2, l3); // make sure l2 is now one.
178  std::cout << "l4 = " << l4 << '\n';
179  KALDI_ASSERT(ApproxEqual(l4, CompactLatticeWeight::One()));
180  } else {
181  KALDI_ASSERT(l5 == CompactLatticeWeight::Zero()
182  && l6 == CompactLatticeWeight::Zero());
183  }
184  }
185 }
CompactLatticeWeight RandomCompactLatticeWeight()
LatticeWeightTpl< FloatType > Divide(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2, DivideType typ=DIVIDE_ANY)
LatticeWeightTpl< FloatType > Plus(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2)
LatticeWeightTpl< FloatType > Times(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2)
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.
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
static bool ApproxEqual(float a, float b, float relative_tolerance=0.001)
return abs(a - b) <= relative_tolerance * (abs(a)+abs(b)).
Definition: kaldi-math.h:262
CompactLatticeWeightTpl< LatticeWeight, int32 > CompactLatticeWeight
CompactLatticeWeightCommonDivisorTpl< LatticeWeight, int32 > CompactLatticeWeightCommonDivisor
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 295 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(), LatticeDeterminizerPruned< Weight, IntType >::MakeSubsetUnique(), LatticeDeterminizer< Weight, IntType >::MakeSubsetUnique(), NaturalLess< LatticeWeightTpl< FloatType > >::operator()(), NaturalLess< CompactLatticeWeightTpl< LatticeWeightTpl< FloatType >, IntType > >::operator()(), PruneSpecialClass< Arc >::Task::operator<(), Plus(), LatticeDeterminizerPruned< Weight, IntType >::ProcessFinal(), LatticeDeterminizer< Weight, IntType >::ProcessFinal(), and PruneSpecialClass< Arc >::ProcessState().

296  {
297  FloatType f1 = w1.Value1() + w1.Value2(),
298  f2 = w2.Value1() + w2.Value2();
299  if (f1 < f2) { return 1; } // having smaller cost means you're larger
300  // in the semiring [higher probability]
301  else if (f1 > f2) { return -1; }
302  // mathematically we should be comparing (w1.value1_-w1.value2_ < w2.value1_-w2.value2_)
303  // in the next line, but add w1.value1_+w1.value2_ = w2.value1_+w2.value2_ to both sides and
304  // divide by two, and we get the simpler equivalent form w1.value1_ < w2.value1_.
305  else if (w1.Value1() < w2.Value1()) { return 1; }
306  else if (w1.Value1() > w2.Value1()) { return -1; }
307  else { return 0; }
308 }
int fst::Compare ( const CompactLatticeWeightTpl< WeightType, IntType > &  w1,
const CompactLatticeWeightTpl< WeightType, IntType > &  w2 
)
inline

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

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

562  {
563  int c1 = Compare(w1.Weight(), w2.Weight());
564  if (c1 != 0) return c1;
565  int l1 = w1.String().size(), l2 = w2.String().size();
566  // Use opposite order on the string lengths, so that if the costs are the same,
567  // the shorter string wins.
568  if (l1 > l2) return -1;
569  else if (l1 < l2) return 1;
570  for(int i = 0; i < l1; i++) {
571  if (w1.String()[i] < w2.String()[i]) return -1;
572  else if (w1.String()[i] > w2.String()[i]) return 1;
573  }
574  return 0;
575 }
int Compare(const TropicalWeight &w1, const TropicalWeight &w2)
int fst::Compare ( const TropicalWeight &  w1,
const TropicalWeight &  w2 
)
inline

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

593  {
594  float f1 = w1.Value(), f2 = w2.Value();
595  if (f1 == f2) return 0;
596  else if (f1 > f2) return -1;
597  else return 1;
598 }
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 EnsureEpsilonProperty(), and TestEnsureEpsilonProperty().

29  {
30  typedef typename Arc::StateId StateId;
31  typedef VectorFst<Arc> Fst;
32  epsilon_info->clear();
33  epsilon_info->resize(fst.NumStates(), static_cast<char>(0));
34  for (StateId s = 0; s < fst.NumStates(); s++) {
35  for (ArcIterator<Fst> aiter(fst, s); !aiter.Done(); aiter.Next()) {
36  const Arc &arc = aiter.Value();
37  if (arc.ilabel == 0 && arc.olabel == 0) {
38  (*epsilon_info)[arc.nextstate] |= static_cast<char>(kStateHasEpsilonArcsEntering);
39  (*epsilon_info)[s] |= static_cast<char>(kStateHasEpsilonArcsLeaving);
40  } else {
41  (*epsilon_info)[arc.nextstate] |= static_cast<char>(kStateHasNonEpsilonArcsEntering);
42  (*epsilon_info)[s] |= static_cast<char>(kStateHasNonEpsilonArcsLeaving);
43  }
44  }
45  }
46 }
fst::StdArc::StateId StateId
Definition: graph.dox:21
bool fst::ContextExpandLeaves ( const kaldi::ContextDependencyInterface ctx_dep,
const vector< L > &  phones,
const vector< L > &  disambig_syms,
const vector< vector< L > > &  symbol_map_in,
vector< vector< L > > *  symbol_map_out,
vector< L > *  aug_to_leaf_out,
vector< L > *  aug_to_phone_out 
)

ContextExpandLeaves transforms the sequences of phones on the input of C, into sequences of states.

However it outputs the new symbols as "mangled" state-names that contain sufficient information to obtain the phone ids. ctx_dep [in] object that

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.

268  {
269  int32 num_states_cache = 50000;
270  CacheOptions cache_opts(true, num_states_cache);
271  StdToLatticeMapper<Real> mapper;
272  MapFst<StdArc, ArcTpl<LatticeWeightTpl<Real> >,
273  StdToLatticeMapper<Real> > map_fst(ifst, mapper, cache_opts);
274  *ofst = map_fst;
275 }
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(), DiscriminativeExampleSplitter::DoExcise(), kaldi::nnet2::ExampleToPdfPost(), NnetDiscriminativeUpdater::LatticeComputations(), main(), MinimumBayesRisk::MinimumBayesRisk(), DiscriminativeExampleSplitter::PrepareLattice(), kaldi::RandCompactLattice(), kaldi::SentenceLevelConfidence(), kaldi::TestCompactLatticeTableCross(), TestConvert2(), kaldi::TestLatticeTableCross(), kaldi::TestWordAlignedLattice(), and kaldi::TestWordAlignLatticeLexicon().

36  {
37  typedef ArcTpl<Weight> Arc;
38  typedef typename Arc::StateId StateId;
39  typedef CompactLatticeWeightTpl<Weight, Int> CompactWeight;
40  typedef ArcTpl<CompactWeight> CompactArc;
41 
42  VectorFst<ArcTpl<Weight> > ffst;
43  vector<vector<Int> > labels;
44  if (invert) // normal case: want the ilabels as sequences on the arcs of
45  Factor(ifst, &ffst, &labels); // the output... Factor makes seqs of
46  // ilabels.
47  else {
48  VectorFst<ArcTpl<Weight> > invfst(ifst);
49  Invert(&invfst);
50  Factor(invfst, &ffst, &labels);
51  }
52 
53  TopSort(&ffst); // Put the states in ffst in topological order, which is
54  // easier on the eye when reading the text-form lattices and corresponds to
55  // what we get when we generate the lattices in the decoder.
56 
57  ofst->DeleteStates();
58 
59  // The states will be numbered exactly the same as the original FST.
60  // Add the states to the new FST.
61  StateId num_states = ffst.NumStates();
62  for (StateId s = 0; s < num_states; s++) {
63  StateId news = ofst->AddState();
64  assert(news == s);
65  }
66  ofst->SetStart(ffst.Start());
67  for (StateId s = 0; s < num_states; s++) {
68  Weight final_weight = ffst.Final(s);
69  if (final_weight != Weight::Zero()) {
70  CompactWeight final_compact_weight(final_weight, vector<Int>());
71  ofst->SetFinal(s, final_compact_weight);
72  }
73  for (ArcIterator<ExpandedFst<Arc> > iter(ffst, s);
74  !iter.Done();
75  iter.Next()) {
76  const Arc &arc = iter.Value();
77  KALDI_PARANOID_ASSERT(arc.weight != Weight::Zero());
78  // note: zero-weight arcs not allowed anyway so weight should not be zero,
79  // but no harm in checking.
80  CompactArc compact_arc(arc.olabel, arc.olabel,
81  CompactWeight(arc.weight, labels[arc.ilabel]),
82  arc.nextstate);
83  ofst->AddArc(s, compact_arc);
84  }
85  }
86 }
fst::StdArc::StateId StateId
void Factor(const Fst< Arc > &fst, MutableFst< Arc > *ofst, vector< vector< I > > *symbols_out)
Factor identifies linear chains of states with an olabel (if any) only on the first arc of the chain...
Definition: factor-inl.h:69
#define KALDI_PARANOID_ASSERT(cond)
Definition: kaldi-error.h:182
fst::StdArc::Weight Weight
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().

88  {
89  VectorFst<ArcTpl<CompactLatticeWeightTpl<LatticeWeightTpl<float>, Int> > > fst;
90  ConvertLattice(ifst, &fst);
91  ConvertLattice(fst, ofst);
92 }
void ConvertLattice(const ExpandedFst< ArcTpl< CompactLatticeWeightTpl< LatticeWeightTpl< float >, Int > > > &ifst, MutableFst< ArcTpl< LatticeWeightTpl< double > > > *ofst)
Converts CompactLattice with float to Lattice with double.
Definition: graph.dox:21
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().

92  {
93  typedef ArcTpl<Weight> Arc;
94  typedef typename Arc::StateId StateId;
95  typedef typename Arc::Label Label;
96  typedef CompactLatticeWeightTpl<Weight, Int> CompactWeight;
97  typedef ArcTpl<CompactWeight> CompactArc;
98  ofst->DeleteStates();
99  // make the states in the new FST have the same numbers as
100  // the original ones, and add chains of states as necessary
101  // to encode the string-valued weights.
102  StateId num_states = ifst.NumStates();
103  for (StateId s = 0; s < num_states; s++) {
104  StateId news = ofst->AddState();
105  assert(news == s);
106  }
107  ofst->SetStart(ifst.Start());
108  for (StateId s = 0; s < num_states; s++) {
109  CompactWeight final_weight = ifst.Final(s);
110  if (final_weight != CompactWeight::Zero()) {
111  StateId cur_state = s;
112  size_t string_length = final_weight.String().size();
113  for (size_t n = 0; n < string_length; n++) {
114  StateId next_state = ofst->AddState();
115  Label ilabel = 0;
116  Arc arc(ilabel, final_weight.String()[n],
117  (n == 0 ? final_weight.Weight() : Weight::One()),
118  next_state);
119  if (invert) std::swap(arc.ilabel, arc.olabel);
120  ofst->AddArc(cur_state, arc);
121  cur_state = next_state;
122  }
123  ofst->SetFinal(cur_state,
124  string_length > 0 ? Weight::One() : final_weight.Weight());
125  }
126  for (ArcIterator<ExpandedFst<CompactArc> > iter(ifst, s);
127  !iter.Done();
128  iter.Next()) {
129  const CompactArc &arc = iter.Value();
130  size_t string_length = arc.weight.String().size();
131  StateId cur_state = s;
132  // for all but the last element in the string--
133  // add a temporary state.
134  for (size_t n = 0 ; n+1 < string_length; n++) {
135  StateId next_state = ofst->AddState();
136  Label ilabel = (n == 0 ? arc.ilabel : 0),
137  olabel = static_cast<Label>(arc.weight.String()[n]);
138  Weight weight = (n == 0 ? arc.weight.Weight() : Weight::One());
139  Arc new_arc(ilabel, olabel, weight, next_state);
140  if (invert) std::swap(new_arc.ilabel, new_arc.olabel);
141  ofst->AddArc(cur_state, new_arc);
142  cur_state = next_state;
143  }
144  Label ilabel = (string_length <= 1 ? arc.ilabel : 0),
145  olabel = (string_length > 0 ? arc.weight.String()[string_length-1] : 0);
146  Weight weight = (string_length <= 1 ? arc.weight.Weight() : Weight::One());
147  Arc new_arc(ilabel, olabel, weight, arc.nextstate);
148  if (invert) std::swap(new_arc.ilabel, new_arc.olabel);
149  ofst->AddArc(cur_state, new_arc);
150  }
151  }
152 }
fst::StdArc::StateId StateId
void swap(basic_filebuf< CharT, Traits > &x, basic_filebuf< CharT, Traits > &y)
struct rnnlm::@11::@12 n
fst::StdArc::Label Label
fst::StdArc::Weight Weight
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().

97  {
98  VectorFst<ArcTpl<CompactLatticeWeightTpl<LatticeWeightTpl<double>, Int> > > fst;
99  ConvertLattice(ifst, &fst);
100  ConvertLattice(fst, ofst);
101 }
void ConvertLattice(const ExpandedFst< ArcTpl< CompactLatticeWeightTpl< LatticeWeightTpl< float >, Int > > > &ifst, MutableFst< ArcTpl< LatticeWeightTpl< double > > > *ofst)
Converts CompactLattice with float to Lattice with double.
Definition: graph.dox:21
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().

106  {
107  VectorFst<ArcTpl<CompactLatticeWeightTpl<LatticeWeightTpl<float>, Int> > > fst;
108  ConvertLattice(ifst, &fst);
109  ConvertLattice(fst, ofst);
110 }
void ConvertLattice(const ExpandedFst< ArcTpl< CompactLatticeWeightTpl< LatticeWeightTpl< float >, Int > > > &ifst, MutableFst< ArcTpl< LatticeWeightTpl< double > > > *ofst)
Converts CompactLattice with float to Lattice with double.
Definition: graph.dox:21
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 ConvertLattice().

115  {
116  VectorFst<ArcTpl<CompactLatticeWeightTpl<LatticeWeightTpl<double>, Int> > > fst;
117  ConvertLattice(ifst, &fst);
118  ConvertLattice(fst, ofst);
119 }
void ConvertLattice(const ExpandedFst< ArcTpl< CompactLatticeWeightTpl< LatticeWeightTpl< float >, Int > > > &ifst, MutableFst< ArcTpl< LatticeWeightTpl< double > > > *ofst)
Converts CompactLattice with float to Lattice with double.
Definition: graph.dox:21
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.

159  {
160  typedef ArcTpl<WeightIn> ArcIn;
161  typedef ArcTpl<WeightOut> ArcOut;
162  typedef typename ArcIn::StateId StateId;
163  ofst->DeleteStates();
164  // The states will be numbered exactly the same as the original FST.
165  // Add the states to the new FST.
166  StateId num_states = ifst.NumStates();
167  for (StateId s = 0; s < num_states; s++) {
168  StateId news = ofst->AddState();
169  assert(news == s);
170  }
171  ofst->SetStart(ifst.Start());
172  for (StateId s = 0; s < num_states; s++) {
173  WeightIn final_iweight = ifst.Final(s);
174  if (final_iweight != WeightIn::Zero()) {
175  WeightOut final_oweight;
176  ConvertLatticeWeight(final_iweight, &final_oweight);
177  ofst->SetFinal(s, final_oweight);
178  }
179  for (ArcIterator<ExpandedFst<ArcIn> > iter(ifst, s);
180  !iter.Done();
181  iter.Next()) {
182  ArcIn arc = iter.Value();
183  KALDI_PARANOID_ASSERT(arc.weight != WeightIn::Zero());
184  ArcOut oarc;
185  ConvertLatticeWeight(arc.weight, &oarc.weight);
186  oarc.ilabel = arc.ilabel;
187  oarc.olabel = arc.olabel;
188  oarc.nextstate = arc.nextstate;
189  ofst->AddArc(s, oarc);
190  }
191  }
192 }
fst::StdArc::StateId StateId
void ConvertLatticeWeight(const LatticeWeightTpl< Float1 > &w_in, LatticeWeightTpl< Float2 > *w_out)
Define some ConvertLatticeWeight functions that are used in various lattice conversions...
#define KALDI_PARANOID_ASSERT(cond)
Definition: kaldi-error.h:182
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 758 of file lattice-weight.h.

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

Referenced by ConvertLattice().

760  {
761  w_out->SetValue1(w_in.Value1());
762  w_out->SetValue2(w_in.Value2());
763 }
void fst::ConvertLatticeWeight ( const CompactLatticeWeightTpl< LatticeWeightTpl< Float1 >, Int > &  w_in,
CompactLatticeWeightTpl< LatticeWeightTpl< Float2 >, Int > *  w_out 
)
inline

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

768  {
769  LatticeWeightTpl<Float2> weight2(w_in.Weight().Value1(),
770  w_in.Weight().Value2());
771  w_out->SetWeight(weight2);
772  w_out->SetString(w_in.String());
773 }
void fst::ConvertLatticeWeight ( const LatticeWeightTpl< Float1 > &  w_in,
TropicalWeightTpl< Float2 > *  w_out 
)
inline

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

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

779  {
780  TropicalWeightTpl<Float2> w1(w_in.Value1());
781  TropicalWeightTpl<Float2> w2(w_in.Value2());
782  *w_out = Times(w1, w2);
783 }
CompactLatticeWeightTpl< WeightType, IntType > Times(const CompactLatticeWeightTpl< WeightType, IntType > &w1, const CompactLatticeWeightTpl< WeightType, IntType > &w2)
void ConvertNbestToVector ( const Fst< Arc > &  fst,
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 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 291 of file fstext-utils-inl.h.

References KALDI_ASSERT.

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

292  {
293  typedef typename Arc::Weight Weight;
294  typedef typename Arc::StateId StateId;
295  fsts_out->clear();
296  StateId start_state = fst.Start();
297  if (start_state == kNoStateId) return; // No output.
298  size_t n_arcs = fst.NumArcs(start_state);
299  bool start_is_final = (fst.Final(start_state) != Weight::Zero());
300  fsts_out->reserve(n_arcs + (start_is_final ? 1 : 0));
301 
302  if (start_is_final) {
303  fsts_out->resize(fsts_out->size() + 1);
304  StateId start_state_out = fsts_out->back().AddState();
305  fsts_out->back().SetFinal(start_state_out, fst.Final(start_state));
306  }
307 
308  for (ArcIterator<Fst<Arc> > start_aiter(fst, start_state);
309  !start_aiter.Done();
310  start_aiter.Next()) {
311  fsts_out->resize(fsts_out->size() + 1);
312  VectorFst<Arc> &ofst = fsts_out->back();
313  const Arc &first_arc = start_aiter.Value();
314  StateId cur_state = start_state,
315  cur_ostate = ofst.AddState();
316  ofst.SetStart(cur_ostate);
317  StateId next_ostate = ofst.AddState();
318  ofst.AddArc(cur_ostate, Arc(first_arc.ilabel, first_arc.olabel,
319  first_arc.weight, next_ostate));
320  cur_state = first_arc.nextstate;
321  cur_ostate = next_ostate;
322  while (1) {
323  size_t this_n_arcs = fst.NumArcs(cur_state);
324  KALDI_ASSERT(this_n_arcs <= 1); // or it violates our assumptions
325  // about the input.
326  if (this_n_arcs == 1) {
327  KALDI_ASSERT(fst.Final(cur_state) == Weight::Zero());
328  // or problem with ShortestPath.
329  ArcIterator<Fst<Arc> > aiter(fst, cur_state);
330  const Arc &arc = aiter.Value();
331  next_ostate = ofst.AddState();
332  ofst.AddArc(cur_ostate, Arc(arc.ilabel, arc.olabel,
333  arc.weight, next_ostate));
334  cur_state = arc.nextstate;
335  cur_ostate = next_ostate;
336  } else {
337  KALDI_ASSERT(fst.Final(cur_state) != Weight::Zero());
338  // or problem with ShortestPath.
339  ofst.SetFinal(cur_ostate, fst.Final(cur_state));
340  break;
341  }
342  }
343  }
344 }
fst::StdArc::StateId StateId
fst::StdArc::Weight Weight
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
double fst::ConvertToCost ( const CompactLatticeWeightTpl< LatticeWeightTpl< Float >, Int > &  w)
inline

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

791  {
792  return static_cast<double>(w.Weight().Value1()) + static_cast<double>(w.Weight().Value2());
793 }
double fst::ConvertToCost ( const TropicalWeightTpl< Float > &  w)
inline

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

796  {
797  return w.Value();
798 }
StdVectorFst* fst::CreateBackoffFst ( )

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

Referenced by TestBackoffAndCache(), and TestCompose().

61  {
62  StdVectorFst *fst = new StdVectorFst();
63  fst->AddState(); // state 0
64  fst->SetStart(0);
65  fst->AddArc(0, StdArc(10, 10, 0.0, 1));
66 
67  fst->AddState(); // state 1
68  fst->AddArc(1, StdArc(12, 12, 0.0, 4));
69  fst->AddArc(1, StdArc(0,0, 0.1,2)); // backoff from 1 to 2
70 
71  fst->AddState(); // state 2
72  fst->AddArc(2, StdArc(13, 13, 0.2, 4));
73  fst->AddArc(2, StdArc(0,0, 0.3,3)); // backoff from 2 to 3
74 
75  fst->AddState(); // state 3
76  fst->AddArc(3, StdArc(14, 14, 0.4, 4));
77 
78  fst->AddState(); // state 4
79  fst->AddArc(4, StdArc(15, 15, 0.5, 5));
80 
81  fst->AddState(); // state 5
82  fst->SetFinal(5, 0.6);
83 
84  return fst;
85 }
Definition: graph.dox:21
fst::StdArc StdArc
fst::StdVectorFst StdVectorFst
void CreateFactorFst ( const vector< 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().

251  {
253  typedef typename Arc::StateId StateId;
254  typedef typename Arc::Label Label;
255  typedef typename Arc::Weight Weight;
256 
257  assert(fst != NULL);
258  fst->DeleteStates();
259  StateId loopstate = fst->AddState();
260  assert(loopstate == 0);
261  fst->SetStart(0);
262  fst->SetFinal(0, Weight::One());
263  if (sequences.size() != 0) assert(sequences[0].size() == 0); // can't replace epsilon...
264 
265  for (Label olabel = 1; olabel < static_cast<Label>(sequences.size()); olabel++) {
266  size_t len = sequences[olabel].size();
267  if (len == 0) {
268  Arc arc(0, olabel, Weight::One(), loopstate);
269  fst->AddArc(loopstate, arc);
270  } else {
271  StateId curstate = loopstate;
272  for (size_t i = 0; i < len; i++) {
273  StateId nextstate = (i == len-1 ? loopstate : fst->AddState());
274  Arc arc(sequences[olabel][i], (i == 0 ? olabel : 0), Weight::One(), nextstate);
275  fst->AddArc(curstate, arc);
276  curstate = nextstate;
277  }
278  }
279  }
280  fst->SetProperties(kOLabelSorted, kOLabelSorted);
281 }
fst::StdArc::StateId StateId
#define KALDI_ASSERT_IS_INTEGER_TYPE(I)
Definition: kaldi-utils.h:130
Definition: graph.dox:21
fst::StdArc::Label Label
fst::StdArc::Weight Weight
void CreateMapFst ( const 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().

286  {
288  typedef typename Arc::StateId StateId;
289  typedef typename Arc::Label Label;
290  typedef typename Arc::Weight Weight;
291 
292  assert(fst != NULL);
293  fst->DeleteStates();
294  StateId loopstate = fst->AddState();
295  assert(loopstate == 0);
296  fst->SetStart(0);
297  fst->SetFinal(0, Weight::One());
298  assert(symbol_map.empty() || symbol_map[0] == 0); // FST cannot map epsilon to something else.
299  for (Label olabel = 1; olabel < static_cast<Label>(symbol_map.size()); olabel++) {
300  Arc arc(symbol_map[olabel], olabel, Weight::One(), loopstate);
301  fst->AddArc(loopstate, arc);
302  }
303 }
fst::StdArc::StateId StateId
#define KALDI_ASSERT_IS_INTEGER_TYPE(I)
Definition: kaldi-utils.h:130
Definition: graph.dox:21
fst::StdArc::Label Label
fst::StdArc::Weight Weight
void CreateNewSymbols ( SymbolTable *  input_sym_table,
int  nSym,
std::string  prefix,
vector< Label > *  symsOut 
)

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

References rnnlm::i.

Referenced by TestAddSelfLoops().

582  {
583  // Creates nSym new symbols named (prefix)0, (prefix)1 and so on.
584  // Crashes if it cannot create them because one or more of them were in the symbol
585  // table already.
586  assert(symsOut && symsOut->size() == 0);
587  for (int i = 0;i < nSym;i++) {
588  std::stringstream ss; ss << prefix << i;
589  std::string str = ss.str();
590  if (input_sym_table->Find(str) != -1) { // should not be present.
591  }
592  assert(symsOut);
593  symsOut->push_back( (Label) input_sym_table->AddSymbol(str));
594  }
595 }
fst::StdArc::Label Label
StdVectorFst* fst::CreateResultFst ( )

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

Referenced by TestBackoffAndCache(), and TestCompose().

88  {
89  StdVectorFst *fst = new StdVectorFst();
90  fst->AddState(); // state 0
91  fst->SetStart(0);
92  fst->AddArc(0, StdArc(10, 10, 0.0, 1));
93 
94  fst->AddState(); // state 1
95  fst->AddArc(1, StdArc(12, 12, 0.0, 4));
96  fst->AddArc(1, StdArc(13,13,0.3,4)); // went through 1 backoff
97  fst->AddArc(1, StdArc(14,14,0.8,4)); // went through 2 backoffs
98 
99  fst->AddState(); // state 2
100  fst->AddState(); // state 3
101 
102  fst->AddState(); // state 4
103  fst->AddArc(4, StdArc(15, 15, 0.5, 5));
104 
105  fst->AddState(); // state 5
106  fst->SetFinal(5, 0.6);
107 
108  return fst;
109 }
Definition: graph.dox:21
fst::StdArc StdArc
fst::StdVectorFst StdVectorFst
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().

687  {
688  typedef typename Arc::StateId StateId;
689  typedef typename Arc::Weight Weight;
690  assert(fst != NULL);
691  StateId num_states = fst->NumStates();
692  StateId num_final = 0;
693  vector<StateId> final_states;
694  for (StateId s = 0; s < num_states; s++) {
695  if (fst->Final(s) != Weight::Zero()) {
696  num_final++;
697  final_states.push_back(s);
698  }
699  }
700  if (final_states.size() == 1) {
701  if (fst->Final(final_states[0]) == Weight::One()) {
702  ArcIterator<MutableFst<Arc> > iter(*fst, final_states[0]);
703  if (iter.Done()) {
704  // We already have a final state w/ no transitions out and unit weight.
705  // So we're done.
706  return final_states[0];
707  }
708  }
709  }
710 
711  StateId final_state = fst->AddState();
712  fst->SetFinal(final_state, Weight::One());
713  for (size_t idx = 0;idx < final_states.size(); idx++) {
714  StateId s = final_states[idx];
715  Weight weight = fst->Final(s);
716  fst->SetFinal(s, Weight::Zero());
717  Arc arc;
718  arc.ilabel = 0;
719  arc.olabel = 0;
720  arc.nextstate = final_state;
721  arc.weight = weight;
722  fst->AddArc(s, arc);
723  }
724  return final_state;
725 }
fst::StdArc::StateId StateId
Definition: graph.dox:21
fst::StdArc::Weight Weight
vector<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().

130  {
131  vector<vector<double> > ans(2);
132  ans[0].resize(2, 0.0);
133  ans[1].resize(2, 0.0);
134  ans[0][0] = ans[1][1] = 1.0;
135  return ans;
136 }
int64 DeleteISymbols ( MutableFst< Arc > *  fst,
vector< typename Arc::Label >  isyms 
)

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

References rnnlm::i.

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

651  {
652 
653  // We could do this using the Mapper concept, but this is much easier to understand.
654 
655  typedef typename Arc::Label Label;
656  typedef typename Arc::StateId StateId;
657 
658  int64 num_deleted = 0;
659 
660  if (isyms.size() == 0) return 0;
661  Label isyms_min = *std::min_element(isyms.begin(), isyms.end()),
662  isyms_max = *std::max_element(isyms.begin(), isyms.end());
663  bool isyms_consecutive = (isyms_max+1-isyms_min == static_cast<Label>(isyms.size()));
664  std::set<Label> isyms_set;
665  if (!isyms_consecutive)
666  for (size_t i = 0;i < isyms.size();i++)
667  isyms_set.insert(isyms[i]);
668 
669  for (StateIterator<MutableFst<Arc> > siter(*fst); ! siter.Done(); siter.Next()) {
670  StateId state = siter.Value();
671  for (MutableArcIterator<MutableFst<Arc> > aiter(fst, state); ! aiter.Done(); aiter.Next()) {
672  const Arc &arc = aiter.Value();
673  if (arc.ilabel >= isyms_min && arc.ilabel <= isyms_max) {
674  if (isyms_consecutive || isyms_set.count(arc.ilabel) != 0) {
675  num_deleted++;
676  Arc mod_arc (arc);
677  mod_arc.ilabel = 0; // change label to epsilon.
678  aiter.SetValue(mod_arc);
679  }
680  }
681  }
682  }
683  return num_deleted;
684 }
fst::StdArc::StateId StateId
Definition: graph.dox:21
fst::StdArc::Label Label
void fst::DeleteTestFst ( StdVectorFst fst)

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

111  {
112  delete fst;
113 }
Definition: graph.dox:21
void fst::DeterminizeInLog ( VectorFst< StdArc > *  fst)
inline

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

Referenced by main().

458  {
459  // DeterminizeInLog determinizes 'fst' in the log semiring.
460 
461  ArcSort(fst, ILabelCompare<StdArc>()); // helps DeterminizeStar to be faster.
462  VectorFst<LogArc> *fst_log = new VectorFst<LogArc>; // Want to determinize in log semiring.
463  Cast(*fst, fst_log);
464  VectorFst<StdArc> tmp;
465  *fst = tmp; // make fst empty to free up memory. [actually may make no difference..]
466  VectorFst<LogArc> *fst_det_log = new VectorFst<LogArc>;
467  Determinize(*fst_log, fst_det_log);
468  Cast(*fst_det_log, fst);
469  delete fst_log;
470  delete fst_det_log;
471 }
Definition: graph.dox:21
template void fst::DeterminizeLatticeDeletePhones ( ArcTpl< kaldi::LatticeWeight >::Label  first_phone_label,
MutableFst< ArcTpl< kaldi::LatticeWeight > > *  fst 
)
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 
)
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 
)
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 1390 of file determinize-lattice-pruned.cc.

References DeterminizeLatticeDeletePhones(), and DeterminizeLatticeInsertPhones().

1394  {
1395  // First, insert the phones.
1396  typename ArcTpl<Weight>::Label first_phone_label =
1397  DeterminizeLatticeInsertPhones(trans_model, fst);
1398  TopSort(fst);
1399 
1400  // Second, do determinization with phone inserted.
1401  bool ans = DeterminizeLatticePruned<Weight>(*fst, beam, fst, opts);
1402 
1403  // Finally, remove the inserted phones.
1404  DeterminizeLatticeDeletePhones(first_phone_label, fst);
1405  TopSort(fst);
1406 
1407  return ans;
1408 }
Definition: graph.dox:21
template void DeterminizeLatticeDeletePhones(ArcTpl< kaldi::LatticeWeight >::Label first_phone_label, MutableFst< ArcTpl< kaldi::LatticeWeight > > *fst)
fst::StdArc::Label Label
ArcTpl< Weight >::Label DeterminizeLatticeInsertPhones(const kaldi::TransitionModel &trans_model, MutableFst< ArcTpl< Weight > > *fst)
This function takes in lattices and inserts phones at phone boundaries.
template bool fst::DeterminizeLatticePruned< kaldi::LatticeWeight > ( const ExpandedFst< kaldi::LatticeArc > &  ifst,
double  prune,
MutableFst< kaldi::CompactLatticeArc > *  ofst,
DeterminizeLatticePrunedOptions  opts 
)
template bool fst::DeterminizeLatticePruned< kaldi::LatticeWeight > ( const ExpandedFst< kaldi::LatticeArc > &  ifst,
double  prune,
MutableFst< kaldi::LatticeArc > *  ofst,
DeterminizeLatticePrunedOptions  opts 
)
void DeterminizeStarInLog ( VectorFst< StdArc > *  fst,
float  delta,
bool *  debug_ptr,
int  max_states 
)
inline

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

References DeterminizeStar().

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

441  {
442  // DeterminizeStarInLog determinizes 'fst' in the log semiring, using
443  // the DeterminizeStar algorithm (which also removes epsilons).
444 
445  ArcSort(fst, ILabelCompare<StdArc>()); // helps DeterminizeStar to be faster.
446  VectorFst<LogArc> *fst_log = new VectorFst<LogArc>; // Want to determinize in log semiring.
447  Cast(*fst, fst_log);
448  VectorFst<StdArc> tmp;
449  *fst = tmp; // make fst empty to free up memory. [actually may make no difference..]
450  VectorFst<LogArc> *fst_det_log = new VectorFst<LogArc>;
451  DeterminizeStar(*fst_log, fst_det_log, delta, debug_ptr, max_states);
452  Cast(*fst_det_log, fst);
453  delete fst_log;
454  delete fst_det_log;
455 }
Definition: graph.dox:21
bool DeterminizeStar(F &ifst, MutableFst< typename F::Arc > *ofst, float delta, bool *debug_ptr, int max_states, bool allow_partial)
This function implements the normal version of DeterminizeStar, in which the output strings are repre...
void fst::DfsSort ( MutableFst< Arc > *  fst)

DfsSort sorts the states in an FST in depth-first-search order.

May be useful after ExpandSequences. This is equivalent to TopSort for acyclic FSTs but it does apply the DFS order even for FSTs with cycles.

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.

127  {
128  T f1 = w1.Value(), f2 = w2.Value();
129  if (f2 == -numeric_limits<T>::infinity())
130  return numeric_limits<T>::quiet_NaN();
131  else if (f1 == -numeric_limits<T>::infinity())
132  return -numeric_limits<T>::infinity();
133  else
134  return ArcticWeightTpl<T>(f1 - f2);
135 }
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.

139  {
140  return Divide<float>(w1, w2, typ);
141 }
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.

145  {
146  return Divide<double>(w1, w2, typ);
147 }
LatticeWeightTpl<FloatType> fst::Divide ( const LatticeWeightTpl< FloatType > &  w1,
const LatticeWeightTpl< FloatType > &  w2,
DivideType  typ = DIVIDE_ANY 
)
inline

Definition at line 340 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().

342  {
343  typedef FloatType T;
344  T a = w1.Value1() - w2.Value1(), b = w1.Value2() - w2.Value2();
345  if (a != a || b != b || a == -numeric_limits<T>::infinity()
346  || b == -numeric_limits<T>::infinity()) {
347  KALDI_WARN << "LatticeWeightTpl::Divide, NaN or invalid number produced. "
348  << "[dividing by zero?] Returning zero";
349  return LatticeWeightTpl<T>::Zero();
350  }
351  if (a == numeric_limits<T>::infinity() ||
352  b == numeric_limits<T>::infinity())
353  return LatticeWeightTpl<T>::Zero(); // not a valid number if only one is infinite.
354  return LatticeWeightTpl<T>(a, b);
355 }
#define KALDI_WARN
Definition: kaldi-error.h:130
CompactLatticeWeightTpl<WeightType, IntType> fst::Divide ( const CompactLatticeWeightTpl< WeightType, IntType > &  w1,
const CompactLatticeWeightTpl< WeightType, IntType > &  w2,
DivideType  div = DIVIDE_ANY 
)
inline

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

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

630  {
631  if (w1.Weight() == WeightType::Zero()) {
632  if (w2.Weight() != WeightType::Zero()) {
633  return CompactLatticeWeightTpl<WeightType, IntType>::Zero();
634  } else {
635  KALDI_ERR << "Division by zero [0/0]";
636  }
637  } else if (w2.Weight() == WeightType::Zero()) {
638  KALDI_ERR << "Error: division by zero";
639  }
640  WeightType w = Divide(w1.Weight(), w2.Weight());
641 
642  const vector<IntType> v1 = w1.String(), v2 = w2.String();
643  if (v2.size() > v1.size()) {
644  KALDI_ERR << "Cannot divide, length mismatch";
645  }
646  typename vector<IntType>::const_iterator v1b = v1.begin(),
647  v1e = v1.end(), v2b = v2.begin(), v2e = v2.end();
648  if (div == DIVIDE_LEFT) {
649  if (!std::equal(v2b, v2e, v1b)) { // v2 must be identical to first part of v1.
650  KALDI_ERR << "Cannot divide, data mismatch";
651  }
652  return CompactLatticeWeightTpl<WeightType, IntType>(
653  w, vector<IntType>(v1b+(v2e-v2b), v1e)); // return last part of v1.
654  } else if (div == DIVIDE_RIGHT) {
655  if (!std::equal(v2b, v2e, v1e-(v2e-v2b))) { // v2 must be identical to last part of v1.
656  KALDI_ERR << "Cannot divide, data mismatch";
657  }
658  return CompactLatticeWeightTpl<WeightType, IntType>(
659  w, vector<IntType>(v1b, v1e-(v2e-v2b))); // return first part of v1.
660 
661  } else {
662  KALDI_ERR << "Cannot divide CompactLatticeWeightTpl with DIVIDE_ANY";
663  }
664  return CompactLatticeWeightTpl<WeightType,IntType>::Zero(); // keep compiler happy.
665 }
#define KALDI_ERR
Definition: kaldi-error.h:127
CompactLatticeWeightTpl< WeightType, IntType > Divide(const CompactLatticeWeightTpl< WeightType, IntType > &w1, const CompactLatticeWeightTpl< WeightType, IntType > &w2, DivideType div=DIVIDE_ANY)
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().

49  {
50 
51  typedef typename Arc::StateId StateId;
52  typedef typename Arc::Weight Weight;
53  typedef VectorFst<Arc> Fst;
54  std::vector<char> epsilon_info;
55  ComputeStateInfo(*fst, &epsilon_info);
56 
57 
58  StateId num_states_old = fst->NumStates();
59  StateId non_coaccessible_state = fst->AddState();
60 
65  std::vector<StateId> new_state_vec(num_states_old, kNoStateId);
66  for (StateId s = 0; s < num_states_old; s++) {
67  if ((epsilon_info[s] & kStateHasEpsilonArcsEntering) != 0 &&
68  (epsilon_info[s] & kStateHasNonEpsilonArcsEntering) != 0) {
69  assert(s != fst->Start()); // a type of cyclic FST we can't handle
70  // easily.
71  StateId new_state = fst->AddState();
72  new_state_vec[s] = new_state;
73  fst->AddArc(new_state, Arc(0, 0, Weight::One(), s));
74  }
75  }
76 
79  for (StateId s = 0; s < num_states_old; s++) {
80  for (MutableArcIterator<Fst> aiter(fst, s);
81  !aiter.Done(); aiter.Next()) {
82  Arc arc = aiter.Value();
83  if (arc.ilabel != 0 || arc.olabel != 0) { // non-epsilon arc
84  StateId replacement_state;
85  if (arc.nextstate >= 0 && arc.nextstate < num_states_old &&
86  (replacement_state = new_state_vec[arc.nextstate]) !=
87  kNoStateId) {
88  arc.nextstate = replacement_state;
89  aiter.SetValue(arc);
90  }
91  }
92  }
93  }
94 
97  for (StateId s = 0; s < num_states_old; s++) {
98  if ((epsilon_info[s] & kStateHasEpsilonArcsLeaving) != 0 &&
99  (epsilon_info[s] & kStateHasNonEpsilonArcsLeaving) != 0) {
100  // state has non-epsilon and epsilon arcs leaving.
101  // create a new state and move the non-epsilon arcs to leave
102  // from there instead.
103  StateId new_state = fst->AddState();
104  for (MutableArcIterator<Fst> aiter(fst, s); !aiter.Done();
105  aiter.Next()) {
106  Arc arc = aiter.Value();
107  if (arc.ilabel != 0 || arc.olabel != 0) { // non-epsilon arc.
108  assert(arc.nextstate != s); // we don't handle cyclic FSTs.
109  // move this arc to leave from the new state:
110  fst->AddArc(new_state, arc);
111  arc.nextstate = non_coaccessible_state;
112  aiter.SetValue(arc); // invalidate the arc, Connect() will remove it.
113  }
114  }
115  // Create an epsilon arc to the new state.
116  fst->AddArc(s, Arc(0, 0, Weight::One(), new_state));
117  }
118  }
119  Connect(fst); // Removes arcs to the non-coaccessible state.
120 }
fst::StdArc::StateId StateId
Definition: graph.dox:21
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.
fst::StdArc::Weight Weight
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 873 of file fstext-utils-inl.h.

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

Referenced by main(), and TestEqualAlign().

877  {
878  srand(rand_seed);
879  KALDI_ASSERT(ofst->NumStates() == 0); // make sure ofst empty.
880  // make sure all states can reach final-state (or this algorithm may enter
881  // infinite loop.
882  KALDI_ASSERT(ifst.Properties(kCoAccessible, true) == kCoAccessible);
883 
884  typedef typename Arc::StateId StateId;
885  typedef typename Arc::Weight Weight;
886 
887  if (ifst.Start() == kNoStateId) {
888  KALDI_WARN << "Empty input fst.";
889  return false;
890  }
891  // First select path through ifst.
892  vector<StateId> path;
893  vector<size_t> arc_offsets; // arc taken out of each state.
894  vector<int> nof_ilabels;
895 
896  StateId num_ilabels = 0;
897  int retry_no = 0;
898 
899  // Under normal circumstances, this will be one-pass-only process
900  // Multiple tries might be needed in special cases, typically when
901  // the number of frames is close to number of transitions from
902  // the start node to the final node. It usually happens for really
903  // short utterances
904  do {
905  num_ilabels = 0;
906  arc_offsets.clear();
907  path.clear();
908  path.push_back(ifst.Start());
909 
910  while (1) {
911  // Select either an arc or final-prob.
912  StateId s = path.back();
913  size_t num_arcs = ifst.NumArcs(s);
914  size_t num_arcs_tot = num_arcs;
915  if (ifst.Final(s) != Weight::Zero()) num_arcs_tot++;
916  // kaldi::RandInt is a bit like Rand(), but gets around situations
917  // where RAND_MAX is very small.
918  // Change this to Rand() % num_arcs_tot if compile issues arise
919  size_t arc_offset = static_cast<size_t>(kaldi::RandInt(0, num_arcs_tot-1));
920 
921  if (arc_offset < num_arcs) { // an actual arc.
922  ArcIterator<Fst<Arc> > aiter(ifst, s);
923  aiter.Seek(arc_offset);
924  const Arc &arc = aiter.Value();
925  if (arc.nextstate == s) {
926  continue; // don't take this self-loop arc
927  } else {
928  arc_offsets.push_back(arc_offset);
929  path.push_back(arc.nextstate);
930  if (arc.ilabel != 0) num_ilabels++;
931  }
932  } else {
933  break; // Chose final-prob.
934  }
935  }
936 
937  nof_ilabels.push_back(num_ilabels);
938  } while (( ++retry_no < num_retries) && (num_ilabels > length));
939 
940  if (num_ilabels > length) {
941  std::stringstream ilabel_vec;
942  std::copy(nof_ilabels.begin(), nof_ilabels.end(),
943  std::ostream_iterator<int>(ilabel_vec, ","));
944  std::string s = ilabel_vec.str();
945  s.erase(s.end() - 1);
946  KALDI_WARN << "EqualAlign: the randomly constructed paths lengths: " << s;
947  KALDI_WARN << "EqualAlign: utterance has too few frames " << length
948  << " to align.";
949  return false; // can't make it shorter by adding self-loops!.
950  }
951 
952  StateId num_self_loops = 0;
953  vector<ssize_t> self_loop_offsets(path.size());
954  for (size_t i = 0; i < path.size(); i++)
955  if ( (self_loop_offsets[i] = FindSelfLoopWithILabel(ifst, path[i]))
956  != static_cast<ssize_t>(-1) )
957  num_self_loops++;
958 
959  if (num_self_loops == 0
960  && num_ilabels < length) {
961  KALDI_WARN << "No self-loops on chosen path; cannot match length.";
962  return false; // no self-loops to make it longer.
963  }
964 
965  StateId num_extra = length - num_ilabels; // Number of self-loops we need.
966 
967  StateId min_num_loops = 0;
968  if (num_extra != 0) min_num_loops = num_extra / num_self_loops; // prevent div by zero.
969  StateId num_with_one_more_loop = num_extra - (min_num_loops*num_self_loops);
970  KALDI_ASSERT(num_with_one_more_loop < num_self_loops || num_self_loops == 0);
971 
972  ofst->AddState();
973  ofst->SetStart(0);
974  StateId cur_state = 0;
975  StateId counter = 0; // tell us when we should stop adding one more loop.
976  for (size_t i = 0; i < path.size(); i++) {
977  // First, add any self-loops that are necessary.
978  StateId num_loops = 0;
979  if (self_loop_offsets[i] != static_cast<ssize_t>(-1)) {
980  num_loops = min_num_loops + (counter < num_with_one_more_loop ? 1 : 0);
981  counter++;
982  }
983  for (StateId j = 0; j < num_loops; j++) {
984  ArcIterator<Fst<Arc> > aiter(ifst, path[i]);
985  aiter.Seek(self_loop_offsets[i]);
986  Arc arc = aiter.Value();
987  KALDI_ASSERT(arc.nextstate == path[i]
988  && arc.ilabel != 0); // make sure self-loop with ilabel.
989  StateId next_state = ofst->AddState();
990  ofst->AddArc(cur_state, Arc(arc.ilabel, arc.olabel, arc.weight, next_state));
991  cur_state = next_state;
992  }
993  if (i+1 < path.size()) { // add forward transition.
994  ArcIterator<Fst<Arc> > aiter(ifst, path[i]);
995  aiter.Seek(arc_offsets[i]);
996  Arc arc = aiter.Value();
997  KALDI_ASSERT(arc.nextstate == path[i+1]);
998  StateId next_state = ofst->AddState();
999  ofst->AddArc(cur_state, Arc(arc.ilabel, arc.olabel, arc.weight, next_state));
1000  cur_state = next_state;
1001  } else { // add final-prob.
1002  Weight weight = ifst.Final(path[i]);
1003  KALDI_ASSERT(weight != Weight::Zero());
1004  ofst->SetFinal(cur_state, weight);
1005  }
1006  }
1007  return true;
1008 }
fst::StdArc::StateId StateId
ssize_t FindSelfLoopWithILabel(const Fst< Arc > &fst, typename Arc::StateId s)
#define KALDI_WARN
Definition: kaldi-error.h:130
fst::StdArc::Weight Weight
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
int32 RandInt(int32 min_val, int32 max_val, struct RandomState *state)
Definition: kaldi-math.cc:100
void ExpandInputSequences ( const vector< 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().

164  {
166  typedef typename Arc::StateId StateId;
167  typedef typename Arc::Label Label;
168  typedef typename Arc::Weight Weight;
169  fst->SetInputSymbols(NULL);
170  size_t size = sequences.size();
171  if (sequences.size() > 0) assert(sequences[0].size() == 0); // should be eps.
172  StateId num_states_at_start = fst->NumStates();
173  for (StateId s = 0; s < num_states_at_start; s++) {
174  StateId num_arcs = fst->NumArcs(s);
175  for (StateId aidx = 0; aidx < num_arcs; aidx++) {
176  ArcIterator<MutableFst<Arc> > aiter(*fst, s);
177  aiter.Seek(aidx);
178  Arc arc = aiter.Value();
179 
180  Label ilabel = arc.ilabel;
181  Label dest_state = arc.nextstate;
182  if (ilabel != 0) { // non-eps [nothing to do if eps]...
183  assert(ilabel < static_cast<Label>(size));
184  size_t len = sequences[ilabel].size();
185  if (len <= 1) {
186  if (len == 0) arc.ilabel = 0;
187  else arc.ilabel = sequences[ilabel][0];
188  MutableArcIterator<MutableFst<Arc> > mut_aiter(fst, s);
189  mut_aiter.Seek(aidx);
190  mut_aiter.SetValue(arc);
191  } else { // len>=2. Must create new states...
192  StateId curstate = -1; // keep compiler happy: this value never used.
193  for (size_t n = 0; n < len; n++) { // adding/modifying "len" arcs.
194  StateId nextstate;
195  if (n < len-1) {
196  nextstate = fst->AddState();
197  assert(nextstate >= num_states_at_start);
198  } else nextstate = dest_state; // going back to original arc's
199  // destination.
200  if (n == 0) {
201  arc.ilabel = sequences[ilabel][0];
202  arc.nextstate = nextstate;
203  MutableArcIterator<MutableFst<Arc> > mut_aiter(fst, s);
204  mut_aiter.Seek(aidx);
205  mut_aiter.SetValue(arc);
206  } else {
207  arc.ilabel = sequences[ilabel][n];
208  arc.olabel = 0;
209  arc.weight = Weight::One();
210  arc.nextstate = nextstate;
211  fst->AddArc(curstate, arc);
212  }
213  curstate = nextstate;
214  }
215  }
216  }
217  }
218  }
219 }
fst::StdArc::StateId StateId
#define KALDI_ASSERT_IS_INTEGER_TYPE(I)
Definition: kaldi-utils.h:130
Definition: graph.dox:21
struct rnnlm::@11::@12 n
fst::StdArc::Label Label
fst::StdArc::Weight Weight
void Factor ( const Fst< Arc > &  fst,
MutableFst< Arc > *  ofst,
vector< 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(), main(), and TestFactor().

70  {
72  typedef typename Arc::StateId StateId;
73  typedef typename Arc::Label Label;
74  typedef typename Arc::Weight Weight;
75  assert(symbols_out != NULL);
76  ofst->DeleteStates();
77  if (fst.Start() < 0) return; // empty FST.
78  vector<StateId> order;
79  DfsOrderVisitor<Arc> dfs_order_visitor(&order);
80  DfsVisit(fst, &dfs_order_visitor);
81  assert(order.size() > 0);
82  StateId max_state = *(std::max_element(order.begin(), order.end()));
83  vector<StatePropertiesType> state_properties;
84  GetStateProperties(fst, max_state, &state_properties);
85 
86  vector<bool> remove(max_state+1); // if true, will remove this state.
87 
88  // Now identify states that will be removed (made the middle of a chain).
89  // The basic rule is that if the FstStateProperties equals
90  // (kStateArcsIn|kStateArcsOut) or (kStateArcsIn|kStateArcsOut|kStateIlabelsOut),
91  // then it is in the middle of a chain. This eliminates state with
92  // multiple input or output arcs, final states, and states with arcs out
93  // that have olabels [we assume these are pushed to the left, so occur on the
94  // 1st arc of a chain.
95 
96  for (StateId i = 0; i <= max_state; i++)
97  remove[i] = (state_properties[i] == (kStateArcsIn|kStateArcsOut)
98  || state_properties[i] == (kStateArcsIn|kStateArcsOut|kStateIlabelsOut));
99  vector<StateId> state_mapping(max_state+1, kNoStateId);
100 
101  typedef unordered_map<vector<I>, Label, kaldi::VectorHasher<I> > SymbolMapType;
102  SymbolMapType symbol_mapping;
103  Label symbol_counter = 0;
104  {
105  vector<I> eps;
106  symbol_mapping[eps] = symbol_counter++;
107  }
108  vector<I> this_sym; // a temporary used inside the loop.
109  for (size_t i = 0; i < order.size(); i++) {
110  StateId state = order[i];
111  if (!remove[state]) { // Process this state...
112  StateId &new_state = state_mapping[state];
113  if (new_state == kNoStateId) new_state = ofst->AddState();
114  for (ArcIterator<Fst<Arc> > aiter(fst, state); !aiter.Done(); aiter.Next()) {
115  Arc arc = aiter.Value();
116  if (arc.ilabel == 0) this_sym.clear();
117  else {
118  this_sym.resize(1);
119  this_sym[0] = arc.ilabel;
120  }
121  while (remove[arc.nextstate]) {
122  ArcIterator<Fst<Arc> > aiter2(fst, arc.nextstate);
123  assert(!aiter2.Done());
124  const Arc &nextarc = aiter2.Value();
125  arc.weight = Times(arc.weight, nextarc.weight);
126  assert(nextarc.olabel == 0);
127  if (nextarc.ilabel != 0) this_sym.push_back(nextarc.ilabel);
128  assert(static_cast<Label>(static_cast<I>(nextarc.ilabel))
129  == nextarc.ilabel); // check within integer range.
130  arc.nextstate = nextarc.nextstate;
131  }
132  StateId &new_nextstate = state_mapping[arc.nextstate];
133  if (new_nextstate == kNoStateId) new_nextstate = ofst->AddState();
134  arc.nextstate = new_nextstate;
135  if (symbol_mapping.count(this_sym) != 0) arc.ilabel = symbol_mapping[this_sym];
136  else arc.ilabel = symbol_mapping[this_sym] = symbol_counter++;
137  ofst->AddArc(new_state, arc);
138  }
139  if (fst.Final(state) != Weight::Zero())
140  ofst->SetFinal(new_state, fst.Final(state));
141  }
142  }
143  ofst->SetStart(state_mapping[fst.Start()]);
144 
145  // Now output the symbol sequences.
146  symbols_out->resize(symbol_counter);
147  for (typename SymbolMapType::const_iterator iter = symbol_mapping.begin();
148  iter != symbol_mapping.end(); ++iter) {
149  (*symbols_out)[iter->second] = iter->first;
150  }
151 }
fst::StdArc::StateId StateId
A hashing function-object for vectors.
Definition: stl-utils.h:230
#define KALDI_ASSERT_IS_INTEGER_TYPE(I)
Definition: kaldi-utils.h:130
void GetStateProperties(const Fst< Arc > &fst, typename Arc::StateId max_state, vector< StatePropertiesType > *props)
This function works out various properties of the states in the FST, using the bit properties defined...
Definition: factor-inl.h:37
LatticeWeightTpl< FloatType > Times(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2)
fst::StdArc::Label Label
fst::StdArc::Weight Weight
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().

155  {
156  typedef typename Arc::Label Label;
157  vector<vector<Label> > symbols;
158  Factor(fst, ofst2, &symbols);
159  CreateFactorFst(symbols, ofst1);
160 }
fst::StdArc::Label Label
void CreateFactorFst(const vector< vector< I > > &sequences, MutableFst< Arc > *fst)
The function CreateFactorFst will create an FST that expands out the "factors" that are the indices o...
Definition: factor-inl.h:250
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: factor-inl.h:154
bool fst::FileExists ( string  strFilename)

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

28  {
29  struct stat stFileInfo;
30  bool blnReturn;
31  int intStat;
32 
33  // Attempt to get the file attributes
34  intStat = stat(strFilename.c_str(), &stFileInfo);
35  if (intStat == 0) {
36  // We were able to get the file attributes
37  // so the file obviously exists.
38  blnReturn = true;
39  } else {
40  // We were not able to get the file attributes.
41  // This may mean that we don't have permission to
42  // access the folder which contains this file. If you
43  // need to do that level of checking, lookup the
44  // return values of stat which will give you
45  // more details on why stat failed.
46  blnReturn = false;
47  }
48 
49  return blnReturn;
50 }
ssize_t fst::FindSelfLoopWithILabel ( const Fst< Arc > &  fst,
typename Arc::StateId  s 
)

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

Referenced by EqualAlign().

864  {
865  for (ArcIterator<Fst<Arc> > aiter(fst, s); !aiter.Done(); aiter.Next())
866  if (aiter.Value().nextstate == s
867  && aiter.Value().ilabel != 0) return static_cast<ssize_t>(aiter.Position());
868  return static_cast<ssize_t>(-1);
869 }
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 567 of file fstext-utils-inl.h.

References FollowingInputSymbolsAreSameClass().

Referenced by TestMakeSymbolsSame().

567  {
568  IdentityFunction<typename Arc::Label> f;
569  return FollowingInputSymbolsAreSameClass(end_is_epsilon, fst, f);
570 }
bool FollowingInputSymbolsAreSameClass(bool end_is_epsilon, const Fst< Arc > &fst, const F &f)
bool FollowingInputSymbolsAreSameClass ( bool  end_is_epsilon,
const Fst< Arc > &  fst,
const F &  f 
)

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

Referenced by FollowingInputSymbolsAreSame(), and TestMakeSymbolsSameClass().

574  {
575  typedef typename Arc::StateId StateId;
576  typedef typename Arc::Weight Weight;
577  typedef typename F::Result ClassType;
578  const ClassType noClass = f(kNoLabel), epsClass = f(0);
579  for (StateIterator<Fst<Arc> > siter(fst); !siter.Done(); siter.Next()) {
580  StateId s = siter.Value();
581  ClassType c = noClass;
582  for (ArcIterator<Fst<Arc> > aiter(fst, s); !aiter.Done(); aiter.Next()) {
583  const Arc &arc = aiter.Value();
584  if (c == noClass)
585  c = f(arc.ilabel);
586  else
587  if (c != f(arc.ilabel))
588  return false;
589  }
590  if (end_is_epsilon && c != noClass &&
591  c != epsClass && fst.Final(s) != Weight::Zero())
592  return false;
593  }
594  return true;
595 }
fst::StdArc::StateId StateId
fst::StdArc::Weight Weight
static VectorFst<Arc>* fst::GenAcceptorFromSequence ( const vector< typename Arc::Label > &  symbols,
float  cost 
)
static

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

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

33  {
34  typedef typename Arc::Weight Weight;
35  typedef typename Arc::StateId StateId;
36 
37  vector<float> split_cost(symbols.size()+1, 0.0); // for #-arcs + end-state.
38  { // compute split_cost. it must sum to "cost".
39  std::set<int32> indices;
40  size_t num_indices = 1 + (kaldi::Rand() % split_cost.size());
41  while (indices.size() < num_indices) indices.insert(kaldi::Rand() % split_cost.size());
42  for (std::set<int32>::iterator iter = indices.begin(); iter != indices.end(); ++iter) {
43  split_cost[*iter] = cost / num_indices;
44  }
45  }
46 
47  VectorFst<Arc> *fst = new VectorFst<Arc>();
48  StateId cur_state = fst->AddState();
49  fst->SetStart(cur_state);
50  for (size_t i = 0; i < symbols.size(); i++) {
51  StateId next_state = fst->AddState();
52  Arc arc;
53  arc.ilabel = symbols[i];
54  arc.olabel = symbols[i];
55  arc.nextstate = next_state;
56  arc.weight = (Weight) split_cost[i];
57  fst->AddArc(cur_state, arc);
58  cur_state = next_state;
59 
60  }
61  fst->SetFinal(cur_state, (Weight)split_cost[symbols.size()]);
62  return fst;
63 }
fst::StdArc::StateId StateId
Definition: graph.dox:21
int Rand(struct RandomState *state)
Definition: kaldi-math.cc:46
fst::StdArc::Weight Weight
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 123 of file context-fst-test.cc.

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

128  {
129  KALDI_ASSERT(phoneseq_out != NULL);
130  typedef typename Arc::Label Label;
131  // Generate an FST that is a random phone sequence, ending
132  // with "num_subseq_syms" subsequential symbols. It will
133  // have disambiguation symbols randomly interspersed throughout.
134  // The number of phones is random (possibly zero).
135  size_t len = (kaldi::Rand() % 4) * (kaldi::Rand() % 3); // up to 3*2=6 phones.
136  float disambig_prob = 0.33;
137  phoneseq_out->clear();
138  vector<Label> syms; // the phones
139  for (size_t i = 0; i < len; i++) {
140  while (kaldi::RandUniform() < disambig_prob) syms.push_back(disambig_syms[kaldi::Rand() % disambig_syms.size()]);
141  Label phone_id = phone_syms[kaldi::Rand() % phone_syms.size()];
142  phoneseq_out->push_back(phone_id); // record in output the underlying phone sequence.
143  syms.push_back(phone_id);
144  }
145  for (size_t i = 0; static_cast<int32>(i) < num_subseq_syms; i++) {
146  while (kaldi::RandUniform() < disambig_prob) syms.push_back(disambig_syms[kaldi::Rand() % disambig_syms.size()]);
147  syms.push_back(subsequential_symbol);
148  }
149  while (kaldi::RandUniform() < disambig_prob) syms.push_back(disambig_syms[kaldi::Rand() % disambig_syms.size()]);
150 
151  // OK, now have the symbols of the FST as a vector.
152  return GenAcceptorFromSequence<Arc>(syms, seq_prob);
153 }
float RandUniform(struct RandomState *state=NULL)
Returns a random number strictly between 0 and 1.
Definition: kaldi-math.h:151
fst::StdArc::Label Label
int Rand(struct RandomState *state)
Definition: kaldi-math.cc:46
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void GetInputSymbols ( const Fst< Arc > &  fst,
bool  include_eps,
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(), kaldi::CreateEditDistance(), kaldi::GetRandomAlignmentForPhone(), and TestMakeLinearAcceptor().

99  {
101  unordered_set<I> all_syms;
102  for (StateIterator<Fst<Arc> > siter(fst); !siter.Done(); siter.Next()) {
103  typename Arc::StateId s = siter.Value();
104  for (ArcIterator<Fst<Arc> > aiter(fst, s); !aiter.Done(); aiter.Next()) {
105  const Arc &arc = aiter.Value();
106  all_syms.insert(arc.ilabel);
107  }
108  }
109  // Remove epsilon, if instructed.
110  if (!include_eps && all_syms.count(0) != 0)
111  all_syms.erase(0);
112  KALDI_ASSERT(symbols != NULL);
113  kaldi::CopySetToVector(all_syms, symbols);
114  std::sort(symbols->begin(), symbols->end());
115 }
fst::StdArc::StateId StateId
void CopySetToVector(const std::set< T > &s, std::vector< T > *v)
Copies the elements of a set to a vector.
Definition: stl-utils.h:98
#define KALDI_ASSERT_IS_INTEGER_TYPE(I)
Definition: kaldi-utils.h:130
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
bool GetLinearSymbolSequence ( const Fst< Arc > &  fst,
vector< I > *  isymbols_out,
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::DecodeUtteranceLatticeSimple(), main(), MinimumBayesRisk::MinimumBayesRisk(), TestEqualAlign(), TestMakeLinearAcceptor(), and DecodeUtteranceLatticeFasterClass::~DecodeUtteranceLatticeFasterClass().

181  {
182  typedef typename Arc::StateId StateId;
183  typedef typename Arc::Weight Weight;
184 
185  Weight tot_weight = Weight::One();
186  vector<I> ilabel_seq;
187  vector<I> olabel_seq;
188 
189  StateId cur_state = fst.Start();
190  if (cur_state == kNoStateId) { // empty sequence.
191  if (isymbols_out != NULL) isymbols_out->clear();
192  if (osymbols_out != NULL) osymbols_out->clear();
193  if (tot_weight_out != NULL) *tot_weight_out = Weight::Zero();
194  return true;
195  }
196  while (1) {
197  Weight w = fst.Final(cur_state);
198  if (w != Weight::Zero()) { // is final..
199  tot_weight = Times(w, tot_weight);
200  if (fst.NumArcs(cur_state) != 0) return false;
201  if (isymbols_out != NULL) *isymbols_out = ilabel_seq;
202  if (osymbols_out != NULL) *osymbols_out = olabel_seq;
203  if (tot_weight_out != NULL) *tot_weight_out = tot_weight;
204  return true;
205  } else {
206  if (fst.NumArcs(cur_state) != 1) return false;
207 
208  ArcIterator<Fst<Arc> > iter(fst, cur_state); // get the only arc.
209  const Arc &arc = iter.Value();
210  tot_weight = Times(arc.weight, tot_weight);
211  if (arc.ilabel != 0) ilabel_seq.push_back(arc.ilabel);
212  if (arc.olabel != 0) olabel_seq.push_back(arc.olabel);
213  cur_state = arc.nextstate;
214  }
215  }
216 }
fst::StdArc::StateId StateId
LatticeWeightTpl< FloatType > Times(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2)
fst::StdArc::Weight Weight
bool GetLinearSymbolSequences ( const Fst< Arc > &  fst,
vector< vector< I > > *  isymbols_out,
vector< vector< I > > *  osymbols_out,
vector< typename Arc::Weight > *  tot_weight_out 
)

GetLinearSymbolSequence gets the symbol sequences and weights from an FST as output by the ShortestPath algorithm (called with some parameter n), which has up to n arcs out from the start state, and if you follow one of the arcs you enter a linear sequence of states.

This function outputs the info in a more N-best-list-like format. It returns true if the FST had the expected structure, and false otherwise (note: an empty FST counts as having this structure). We don't accept an FST that has a final-prob on the start state, as it wouldn't be clear whether to put it as the first or last path (this function is used in an N-best context where the paths' ordering is somewhat meaningful.) This function will set the output vectors to the appropriate size, and for each path will output the input and output symbols as vectors (not including epsilons). It outputs the total weight for each path.

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

References rnnlm::n, and Times().

Referenced by TestMakeLinearAcceptor().

223  {
224  typedef typename Arc::StateId StateId;
225  typedef typename Arc::Weight Weight;
226 
227  if (isymbols_out) isymbols_out->clear();
228  if (osymbols_out) osymbols_out->clear();
229  if (weights_out) weights_out->clear();
230 
231  StateId start_state = fst.Start();
232  if (start_state == kNoStateId) { // no paths.
233  return true; // empty FST counts as having this structure.
234  }
235 
236  if (fst.Final(start_state) != Weight::Zero())
237  return false; // We don't allow final-prob on the start state.
238 
239  size_t N = fst.NumArcs(start_state), n = 0;
240  if (isymbols_out) isymbols_out->resize(N);
241  if (osymbols_out) osymbols_out->resize(N);
242  if (weights_out) weights_out->resize(N);
243 
244  bool error = false;
245 
246  for (ArcIterator<Fst<Arc> > aiter(fst, start_state);
247  !aiter.Done();
248  aiter.Next(), n++) {
249  StateId cur_state = start_state;
250  if (isymbols_out) (*isymbols_out)[n].clear();
251  if (osymbols_out) (*osymbols_out)[n].clear();
252  if (weights_out) (*weights_out)[n] = Weight::One();
253 
254  while (1) {
255  if (fst.Final(cur_state) != Weight::Zero()) {
256  (*weights_out)[n] = Times((*weights_out)[n],
257  fst.Final(cur_state));
258  if (fst.NumArcs(cur_state) != 0)
259  error = true;
260  break;
261  } else {
262  if (fst.NumArcs(cur_state) != 1) {
263  error = true;
264  break;
265  }
266  ArcIterator<Fst<Arc> > aiter(fst, cur_state);
267  const Arc &arc = aiter.Value();
268  if (isymbols_out && arc.ilabel != 0)
269  (*isymbols_out)[n].push_back(arc.ilabel);
270  if (osymbols_out && arc.ilabel != 0)
271  (*osymbols_out)[n].push_back(arc.olabel);
272  if (weights_out)
273  (*weights_out)[n] = Times((*weights_out)[n], arc.weight);
274  cur_state = arc.nextstate;
275  }
276  }
277  if (error) break;
278  }
279  if (error) {
280  if (isymbols_out) isymbols_out->clear();
281  if (osymbols_out) osymbols_out->clear();
282  if (weights_out) weights_out->clear();
283  return false;
284  } else {
285  return true;
286  }
287 }
fst::StdArc::StateId StateId
LatticeWeightTpl< FloatType > Times(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2)
struct rnnlm::@11::@12 n
fst::StdArc::Weight Weight
void GetOutputSymbols ( const Fst< Arc > &  fst,
bool  include_eps,
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().

78  {
80  std::set<I> all_syms;
81  for (StateIterator<Fst<Arc> > siter(fst); !siter.Done(); siter.Next()) {
82  typename Arc::StateId s = siter.Value();
83  for (ArcIterator<Fst<Arc> > aiter(fst, s); !aiter.Done(); aiter.Next()) {
84  const Arc &arc = aiter.Value();
85  all_syms.insert(arc.olabel);
86  }
87  }
88 
89  // Remove epsilon, if instructed.
90  if (!include_eps && !all_syms.empty() && *all_syms.begin() == 0)
91  all_syms.erase(0);
92  KALDI_ASSERT(symbols != NULL);
93  kaldi::CopySetToVector(all_syms, symbols);
94 }
fst::StdArc::StateId StateId
void CopySetToVector(const std::set< T > &s, std::vector< T > *v)
Copies the elements of a set to a vector.
Definition: stl-utils.h:98
#define KALDI_ASSERT_IS_INTEGER_TYPE(I)
Definition: kaldi-utils.h:130
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void GetStateProperties ( const Fst< Arc > &  fst,
typename Arc::StateId  max_state,
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().

39  {
40  typedef typename Arc::StateId StateId;
41  typedef typename Arc::Weight Weight;
42  assert(props != NULL);
43  props->clear();
44  if (fst.Start() < 0) return; // Empty fst.
45  props->resize(max_state+1, 0);
46  assert(fst.Start() <= max_state);
47  (*props)[fst.Start()] |= kStateInitial;
48  for (StateId s = 0; s <= max_state; s++) {
49  StatePropertiesType &s_info = (*props)[s];
50  for (ArcIterator<Fst<Arc> > aiter(fst, s); !aiter.Done(); aiter.Next()) {
51  const Arc &arc = aiter.Value();
52  if (arc.ilabel != 0) s_info |= kStateIlabelsOut;
53  if (arc.olabel != 0) s_info |= kStateOlabelsOut;
54  StateId nexts = arc.nextstate;
55  assert(nexts <= max_state); // or input was invalid.
56  StatePropertiesType &nexts_info = (*props)[nexts];
57  if (s_info&kStateArcsOut) s_info |= kStateMultipleArcsOut;
58  s_info |= kStateArcsOut;
59  if (nexts_info&kStateArcsIn) nexts_info |= kStateMultipleArcsIn;
60  nexts_info |= kStateArcsIn;
61  }
62  if (fst.Final(s) != Weight::Zero()) s_info |= kStateFinal;
63  }
64 }
fst::StdArc::StateId StateId
unsigned char StatePropertiesType
Definition: factor.h:122
fst::StdArc::Weight Weight
void GetSymbols ( const SymbolTable &  symtab,
bool  include_eps,
vector< I > *  syms_out 
)

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

References KALDI_ASSERT.

Referenced by main().

401  {
402  KALDI_ASSERT(syms_out != NULL);
403  syms_out->clear();
404  for (SymbolTableIterator iter(symtab);
405  !iter.Done();
406  iter.Next()) {
407  if (include_eps || iter.Value() != 0) {
408  syms_out->push_back(iter.Value());
409  KALDI_ASSERT(syms_out->back() == iter.Value()); // an integer-range thing.
410  }
411  }
412 }
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
vector<vector<double> > fst::GraphLatticeScale ( double  lmwt)
inline

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

Referenced by main().

147  {
148  vector<vector<double> > ans(2);
149  ans[0].resize(2, 0.0);
150  ans[1].resize(2, 0.0);
151  ans[0][0] = lmwt;
152  ans[1][1] = 1.0;
153  return ans;
154 }
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().

54  {
55  typename Arc::Label ans = 0;
56  for (StateIterator<Fst<Arc> > siter(fst); !siter.Done(); siter.Next()) {
57  typename Arc::StateId s = siter.Value();
58  for (ArcIterator<Fst<Arc> > aiter(fst, s); !aiter.Done(); aiter.Next()) {
59  const Arc &arc = aiter.Value();
60  ans = std::max(ans, arc.ilabel);
61  }
62  }
63  return ans;
64 }
fst::StdArc::StateId StateId
fst::StdArc::Label Label
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().

41  {
42  typename Arc::Label ans = 0;
43  for (StateIterator<Fst<Arc> > siter(fst); !siter.Done(); siter.Next()) {
44  typename Arc::StateId s = siter.Value();
45  for (ArcIterator<Fst<Arc> > aiter(fst, s); !aiter.Done(); aiter.Next()) {
46  const Arc &arc = aiter.Value();
47  ans = std::max(ans, arc.olabel);
48  }
49  }
50  return ans;
51 }
fst::StdArc::StateId StateId
fst::StdArc::Label Label
bool IsStochasticFst ( const Fst< LogArc > &  fst,
float  delta,
LogArc::Weight *  min_sum,
LogArc::Weight *  max_sum 
)
inline

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

References ApproxEqual(), and Plus().

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

1244  {
1245  typedef LogArc Arc;
1246  typedef Arc::StateId StateId;
1247  typedef Arc::Weight Weight;
1248  bool first_time = true;
1249  bool ans = true;
1250  for (StateIterator<Fst<Arc> > siter(fst); !siter.Done(); siter.Next()) {
1251  StateId s = siter.Value();
1252  Weight sum = fst.Final(s);
1253  for (ArcIterator<Fst<Arc> > aiter(fst, s); !aiter.Done(); aiter.Next()) {
1254  const Arc &arc = aiter.Value();
1255  sum = Plus(sum, arc.weight);
1256  }
1257  if (!ApproxEqual(Weight::One(), sum, delta)) ans = false;
1258  if (first_time) {
1259  first_time = false;
1260  if (max_sum) *max_sum = sum;
1261  if (min_sum) *min_sum = sum;
1262  } else {
1263  // note that max and min are reversed from their normal
1264  // meanings here (max and min w.r.t. the underlying probabilities).
1265  if (max_sum && sum.Value() < max_sum->Value()) *max_sum = sum;
1266  if (min_sum && sum.Value() > min_sum->Value()) *min_sum = sum;
1267  }
1268  }
1269  if (first_time) { // just avoid NaNs if FST was empty.
1270  if (max_sum) *max_sum = Weight::One();
1271  if (min_sum) *min_sum = Weight::One();
1272  }
1273  return ans;
1274 }
fst::StdArc::StateId StateId
LatticeWeightTpl< FloatType > Plus(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2)
fst::StdArc::Weight Weight
static bool ApproxEqual(float a, float b, float relative_tolerance=0.001)
return abs(a - b) <= relative_tolerance * (abs(a)+abs(b)).
Definition: kaldi-math.h:262
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.

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 1205 of file fstext-utils-inl.h.

References ApproxEqual(), and Plus().

1208  {
1209  typedef typename Arc::StateId StateId;
1210  typedef typename Arc::Weight Weight;
1211  NaturalLess<Weight> nl;
1212  bool first_time = true;
1213  bool ans = true;
1214  for (StateIterator<Fst<Arc> > siter(fst); !siter.Done(); siter.Next()) {
1215  StateId s = siter.Value();
1216  Weight sum = fst.Final(s);
1217  for (ArcIterator<Fst<Arc> > aiter(fst, s); !aiter.Done(); aiter.Next()) {
1218  const Arc &arc = aiter.Value();
1219  sum = Plus(sum, arc.weight);
1220  }
1221  if (!ApproxEqual(Weight::One(), sum, delta)) ans = false;
1222  if (first_time) {
1223  first_time = false;
1224  if (max_sum) *max_sum = sum;
1225  if (min_sum) *min_sum = sum;
1226  } else {
1227  if (max_sum && nl(*max_sum, sum)) *max_sum = sum;
1228  if (min_sum && nl(sum, *min_sum)) *min_sum = sum;
1229  }
1230  }
1231  if (first_time) { // just avoid NaNs if FST was empty.
1232  if (max_sum) *max_sum = Weight::One();
1233  if (min_sum) *min_sum = Weight::One();
1234  }
1235  return ans;
1236 }
fst::StdArc::StateId StateId
LatticeWeightTpl< FloatType > Plus(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2)
fst::StdArc::Weight Weight
static bool ApproxEqual(float a, float b, float relative_tolerance=0.001)
return abs(a - b) <= relative_tolerance * (abs(a)+abs(b)).
Definition: kaldi-math.h:262
bool IsStochasticFstInLog ( const VectorFst< StdArc > &  fst,
float  delta,
StdArc::Weight *  min_sum,
StdArc::Weight *  max_sum 
)
inline

Tests whether a tropical FST is stochastic in the log semiring (casts it and does the check.)

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

References IsStochasticFst().

Referenced by main(), and TestPushSpecial().

1281  {
1282  VectorFst<LogArc> logfst;
1283  Cast(fst, &logfst);
1284  LogArc::Weight log_min, log_max;
1285  bool ans = IsStochasticFst(logfst, delta, &log_min, &log_max);
1286  if (min_sum) *min_sum = StdArc::Weight(log_min.Value());
1287  if (max_sum) *max_sum = StdArc::Weight(log_max.Value());
1288  return ans;
1289 }
Definition: graph.dox:21
fst::StdArc::Weight Weight
bool IsStochasticFst(const Fst< Arc > &fst, float delta, typename Arc::Weight *min_sum, typename Arc::Weight *max_sum)
This function returns true if, in the semiring of the FST, the sum (within the semiring) of all the a...
vector<vector<double> > fst::LatticeScale ( double  lmwt,
double  acwt 
)
inline

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

Referenced by main().

156  {
157  vector<vector<double> > ans(2);
158  ans[0].resize(2, 0.0);
159  ans[1].resize(2, 0.0);
160  ans[0][0] = lmwt;
161  ans[1][1] = acwt;
162  return ans;
163 }
void fst::LatticeWeightTest ( )

Definition at line 61 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().

61  {
62  for(int32 i = 0; i < 100; i++) {
64  LatticeWeight l3 = Plus(l1, l2);
65  LatticeWeight l4 = Times(l1, l2);
66  BaseFloat f1 = l1.Value1() + l1.Value2(), f2 = l2.Value1() + l2.Value2(), f3 = l3.Value1() + l3.Value2(),
67  f4 = l4.Value1() + l4.Value2();
68  kaldi::AssertEqual(std::min(f1, f2), f3);
69  kaldi::AssertEqual(f1 + f2, f4);
70 
71  KALDI_ASSERT(Plus(l3, l3) == l3);
72  KALDI_ASSERT(Plus(l1, l2) == Plus(l2, l1)); // commutativity of plus
73  KALDI_ASSERT(Times(l1, l2) == Times(l2, l1)); // commutativity of Times (true for this semiring, not always)
74  KALDI_ASSERT(Plus(l3, LatticeWeight::Zero()) == l3); // x + 0 = x
75  KALDI_ASSERT(Times(l3, LatticeWeight::One()) == l3); // x * 1 = x
76  KALDI_ASSERT(Times(l3, LatticeWeight::Zero()) == LatticeWeight::Zero()); // x * 0 = 0
77 
78  KALDI_ASSERT(l3.Reverse().Reverse() == l3);
79 
80  NaturalLess<LatticeWeight> nl;
81  bool a = nl(l1, l2);
82  bool b = (Plus(l1, l2) == l1 && l1 != l2);
83  KALDI_ASSERT(a == b);
84 
85  KALDI_ASSERT(Compare(l1, Plus(l1, l2)) != 1); // so do not have l1 > l1 + l2
87  {
88  LatticeWeight wa = Times(Plus(l1, l2), Plus(l5, l6)),
89  wb = Plus(Times(l1, l5), Plus(Times(l1, l6),
90  Plus(Times(l2, l5), Times(l2, l6))));
91  if (!ApproxEqual(wa, wb)) {
92  std::cout << "l1 = " << l1 << ", l2 = " << l2
93  << ", l5 = " << l5 << ", l6 = " << l6 << "\n";
94  std::cout << "ERROR: " << wa << " != " << wb << "\n";
95  }
96  // KALDI_ASSERT(Times(Plus(l1, l2), Plus(l5, l6))
97  // == Plus(Times(l1, l5), Plus(Times(l1,l6),
98  // Plus(Times(l2, l5), Times(l2, l6))))); // * distributes over +
99  }
100  KALDI_ASSERT(l1.Member() && l2.Member() && l3.Member() && l4.Member()
101  && l5.Member() && l6.Member());
102  if (l2 != LatticeWeight::Zero())
103  KALDI_ASSERT(ApproxEqual(Divide(Times(l1, l2), l2), l1)); // (a*b) / b = a if b != 0
104  KALDI_ASSERT(ApproxEqual(l1, l1.Quantize()));
105 
106  std::ostringstream s1;
107  s1 << l1;
108  std::istringstream s2(s1.str());
109  s2 >> l2;
110  KALDI_ASSERT(ApproxEqual(l1, l2));
111  std::cout << s1.str() << '\n';
112  {
113  std::ostringstream s1b;
114  l1.Write(s1b);
115  std::istringstream s2b(s1b.str());
116  l3.Read(s2b);
117  KALDI_ASSERT(l1 == l3);
118  }
119  }
120 }
LatticeWeightTpl< FloatType > Divide(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2, DivideType typ=DIVIDE_ANY)
LatticeWeightTpl< FloatType > Plus(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2)
LatticeWeightTpl< FloatType > Times(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2)
float BaseFloat
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.
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
LatticeWeight RandomLatticeWeight()
static void AssertEqual(float a, float b, float relative_tolerance=0.001)
assert abs(a - b) <= relative_tolerance * (abs(a)+abs(b))
Definition: kaldi-math.h:273
LatticeWeightTpl< BaseFloat > LatticeWeight
static bool ApproxEqual(float a, float b, float relative_tolerance=0.001)
return abs(a - b) <= relative_tolerance * (abs(a)+abs(b)).
Definition: kaldi-math.h:262
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 680 of file fstext-utils-inl.h.

References MakeFollowingInputSymbolsSameClass().

Referenced by TestMakeSymbolsSame().

680  {
681  IdentityFunction<typename Arc::Label> f;
682  MakeFollowingInputSymbolsSameClass(end_is_epsilon, fst, f);
683 }
Definition: graph.dox:21
void MakeFollowingInputSymbolsSameClass(bool end_is_epsilon, MutableFst< Arc > *fst, const F &f)
As MakeFollowingInputSymbolsSame, but takes a functor object that maps labels to classes.
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 686 of file fstext-utils-inl.h.

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

Referenced by kaldi::AddSelfLoopsAfter(), MakeFollowingInputSymbolsSame(), and TestMakeSymbolsSameClass().

686  {
687  typedef typename Arc::StateId StateId;
688  typedef typename Arc::Weight Weight;
689  typedef typename F::Result ClassType;
690  vector<StateId> bad_states;
691  ClassType noClass = f(kNoLabel);
692  ClassType epsClass = f(0);
693  for (StateIterator<Fst<Arc> > siter(*fst); !siter.Done(); siter.Next()) {
694  StateId s = siter.Value();
695  ClassType c = noClass;
696  bool bad = false;
697  for (ArcIterator<Fst<Arc> > aiter(*fst, s); !aiter.Done(); aiter.Next()) {
698  const Arc &arc = aiter.Value();
699  if (c == noClass)
700  c = f(arc.ilabel);
701  else
702  if (c != f(arc.ilabel)) {
703  bad = true;
704  break;
705  }
706  }
707  if (end_is_epsilon && c != noClass &&
708  c != epsClass && fst->Final(s) != Weight::Zero())
709  bad = true;
710  if (bad)
711  bad_states.push_back(s);
712  }
713  vector<Arc> my_arcs;
714  for (size_t i = 0; i < bad_states.size(); i++) {
715  StateId s = bad_states[i];
716  my_arcs.clear();
717  for (ArcIterator<MutableFst<Arc> > aiter(*fst, s); !aiter.Done(); aiter.Next())
718  my_arcs.push_back(aiter.Value());
719 
720  for (size_t j = 0; j < my_arcs.size(); j++) {
721  Arc &arc = my_arcs[j];
722  if (arc.ilabel != 0) {
723  StateId newstate = fst->AddState();
724  // Create a new state for each non-eps arc in original FST, out of each bad state.
725  // Not as optimal as it could be, but does avoid some complicated weight-pushing
726  // issues in which, to maintain stochasticity, we would have to know which semiring
727  // we want to maintain stochasticity in.
728  fst->AddArc(newstate, Arc(arc.ilabel, 0, Weight::One(), arc.nextstate));
729  MutableArcIterator<MutableFst<Arc> > maiter(fst, s);
730  maiter.Seek(j);
731  maiter.SetValue(Arc(0, arc.olabel, arc.weight, newstate));
732  }
733  }
734  }
735 }
fst::StdArc::StateId StateId
Definition: graph.dox:21
fst::StdArc::Weight Weight
void MakeLinearAcceptor ( const vector< I > &  labels,
MutableFst< Arc > *  ofst 
)

Creates unweighted linear acceptor from symbol sequence.

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

References rnnlm::i.

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

381  {
382  typedef typename Arc::StateId StateId;
383  typedef typename Arc::Weight Weight;
384 
385  ofst->DeleteStates();
386  StateId cur_state = ofst->AddState();
387  ofst->SetStart(cur_state);
388  for (size_t i = 0; i < labels.size(); i++) {
389  StateId next_state = ofst->AddState();
390  Arc arc(labels[i], labels[i], Weight::One(), next_state);
391  ofst->AddArc(cur_state, arc);
392  cur_state = next_state;
393  }
394  ofst->SetFinal(cur_state, Weight::One());
395 }
fst::StdArc::StateId StateId
fst::StdArc::Weight Weight
void MakeLinearAcceptorWithAlternatives ( const vector< 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 360 of file fstext-utils-inl.h.

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

361  {
362  typedef typename Arc::StateId StateId;
363  typedef typename Arc::Weight Weight;
364 
365  ofst->DeleteStates();
366  StateId cur_state = ofst->AddState();
367  ofst->SetStart(cur_state);
368  for (size_t i = 0; i < labels.size(); i++) {
369  KALDI_ASSERT(labels[i].size() != 0);
370  StateId next_state = ofst->AddState();
371  for (size_t j = 0; j < labels[i].size(); j++) {
372  Arc arc(labels[i][j], labels[i][j], Weight::One(), next_state);
373  ofst->AddArc(cur_state, arc);
374  }
375  cur_state = next_state;
376  }
377  ofst->SetFinal(cur_state, Weight::One());
378 }
fst::StdArc::StateId StateId
fst::StdArc::Weight Weight
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
VectorFst< Arc > * MakeLoopFst ( const 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 739 of file fstext-utils-inl.h.

References rnnlm::i, and KALDI_ASSERT.

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

739  {
740  typedef typename Arc::Weight Weight;
741  typedef typename Arc::StateId StateId;
742  typedef typename Arc::Label Label;
743 
744  VectorFst<Arc> *ans = new VectorFst<Arc>;
745  StateId loop_state = ans->AddState(); // = 0.
746  ans->SetStart(loop_state);
747  ans->SetFinal(loop_state, Weight::One());
748 
749  // "cache" is used as an optimization when some of the pointers in "fsts"
750  // may have the same value.
751  unordered_map<const ExpandedFst<Arc> *, Arc> cache;
752 
753  for (Label i = 0; i < static_cast<Label>(fsts.size()); i++) {
754  const ExpandedFst<Arc> *fst = fsts[i];
755  if (fst == NULL) continue;
756  { // optimization with cache: helpful if some members of "fsts" may
757  // contain the same pointer value (e.g. in GetHTransducer).
758  typename unordered_map<const ExpandedFst<Arc> *, Arc>::iterator
759  iter = cache.find(fst);
760  if (iter != cache.end()) {
761  Arc arc = iter->second;
762  arc.olabel = i;
763  ans->AddArc(0, arc);
764  continue;
765  }
766  }
767 
768  KALDI_ASSERT(fst->Properties(kAcceptor, true) == kAcceptor); // expect acceptor.
769 
770  StateId fst_num_states = fst->NumStates();
771  StateId fst_start_state = fst->Start();
772 
773  if (fst_start_state == kNoStateId)
774  continue; // empty fst.
775 
776  bool share_start_state =
777  fst->Properties(kInitialAcyclic, true) == kInitialAcyclic
778  && fst->NumArcs(fst_start_state) == 1
779  && fst->Final(fst_start_state) == Weight::Zero();
780 
781  vector<StateId> state_map(fst_num_states); // fst state -> ans state
782  for (StateId s = 0; s < fst_num_states; s++) {
783  if (s == fst_start_state && share_start_state) state_map[s] = loop_state;
784  else state_map[s] = ans->AddState();
785  }
786  if (!share_start_state) {
787  Arc arc(0, i, Weight::One(), state_map[fst_start_state]);
788  cache[fst] = arc;
789  ans->AddArc(0, arc);
790  }
791  for (StateId s = 0; s < fst_num_states; s++) {
792  // Add arcs out of state s.
793  for (ArcIterator<ExpandedFst<Arc> > aiter(*fst, s); !aiter.Done(); aiter.Next()) {
794  const Arc &arc = aiter.Value();
795  Label olabel = (s == fst_start_state && share_start_state ? i : 0);
796  Arc newarc(arc.ilabel, olabel, arc.weight, state_map[arc.nextstate]);
797  ans->AddArc(state_map[s], newarc);
798  if (s == fst_start_state && share_start_state)
799  cache[fst] = newarc;
800  }
801  if (fst->Final(s) != Weight::Zero()) {
802  KALDI_ASSERT(!(s == fst_start_state && share_start_state));
803  ans->AddArc(state_map[s], Arc(0, 0, fst->Final(s), loop_state));
804  }
805  }
806  }
807  return ans;
808 }
fst::StdArc::StateId StateId
Definition: graph.dox:21
fst::StdArc::Label Label
fst::StdArc::Weight Weight
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
VectorFst<Arc>* fst::MakeLoopFstCompare ( const vector< const ExpandedFst< Arc > * > &  fsts)

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

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

Referenced by TestMakeLoopFst().

296  {
297  VectorFst<Arc> *ans = new VectorFst<Arc>;
298  typedef typename Arc::Label Label;
299  typedef typename Arc::StateId StateId;
300  typedef typename Arc::Weight Weight;
301 
302  for (Label i = 0; i < fsts.size(); i++) {
303  if (fsts[i] != NULL) {
304  VectorFst<Arc> i_fst; // accepts symbol i on output.
305  i_fst.AddState(); i_fst.AddState();
306  i_fst.SetStart(0); i_fst.SetFinal(1, Weight::One());
307  i_fst.AddArc(0, Arc(0, i, Weight::One(), 1));
308  VectorFst<Arc> other_fst(*(fsts[i])); // copy it.
309  ClearSymbols(false, true, &other_fst); // Clear output symbols so symbols
310  // are on input side.
311  Concat(&i_fst, other_fst); // now i_fst is "i_fst [concat] other_fst".
312  Union(ans, i_fst);
313  }
314  }
315  Closure(ans, CLOSURE_STAR);
316  return ans;
317 }
fst::StdArc::StateId StateId
void Closure(MutableFst< Arc > *fst, std::set< typename Arc::StateId > *S, const vector< bool > &pVec)
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.
fst::StdArc::Label Label
fst::StdArc::Weight Weight
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 598 of file fstext-utils-inl.h.

References MakePrecedingInputSymbolsSameClass().

Referenced by TestMakeSymbolsSame().

598  {
599  IdentityFunction<typename Arc::Label> f;
600  MakePrecedingInputSymbolsSameClass(start_is_epsilon, fst, f);
601 }
Definition: graph.dox:21
void MakePrecedingInputSymbolsSameClass(bool start_is_epsilon, MutableFst< Arc > *fst, const F &f)
As MakePrecedingInputSymbolsSame, but takes a functor object that maps labels to classes.
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 604 of file fstext-utils-inl.h.

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

Referenced by kaldi::AddSelfLoopsBefore(), MakePrecedingInputSymbolsSame(), and TestMakeSymbolsSameClass().

604  {
605  typedef typename F::Result ClassType;
606  typedef typename Arc::StateId StateId;
607  typedef typename Arc::Weight Weight;
608  vector<ClassType> classes;
609  ClassType noClass = f(kNoLabel);
610  ClassType epsClass = f(0);
611  if (start_is_epsilon) { // treat having-start-state as epsilon in-transition.
612  StateId start_state = fst->Start();
613  if (start_state < 0 || start_state == kNoStateId) // empty FST.
614  return;
615  classes.resize(start_state+1, noClass);
616  classes[start_state] = epsClass;
617  }
618 
619  // Find bad states (states with multiple input-symbols into them).
620  std::set<StateId> bad_states; // states that we need to change.
621  for (StateIterator<Fst<Arc> > siter(*fst); !siter.Done(); siter.Next()) {
622  StateId s = siter.Value();
623  for (ArcIterator<Fst<Arc> > aiter(*fst, s); !aiter.Done(); aiter.Next()) {
624  const Arc &arc = aiter.Value();
625  if (classes.size() <= static_cast<size_t>(arc.nextstate))
626  classes.resize(arc.nextstate+1, noClass);
627  if (classes[arc.nextstate] == noClass)
628  classes[arc.nextstate] = f(arc.ilabel);
629  else
630  if (classes[arc.nextstate] != f(arc.ilabel))
631  bad_states.insert(arc.nextstate);
632  }
633  }
634  if (bad_states.empty()) return; // Nothing to do.
635  kaldi::ConstIntegerSet<StateId> bad_states_ciset(bad_states); // faster lookup.
636 
637  // Work out list of arcs we have to change as (state, arc-offset).
638  // Can't do the actual changes in this pass, since we have to add new
639  // states which invalidates the iterators.
640  vector<pair<StateId, size_t> > arcs_to_change;
641  for (StateIterator<Fst<Arc> > siter(*fst); !siter.Done(); siter.Next()) {
642  StateId s = siter.Value();
643  for (ArcIterator<Fst<Arc> > aiter(*fst, s); !aiter.Done(); aiter.Next()) {
644  const Arc &arc = aiter.Value();
645  if (arc.ilabel != 0 &&
646  bad_states_ciset.count(arc.nextstate) != 0)
647  arcs_to_change.push_back(std::make_pair(s, aiter.Position()));
648  }
649  }
650  KALDI_ASSERT(!arcs_to_change.empty()); // since !bad_states.empty().
651 
652  std::map<pair<StateId, ClassType>, StateId> state_map;
653  // state_map is a map from (bad-state, input-symbol-class) to dummy-state.
654 
655  for (size_t i = 0; i < arcs_to_change.size(); i++) {
656  StateId s = arcs_to_change[i].first;
657  ArcIterator<MutableFst<Arc> > aiter(*fst, s);
658  aiter.Seek(arcs_to_change[i].second);
659  Arc arc = aiter.Value();
660 
661  // Transition is non-eps transition to "bad" state. Introduce new state (or find
662  // existing one).
663  pair<StateId, ClassType> p(arc.nextstate, f(arc.ilabel));
664  if (state_map.count(p) == 0) {
665  StateId newstate = state_map[p] = fst->AddState();
666  fst->AddArc(newstate, Arc(0, 0, Weight::One(), arc.nextstate));
667  }
668  StateId dst_state = state_map[p];
669  arc.nextstate = dst_state;
670 
671  // Initialize the MutableArcIterator only now, as the call to NewState()
672  // may have invalidated the first arc iterator.
673  MutableArcIterator<MutableFst<Arc> > maiter(fst, s);
674  maiter.Seek(arcs_to_change[i].second);
675  maiter.SetValue(arc);
676  }
677 }
fst::StdArc::StateId StateId
Definition: graph.dox:21
fst::StdArc::Weight Weight
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
VectorFst<Arc>* fst::MakeRemapper ( const SymbolTable *  isymbols,
const SymbolTable *  osymbols 
)

The following function doesn't exactly belong here.

It creates an FST that transduces the isymbol to its matching osymbols, wherever they share the same string. It's useful for remapping symbol tables. You will have to explicitly specify the Arc template argument when you call this function, e.g. MakeRemapper<StdArc>(isyms, osyms).

void MapInputSymbols ( const 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 TestFactor().

169  {
171  // false == don't copy the "symbol_mapping", retain pointer--
172  // safe since short-lived object.
173  MapInputSymbolsMapper<Arc, I> mapper(symbol_mapping, false);
174  Map(fst, mapper);
175 }
#define KALDI_ASSERT_IS_INTEGER_TYPE(I)
Definition: kaldi-utils.h:130
Definition: graph.dox:21
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.

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

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

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

276  {
277  CompactLatticeMinimizer<Weight, IntType> minimizer(clat, delta);
278  return minimizer.Minimize();
279 }
template bool fst::MinimizeCompactLattice< kaldi::LatticeWeight, kaldi::int32 > ( MutableFst< kaldi::CompactLatticeArc > *  clat,
float  delta 
)
void fst::MinimizeEncoded ( VectorFst< Arc > *  fst,
float  delta = kDelta 
)

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

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

114  {
115 
116  Map(fst, QuantizeMapper<Arc>(delta));
117  EncodeMapper<Arc> encoder(kEncodeLabels | kEncodeWeights, ENCODE);
118  Encode(fst, &encoder);
119  AcceptorMinimize(fst);
120  Decode(fst, encoder);
121 }
Definition: graph.dox:21
void NbestAsFsts ( const Fst< Arc > &  fst,
size_t  n,
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 349 of file fstext-utils-inl.h.

References ConvertNbestToVector(), and KALDI_ASSERT.

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

351  {
352  KALDI_ASSERT(n > 0);
353  KALDI_ASSERT(fsts_out != NULL);
354  VectorFst<Arc> nbest_fst;
355  ShortestPath(fst, &nbest_fst, n);
356  ConvertNbestToVector(nbest_fst, fsts_out);
357 }
struct rnnlm::@11::@12 n
void ConvertNbestToVector(const Fst< Arc > &fst, vector< VectorFst< Arc > > *fsts_out)
This function converts an FST with a special structure, which is output by the OpenFst functions Shor...
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
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(), ContextFstImpl< Arc, LabelT >::NumArcs(), and TrivialFactorWeightFstImpl< A, F >::NumArcs().

67  {
68  typedef typename Arc::StateId StateId;
69  StateId num_arcs = 0;
70  for (StateId s = 0; s < fst.NumStates(); s++)
71  num_arcs += fst.NumArcs(s);
72  return num_arcs;
73 }
fst::StdArc::StateId StateId
Definition: graph.dox:21
bool fst::operator!= ( const LatticeWeightTpl< FloatType > &  wa,
const LatticeWeightTpl< FloatType > &  wb 
)
inline

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

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

279  {
280  // Volatile qualifier thwarts over-aggressive compiler optimizations
281  // that lead to problems esp. with NaturalLess().
282  volatile FloatType va1 = wa.Value1(), va2 = wa.Value2(),
283  vb1 = wb.Value1(), vb2 = wb.Value2();
284  return (va1 != vb1 || va2 != vb2);
285 }
bool fst::operator!= ( const CompactLatticeWeightTpl< WeightType, IntType > &  w1,
const CompactLatticeWeightTpl< WeightType, IntType > &  w2 
)
inline

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

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

535  {
536  return (w1.Weight() != w2.Weight() || w1.String() != w2.String());
537 }
ostream & operator<< ( ostream &  strm,
const LatticeWeightTpl< FloatType > &  w 
)
inline

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

References LatticeWeightTpl< FloatType >::WriteFloatType().

367  {
368  LatticeWeightTpl<FloatType>::WriteFloatType(strm, w.Value1());
369  CHECK(FLAGS_fst_weight_separator.size() == 1);
370  strm << FLAGS_fst_weight_separator[0]; // comma by default;
371  // may or may not be settable from Kaldi programs.
372  LatticeWeightTpl<FloatType>::WriteFloatType(strm, w.Value2());
373  return strm;
374 }
ostream& fst::operator<< ( ostream &  strm,
const CompactLatticeWeightTpl< WeightType, IntType > &  w 
)
inline

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

References rnnlm::i.

668  {
669  strm << w.Weight();
670  CHECK(FLAGS_fst_weight_separator.size() == 1);
671  strm << FLAGS_fst_weight_separator[0]; // comma by default.
672  for(size_t i = 0; i < w.String().size(); i++) {
673  strm << w.String()[i];
674  if (i+1 < w.String().size())
675  strm << kStringSeparator; // '_'; defined in string-weight.h in OpenFst code.
676  }
677  return strm;
678 }
bool fst::operator== ( const LatticeWeightTpl< FloatType > &  wa,
const LatticeWeightTpl< FloatType > &  wb 
)
inline

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

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

269  {
270  // Volatile qualifier thwarts over-aggressive compiler optimizations
271  // that lead to problems esp. with NaturalLess().
272  volatile FloatType va1 = wa.Value1(), va2 = wa.Value2(),
273  vb1 = wb.Value1(), vb2 = wb.Value2();
274  return (va1 == vb1 && va2 == vb2);
275 }
bool fst::operator== ( const CompactLatticeWeightTpl< WeightType, IntType > &  w1,
const CompactLatticeWeightTpl< WeightType, IntType > &  w2 
)
inline

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

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

529  {
530  return (w1.Weight() == w2.Weight() && w1.String() == w2.String());
531 }
istream & operator>> ( istream &  strm,
LatticeWeightTpl< FloatType > &  w 
)
inline

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

References LatticeWeightTpl< FloatType >::ReadNoParen().

377  {
378  CHECK(FLAGS_fst_weight_separator.size() == 1);
379  // separator defaults to ','
380  return w1.ReadNoParen(strm, FLAGS_fst_weight_separator[0]);
381 }
istream& fst::operator>> ( istream &  strm,
CompactLatticeWeightTpl< WeightType, IntType > &  w 
)
inline

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

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

681  {
682  std::string s;
683  strm >> s;
684  if (strm.fail()) {
685  return strm;
686  }
687  CHECK(FLAGS_fst_weight_separator.size() == 1);
688  size_t pos = s.find_last_of(FLAGS_fst_weight_separator); // normally ","
689  if (pos == std::string::npos) {
690  strm.clear(std::ios::badbit);
691  return strm;
692  }
693  // get parts of str before and after the separator (default: ',');
694  std::string s1(s, 0, pos), s2(s, pos+1);
695  std::istringstream strm1(s1);
696  WeightType weight;
697  strm1 >> weight;
698  w.SetWeight(weight);
699  if (strm1.fail() || !strm1.eof()) {
700  strm.clear(std::ios::badbit);
701  return strm;
702  }
703  // read string part.
704  vector<IntType> string;
705  const char *c = s2.c_str();
706  while(*c != '\0') {
707  if (*c == kStringSeparator) // '_'
708  c++;
709  char *c2;
710  long int i = strtol(c, &c2, 10);
711  if (c2 == c || static_cast<long int>(static_cast<IntType>(i)) != i) {
712  strm.clear(std::ios::badbit);
713  return strm;
714  }
715  c = c2;
716  string.push_back(static_cast<IntType>(i));
717  }
718  w.SetString(string);
719  return strm;
720 }
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().

60  {
61  typedef typename Arc::StateId StateId;
62  typedef typename Arc::Label Label;
63  typedef typename Arc::Weight Weight;
64 
65  Weight penalty_weight(penalty);
66 
67  kaldi::ConstIntegerSet<I> symbol_set(symbols_in);
68 
69  StateId num_states = fst->NumStates();
70  for (StateId s = 0; s < num_states; s++) {
71  for (MutableArcIterator<VectorFst<Arc> > iter(fst, s);
72  !iter.Done(); iter.Next()) {
73  if (symbol_set.count(iter.Value().ilabel) != 0) {
74  Arc arc = iter.Value();
75  arc.weight = Times(arc.weight, penalty_weight);
76  iter.SetValue(arc);
77  }
78  }
79  }
80 }
fst::StdArc::StateId StateId
Definition: graph.dox:21
LatticeWeightTpl< FloatType > Times(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2)
fst::StdArc::Label Label
fst::StdArc::Weight Weight
void PhiCompose ( const Fst< Arc > &  fst1,
const Fst< Arc > &  fst2,
typename Arc::Label  phi_label,
MutableFst< Arc > *  ofst 
)

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

References KALDI_ASSERT.

Referenced by main().

1094  {
1095  KALDI_ASSERT(phi_label != kNoLabel); // just use regular compose in this case.
1096  typedef Fst<Arc> F;
1097  typedef PhiMatcher<SortedMatcher<F> > PM;
1098  CacheOptions base_opts;
1099  base_opts.gc_limit = 0; // Cache only the last state for fastest copy.
1100  // ComposeFstImplOptions templated on matcher for fst1, matcher for fst2.
1101  // The matcher for fst1 doesn't matter; we'll use fst2's matcher.
1102  ComposeFstImplOptions<SortedMatcher<F>, PM> impl_opts(base_opts);
1103 
1104  // the false below is something called phi_loop which is something I don't
1105  // fully understand, but I don't think we want it.
1106 
1107  // These pointers are taken ownership of, by ComposeFst.
1108  PM *phi_matcher =
1109  new PM(fst2, MATCH_INPUT, phi_label, false);
1110  SortedMatcher<F> *sorted_matcher =
1111  new SortedMatcher<F>(fst1, MATCH_NONE); // tell it
1112  // not to use this matcher, as this would mean we would
1113  // not follow phi transitions.
1114  impl_opts.matcher1 = sorted_matcher;
1115  impl_opts.matcher2 = phi_matcher;
1116  *ofst = ComposeFst<Arc>(fst1, fst2, impl_opts);
1117  Connect(ofst);
1118 }
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
ArcticWeightTpl<T> fst::Plus ( const ArcticWeightTpl< T > &  w1,
const ArcticWeightTpl< T > &  w2 
)
inline

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

88  {
89  return w1.Value() > w2.Value() ? w1 : w2;
90 }
ArcticWeightTpl<float> fst::Plus ( const ArcticWeightTpl< float > &  w1,
const ArcticWeightTpl< float > &  w2 
)
inline

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

93  {
94  return Plus<float>(w1, w2);
95 }
ArcticWeightTpl<double> fst::Plus ( const ArcticWeightTpl< double > &  w1,
const ArcticWeightTpl< double > &  w2 
)
inline

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

98  {
99  return Plus<double>(w1, w2);
100 }
CompactLatticeWeightTpl<WeightType, IntType> fst::Plus ( const CompactLatticeWeightTpl< WeightType, IntType > &  w1,
const CompactLatticeWeightTpl< WeightType, IntType > &  w2 
)
inline

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

References Compare().

605  {
606  return (Compare(w1, w2) >= 0 ? w1 : w2);
607 }
int Compare(const TropicalWeight &w1, const TropicalWeight &w2)
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 530 of file fstext-utils-inl.h.

References PrecedingInputSymbolsAreSameClass().

Referenced by TestMakeSymbolsSame().

530  {
531  IdentityFunction<typename Arc::Label> f;
532  return PrecedingInputSymbolsAreSameClass(start_is_epsilon, fst, f);
533 }
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...
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.

The function tests whether the symbols preceding any given state are in the same class. Formally, f is of a type F that has an operator of type F::Result F::operator() (F::Arg a) const; where F::Result is an integer type and F::Arc can be constructed from Arc::Label. this must apply to valid labels and also to kNoLabel (so we can have a marker for the invalid labels.

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

Referenced by PrecedingInputSymbolsAreSame(), and TestMakeSymbolsSameClass().

536  {
537  typedef typename F::Result ClassType;
538  typedef typename Arc::StateId StateId;
539  vector<ClassType> classes;
540  ClassType noClass = f(kNoLabel);
541 
542  if (start_is_epsilon) {
543  StateId start_state = fst.Start();
544  if (start_state < 0 || start_state == kNoStateId)
545  return true; // empty fst-- doesn't matter.
546  classes.resize(start_state+1, noClass);
547  classes[start_state] = 0;
548  }
549 
550  for (StateIterator<Fst<Arc> > siter(fst); !siter.Done(); siter.Next()) {
551  StateId s = siter.Value();
552  for (ArcIterator<Fst<Arc> > aiter(fst, s); !aiter.Done(); aiter.Next()) {
553  const Arc &arc = aiter.Value();
554  if (classes.size() <= arc.nextstate)
555  classes.resize(arc.nextstate+1, noClass);
556  if (classes[arc.nextstate] == noClass)
557  classes[arc.nextstate] = f(arc.ilabel);
558  else
559  if (classes[arc.nextstate] != f(arc.ilabel))
560  return false;
561  }
562  }
563  return true;
564 }
fst::StdArc::StateId StateId
void PreDeterminize ( MutableFst< Arc > *  fst,
typename Arc::Label  first_new_sym,
vector< Int > *  symsOut 
)

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

References fst::pre_determinize_helpers::Closure(), fst::pre_determinize_helpers::CopySetToVector(), CreateSuperFinal(), rnnlm::i, fst::pre_determinize_helpers::InsertMember(), KALDI_ASSERT, KALDI_ERR, KALDI_VLOG, and rnnlm::n.

Referenced by SafeDeterminizeMinimizeWrapper(), SafeDeterminizeWrapper(), TestDeterminize(), TestDeterminizeStarInLog(), TestFactor(), TestMinimize(), TestPreDeterminize(), and TestPush().

319  {
320  typedef typename Arc::Label Label;
321  typedef typename Arc::StateId StateId;
322  typedef size_t ArcId; // Our own typedef, not standard OpenFst. Use size_t
323  // for compatibility with argument of ArcIterator::Seek().
324  typedef typename Arc::Weight Weight;
325  assert(first_new_sym > 0);
326  assert(fst != NULL);
327  if (fst->Start() == kNoStateId) return; // for empty FST, nothing to do.
328  assert(symsOut != NULL && symsOut->size() == 0); // we will output the symbols we add into this.
329 
330  { // (D)(i)(a): check is trim (i.e. connected, in OpenFST parlance).
331  KALDI_VLOG(2) << "PreDeterminize: Checking FST properties";
332  uint64 props = fst->Properties(kAccessible|kCoAccessible, true); // true-> computes properties if unknown at time when called.
333  if (props != (kAccessible|kCoAccessible)) { // All states are not both accessible and co-accessible...
334  KALDI_ERR << "PreDeterminize: FST is not trim";
335  }
336  }
337 
338  { // (D)(i)(b): make single final state.
339  KALDI_VLOG(2) << "PreDeterminize: creating single final state";
341  }
342 
343  { // (D)(i)(c): sort arcs on input.
344  KALDI_VLOG(2) << "PreDeterminize: sorting arcs on input";
345  ILabelCompare<Arc> icomp;
346  ArcSort(fst, icomp);
347  }
348 
349  StateId n_states = 0, max_state = 0; // Compute n_states, max_state = highest-numbered state.
350  { // compute nStates, maxStates.
351  for (StateIterator<MutableFst<Arc> > iter(*fst); ! iter.Done(); iter.Next()) {
352  StateId state = iter.Value();
353  assert(state>=0);
354  n_states++;
355  if (state > max_state) max_state = state;
356  }
357  KALDI_VLOG(2) << "PreDeterminize: n_states = "<<(n_states)<<", max_state ="<<(max_state);
358  }
359 
360  vector<bool> p_vec(max_state+1, false); // compute this next.
361  { // D(ii): computing the array p. ["problematic states, i.e. states with >1 input transition,
362  // counting being the initial state as an input transition"].
363  vector<bool> seen_vec(max_state+1, false); // rather than counting incoming transitions we just have a bool that says we saw at least one.
364 
365  seen_vec[fst->Start()] = true;
366  for (StateIterator<MutableFst<Arc> > siter(*fst); ! siter.Done(); siter.Next()) {
367  for (ArcIterator<MutableFst<Arc> > aiter(*fst, siter.Value()); ! aiter.Done(); aiter.Next()) {
368  const Arc &arc = aiter.Value();
369  assert(arc.nextstate>=0&&arc.nextstate<max_state+1);
370  if (seen_vec[arc.nextstate])
371  p_vec[arc.nextstate] = true; // now have >1 transition in, so problematic.
372  else
373  seen_vec[arc.nextstate] = true;
374  }
375  }
376  }
377  // D(iii): set up m(a)
378  std::map<pair<StateId, ArcId>, size_t> m_map;
379  // This is the array m, indexed by arcs. It maps to the index of the symbol we add.
380 
381 
382  // WARNING: we should be sure to clean up this memory before exiting. Do not return
383  // or throw an exception from this function, later than this point, without cleaning up!
384  // Note that the vectors are shared between Q and S (they "belong to" S.
385  vector<vector<StateId>* > S(max_state+1, (vector<StateId>*)(void*)0);
386  vector<pair<vector<StateId>*, size_t> > Q;
387 
388  // D(iv): initialize S and Q.
389  {
390  vector<StateId> all_seed_states; // all "problematic" states, plus initial state (if not problematic).
391  if (!p_vec[fst->Start()])
392  all_seed_states.push_back(fst->Start());
393  for (StateId s = 0;s<=max_state; s++)
394  if (p_vec[s]) all_seed_states.push_back(s);
395 
396  for (size_t idx = 0;idx < all_seed_states.size(); idx++) {
397  StateId s = all_seed_states[idx];
398  std::set<StateId> closure_s;
399  closure_s.insert(s); // insert "seed" state.
400  pre_determinize_helpers::Closure(fst, &closure_s, p_vec); // follow epsilons to non-problematic states.
401  // Closure in this case whis will usually not add anything, for typical topologies in speech
402  vector<StateId> closure_s_vec;
403  pre_determinize_helpers::CopySetToVector(closure_s, &closure_s_vec);
404  KALDI_ASSERT(closure_s_vec.size() != 0);
405  vector<StateId> *ptr = pre_determinize_helpers::InsertMember(closure_s_vec, &S);
406  KALDI_ASSERT(ptr != NULL); // Or conceptual bug or programming error.
407  Q.push_back(pair<vector<StateId>*, size_t>(ptr, 0));
408  }
409  }
410 
411  vector<bool> d_vec(max_state+1, false); // "done vector". Purely for debugging.
412 
413 
414  size_t num_extra_det_states = 0;
415 
416  // (D)(v)
417  while (Q.size() != 0) {
418 
419  // (D)(v)(a)
420  pair<vector<StateId>*, size_t> cur_pair(Q.back());
421  Q.pop_back();
422  const vector<StateId> &A(*cur_pair.first);
423  size_t n =cur_pair.second; // next special symbol to add.
424 
425  // (D)(v)(b)
426  for (size_t idx = 0;idx < A.size(); idx++) {
427  assert(d_vec[A[idx]] == false && "This state has been seen before. Algorithm error.");
428  d_vec[A[idx]] = true;
429  }
430 
431  // From here is (D)(v)(c). We work out S_\eps and S_t (for t\neq eps)
432  // simultaneously at first.
433  map<Label, set<pair<pair<StateId, ArcId>, StateId> > > arc_hash;
434  // arc_hash is a hash with info of all arcs from states in the set A to
435  // non-problematic states.
436  // It is a map from ilabel to pair(pair(start-state, arc-offset), end-state).
437  // Here, arc-offset reflects the order in which we accessed the arc using the
438  // ArcIterator (zero for the first arc).
439 
440 
441  { // This block sets up arc_hash
442  for (size_t idx = 0;idx < A.size(); idx++) {
443  StateId s = A[idx];
444  assert(s>=0 && s<=max_state);
445  ArcId arc_id = 0;
446  for (ArcIterator<MutableFst<Arc> > aiter(*fst, s); ! aiter.Done(); aiter.Next(), ++arc_id) {
447  const Arc &arc = aiter.Value();
448 
449  pair<pair<StateId, ArcId>, StateId>
450  this_pair(pair<StateId, ArcId>(s, arc_id), arc.nextstate);
451  bool inserted = (arc_hash[arc.ilabel].insert(this_pair)).second;
452  assert(inserted); // Otherwise we had a duplicate.
453  }
454  }
455  }
456 
457  // (D)(v)(d)
458  if (arc_hash.count(0) == 1) { // We have epsilon transitions out.
459  set<pair<pair<StateId, ArcId>, StateId> > &eps_set = arc_hash[0];
460  typedef typename set<pair<pair<StateId, ArcId>, StateId> >::iterator set_iter_t;
461  for (set_iter_t siter = eps_set.begin(); siter != eps_set.end(); ++siter) {
462  const pair<pair<StateId, ArcId>, StateId> &this_pr = *siter;
463  if (p_vec[this_pr.second]) { // Eps-transition to problematic state.
464  assert(m_map.count(this_pr.first) == 0);
465  m_map[this_pr.first] = n;
466  n++;
467  }
468  }
469  }
470 
471  // (D)(v)(e)
472  {
473  typedef typename map<Label, set<pair<pair<StateId, ArcId>, StateId> > >::iterator map_iter_t;
474  typedef typename set<pair<pair<StateId, ArcId>, StateId> >::iterator set_iter_t2;
475  for (map_iter_t miter = arc_hash.begin(); miter != arc_hash.end(); ++miter) {
476  Label t = miter->first;
477  set<pair<pair<StateId, ArcId>, StateId> > &S_t = miter->second;
478  if (t != 0) { // For t != epsilon,
479  set<StateId> V_t; // set of destination non-problem states. Will create this set now.
480 
481  // exists_noproblem is true iff |U_t| > 0.
482  size_t k = 0;
483 
484  // First loop "for each transition a in T_t" (i.e. transitions to problematic states)
485  // The if-statement if (|S_t|>1) is pushed inside the loop, as the loop also computes
486  // the set V_t.
487  for (set_iter_t2 siter = S_t.begin(); siter != S_t.end(); ++siter) {
488  const pair<pair<StateId, ArcId>, StateId> &this_pr = *siter;
489  if (p_vec[this_pr.second]) { // only consider problematic states (just set T_t)
490  if (S_t.size() > 1) { // This is where we pushed the if-statement in.
491  assert(m_map.count(this_pr.first) == 0);
492  m_map[this_pr.first] = k;
493  k++;
494  num_extra_det_states++;
495  }
496  } else { // Create the set V_t.
497  V_t.insert(this_pr.second);
498  }
499  }
500  if (V_t.size() != 0) {
501  pre_determinize_helpers::Closure(fst, &V_t, p_vec); // follow epsilons to non-problematic states.
502  vector<StateId> closure_V_t_vec;
503  pre_determinize_helpers::CopySetToVector(V_t, &closure_V_t_vec);
504  vector<StateId> *ptr = pre_determinize_helpers::InsertMember(closure_V_t_vec, &S);
505  if (ptr != NULL) { // was inserted.
506  Q.push_back(pair<vector<StateId>*, size_t>(ptr, k));
507  }
508  }
509  }
510  }
511  }
512  } // end while (Q.size() != 0)
513 
514 
515  { // (D)(vi): Check that for each state in the FST, d(s) = true.
516  for (StateIterator<MutableFst<Arc> > siter(*fst); ! siter.Done(); siter.Next()) {
517  StateId val = siter.Value();
518  assert(d_vec[val] == true);
519  }
520  }
521 
522  { // (D)(vii): compute symbol-table ID's.
523  // sets up symsOut array.
524  int64 n = -1;
525  for (typename map<pair<StateId, ArcId>, size_t>::iterator m_iter = m_map.begin();
526  m_iter != m_map.end();
527  ++m_iter) {
528  n = std::max(n, (int64) m_iter->second); // m_iter->second is of type size_t.
529  }
530  // At this point n is the highest symbol-id (type size_t) of symbols we must add.
531  n++; // This is now the number of symbols we must add.
532  for (size_t i = 0;static_cast<int64>(i)<n;i++) symsOut->push_back(first_new_sym + i);
533  }
534 
535  // (D)(viii): set up hash.
536  map<pair<StateId, size_t>, StateId> h_map;
537 
538  { // D(ix): add extra symbols! This is where the work gets done.
539 
540  // Core part of this is below, search for (*)
541  size_t n_states_added = 0;
542 
543  for (typename map<pair<StateId, ArcId>, size_t>::iterator m_iter = m_map.begin();
544  m_iter != m_map.end();
545  ++m_iter) {
546  StateId state = m_iter->first.first;
547  ArcId arcpos = m_iter->first.second;
548  size_t m_a = m_iter->second;
549 
550  MutableArcIterator<MutableFst<Arc> > aiter(fst, state);
551  aiter.Seek(arcpos);
552  Arc arc = aiter.Value();
553 
554  // (*) core part here.
555  if (arc.ilabel == 0)
556  arc.ilabel = (*symsOut)[m_a];
557  else {
558  pair<StateId, size_t> pr(arc.nextstate, m_a);
559  if (!h_map.count(pr)) {
560  n_states_added++;
561  StateId newstate = fst->AddState();
562  assert(newstate>=0);
563  Arc new_arc( (*symsOut)[m_a], (Label)0, Weight::One(), arc.nextstate);
564  fst->AddArc(newstate, new_arc);
565  h_map[pr] = newstate;
566  }
567  arc.nextstate = h_map[pr];
568  }
569  aiter.SetValue(arc);
570  }
571 
572  KALDI_VLOG(2) << "Added " <<(n_states_added)<<" new states and added/changed "<<(m_map.size())<<" arcs";
573 
574  }
575  // Now free up memory.
576  for (size_t i = 0;i < S.size();i++)
577  delete S[i];
578 } // end function PreDeterminize
fst::StdArc::StateId StateId
void Closure(MutableFst< Arc > *fst, std::set< typename Arc::StateId > *S, const vector< bool > &pVec)
vector< T > * InsertMember(const vector< T > m, vector< vector< T > * > *S)
Definition: graph.dox:21
struct rnnlm::@11::@12 n
Arc::StateId CreateSuperFinal(MutableFst< Arc > *fst)
#define KALDI_ERR
Definition: kaldi-error.h:127
fst::StdArc::Label Label
fst::StdArc::Weight Weight
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
#define KALDI_VLOG(v)
Definition: kaldi-error.h:136
void CopySetToVector(const std::set< T > s, vector< T > *v)
void fst::Print ( const Fst< Arc > &  fst,
std::string  message 
)

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

377  {
378  std::cout << message << "\n";
379 #ifdef HAVE_OPENFST_GE_10400
380  FstPrinter<Arc> fstprinter(fst, NULL, NULL, NULL, false, true, "\t");
381 #else
382  FstPrinter<Arc> fstprinter(fst, NULL, NULL, NULL, false, true);
383 #endif
384  fstprinter.Print(&std::cout, "standard output");
385 }
bool fst::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 
)

Definition at line 29 of file generate-proxy-keywords.cc.

References Times().

Referenced by main().

34  {
35  if (proxy.Final(cur_state) != StdArc::Weight::Zero()) {
36  // Assumes only final state has non-zero weight.
37  cur_weight = Times(proxy.Final(cur_state), cur_weight);
38  path->push_back(cur_path);
39  weight->push_back(cur_weight);
40  return true;
41  }
42 
43  for (ArcIterator<StdFst> aiter(proxy, cur_state);
44  !aiter.Done(); aiter.Next()) {
45  const StdArc &arc = aiter.Value();
46  StdArc::Weight temp_weight = Times(arc.weight, cur_weight);
47  cur_path.push_back(arc.ilabel);
48  PrintProxyFstPath(proxy, path, weight,
49  arc.nextstate, cur_path, temp_weight);
50  cur_path.pop_back();
51  }
52 
53  return true;
54 }
fst::StdArc StdArc
LatticeWeightTpl< FloatType > Times(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2)
fst::StdArc::Weight Weight
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)
void PropagateFinal ( typename Arc::Label  phi_label,
MutableFst< Arc > *  fst 
)

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

References KALDI_WARN, and PropagateFinalInternal().

Referenced by main().

1155  {
1156  typedef typename Arc::StateId StateId;
1157  if (fst->Properties(kIEpsilons, true)) // just warn.
1158  KALDI_WARN << "PropagateFinal: this may not work as desired "
1159  "since your FST has input epsilons.";
1160  StateId num_states = fst->NumStates();
1161  for (StateId s = 0; s < num_states; s++)
1162  PropagateFinalInternal(phi_label, s, fst);
1163 }
fst::StdArc::StateId StateId
Definition: graph.dox:21
#define KALDI_WARN
Definition: kaldi-error.h:130
void PropagateFinalInternal(typename Arc::Label phi_label, typename Arc::StateId s, MutableFst< Arc > *fst)
void fst::PropagateFinalInternal ( typename Arc::Label  phi_label,
typename Arc::StateId  s,
MutableFst< Arc > *  fst 
)

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

References KALDI_ASSERT, and Times().

Referenced by PropagateFinal().

1124  {
1125  typedef typename Arc::Weight Weight;
1126  if (fst->Final(s) == Weight::Zero()) {
1127  // search for phi transition. We assume there
1128  // is just one-- phi nondeterminism is not allowed
1129  // anyway.
1130  int num_phis = 0;
1131  for (ArcIterator<Fst<Arc> > aiter(*fst, s);
1132  !aiter.Done(); aiter.Next()) {
1133  const Arc &arc = aiter.Value();
1134  if (arc.ilabel == phi_label) {
1135  num_phis++;
1136  if (arc.nextstate == s) continue; // don't expect
1137  // phi loops but ignore them anyway.
1138 
1139  // If this recurses infinitely, it means there
1140  // are loops of phi transitions, which there should
1141  // not be in a normal backoff LM. We could make this
1142  // routine work for this case, but currently there is
1143  // no need.
1144  PropagateFinalInternal(phi_label, arc.nextstate, fst);
1145  if (fst->Final(arc.nextstate) != Weight::Zero())
1146  fst->SetFinal(s, Times(fst->Final(arc.nextstate), arc.weight));
1147  }
1148  KALDI_ASSERT(num_phis <= 1 && "Phi nondeterminism found");
1149  }
1150  }
1151 }
Definition: graph.dox:21
LatticeWeightTpl< FloatType > Times(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2)
fst::StdArc::Weight Weight
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
void PropagateFinalInternal(typename Arc::Label phi_label, typename Arc::StateId s, MutableFst< Arc > *fst)
void fst::PruneCompactLattice ( Weight  beam,
MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, Int > > > *  fst 
)
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.

It supports pruning either to a specified beam (if beam is not One()), or to a specified max_states (if max_states is > 0). One of the two must be specified.

Requirements:

  • Costs must be non-negative (equivalently, weights must not be greater than One()).
  • There must be a Compare(a, b) function that compares two weights and returns (-1,0,1) if (a<b, a=b, a>b). We define this in Kaldi, for TropicalWeight, LogWeight (I think), and LatticeWeight... also CompactLatticeWeight, but we doubt that will be used here; better to use PruneCompactLattice().

Definition at line 161 of file prune-special-inl.h.

Referenced by main().

164  {
165  PruneSpecialClass<Arc> c(ifst, ofst, beam, max_states);
166 }
bool PushCompactLatticeStrings ( MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, IntType > > > *  clat)

This function pushes the transition-ids as far towards the start as they will go.

It can be useful prior to lattice-align-words (for non-linear lattices). We can't use the generic OpenFst "push" function because it uses the sum as the divisor, which is not appropriate in this case (a+b generally won't divide a or b in this semiring). It returns true on success, false if it failed due to TopSort failing, which should never happen, but we handle it gracefully by just leaving the lattice the same. This function used to be called just PushCompactLattice.

Definition at line 209 of file push-lattice.cc.

References CompactLatticePusher< Weight, IntType >::Push().

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

210  {
211  CompactLatticePusher<Weight, IntType> pusher(clat);
212  return pusher.Push();
213 }
template bool fst::PushCompactLatticeStrings< kaldi::LatticeWeight, kaldi::int32 > ( MutableFst< kaldi::CompactLatticeArc > *  clat)
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.

interpreting the weights as negated log-probs). It returns true on success, false if it failed due to TopSort failing, which should never happen, but we handle it gracefully by just leaving the lattice the same.

Definition at line 216 of file push-lattice.cc.

References Divide(), KALDI_ASSERT, KALDI_WARN, Plus(), and Times().

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

217  {
218  if (clat->Properties(kTopSorted, true) == 0) {
219  if (!TopSort(clat)) {
220  KALDI_WARN << "Topological sorting of state-level lattice failed "
221  "(probably your lexicon has empty words or your LM has epsilon cycles; this "
222  " is a bad idea.)";
223  return false;
224  }
225  }
226  typedef CompactLatticeWeightTpl<Weight, IntType> CompactWeight;
227  typedef ArcTpl<CompactWeight> CompactArc;
228  typedef typename CompactArc::StateId StateId;
229 
230  StateId num_states = clat->NumStates();
231  if (num_states == 0) {
232  KALDI_WARN << "Pushing weights of empty compact lattice";
233  return true; // this is technically success because an empty
234  // lattice is already pushed.
235  }
236  std::vector<Weight> weight_to_end(num_states); // Note: LatticeWeight
237  // contains two floats.
238  for (StateId s = num_states - 1; s >= 0; s--) {
239  Weight this_weight_to_end = clat->Final(s).Weight();
240  for (ArcIterator<MutableFst<CompactArc> > aiter(*clat, s);
241  !aiter.Done(); aiter.Next()) {
242  const CompactArc &arc = aiter.Value();
243  KALDI_ASSERT(arc.nextstate > s && "Cyclic lattices not allowed.");
244  this_weight_to_end = Plus(this_weight_to_end,
245  Times(aiter.Value().weight.Weight(),
246  weight_to_end[arc.nextstate]));
247  }
248  if (this_weight_to_end == Weight::Zero()) {
249  KALDI_WARN << "Lattice has non-coaccessible states.";
250  }
251  weight_to_end[s] = this_weight_to_end;
252  }
253  weight_to_end[0] = Weight::One(); // We leave the "leftover weight" on
254  // the start state, which won't
255  // necessarily end up summing to one.
256  for (StateId s = 0; s < num_states; s++) {
257  Weight this_weight_to_end = weight_to_end[s];
258  if (this_weight_to_end == Weight::Zero())
259  continue;
260  for (MutableArcIterator<MutableFst<CompactArc> > aiter(clat, s);
261  !aiter.Done(); aiter.Next()) {
262  CompactArc arc = aiter.Value();
263  Weight next_weight_to_end = weight_to_end[arc.nextstate];
264  if (next_weight_to_end != Weight::Zero()) {
265  arc.weight.SetWeight(Times(arc.weight.Weight(),
266  Divide(next_weight_to_end,
267  this_weight_to_end)));
268  aiter.SetValue(arc);
269  }
270  }
271  CompactWeight final_weight = clat->Final(s);
272  if (final_weight != CompactWeight::Zero()) {
273  final_weight.SetWeight(Divide(final_weight.Weight(), this_weight_to_end));
274  clat->SetFinal(s, final_weight);
275  }
276  }
277 
278  return true;
279 }
fst::StdArc::StateId StateId
LatticeWeightTpl< FloatType > Divide(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2, DivideType typ=DIVIDE_ANY)
LatticeWeightTpl< FloatType > Plus(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2)
LatticeWeightTpl< FloatType > Times(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2)
#define KALDI_WARN
Definition: kaldi-error.h:130
fst::StdArc::Weight Weight
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
template bool fst::PushCompactLatticeWeights< kaldi::LatticeWeight, kaldi::int32 > ( MutableFst< kaldi::CompactLatticeArc > *  clat)
void fst::PushInLog ( VectorFst< StdArc > *  fst,
uint32  ptype,
float  delta = kDelta 
)

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

91  {
92 
93  // PushInLog pushes the FST
94  // and returns a new pushed FST (labels and weights pushed to the left).
95  VectorFst<LogArc> *fst_log = new VectorFst<LogArc>; // Want to determinize in log semiring.
96  Cast(*fst, fst_log);
97  VectorFst<StdArc> tmp;
98  *fst = tmp; // free up memory.
99  VectorFst<LogArc> *fst_pushed_log = new VectorFst<LogArc>;
100  Push<LogArc, rtype>(*fst_log, fst_pushed_log, ptype, delta);
101  Cast(*fst_pushed_log, fst);
102  delete fst_log;
103  delete fst_pushed_log;
104 }
Definition: graph.dox:21
void PushSpecial ( VectorFst< StdArc > *  fst,
float  delta 
)

Definition at line 226 of file push-special.cc.

Referenced by main(), and TestPushSpecial().

226  {
227  if (fst->NumStates() > 0)
228  PushSpecialClass c(fst, delta); // all the work
229  // gets done in the initializer.
230 }
Definition: graph.dox:21
VectorFst<Arc>* fst::RandFst ( RandFstOptions  opts = RandFstOptions())

Returns a random FST.

Useful for randomized algorithm testing. Only works if weight can be constructed from float.

Definition at line 56 of file rand-fst.h.

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

56  {
57  typedef typename Arc::StateId StateId;
58  typedef typename Arc::Weight Weight;
59 
60  VectorFst<Arc> *fst = new VectorFst<Arc>();
61 
62  start:
63 
64  // Create states.
65  vector<StateId> all_states;
66  for (size_t i = 0;i < (size_t)opts.n_states;i++) {
67  StateId this_state = fst->AddState();
68  if (i == 0) fst->SetStart(i);
69  all_states.push_back(this_state);
70  }
71  // Set final states.
72  for (size_t j = 0;j < (size_t)opts.n_final;j++) {
73  StateId id = all_states[kaldi::Rand() % opts.n_states];
74  Weight weight = (Weight)(opts.weight_multiplier*(kaldi::Rand() % 5));
75  fst->SetFinal(id, weight);
76  }
77  // Create arcs.
78  for (size_t i = 0;i < (size_t)opts.n_arcs;i++) {
79  Arc a;
80  StateId start_state;
81  if(!opts.acyclic) { // no restriction on arcs.
82  start_state = all_states[kaldi::Rand() % opts.n_states];
83  a.nextstate = all_states[kaldi::Rand() % opts.n_states];
84  } else {
85  start_state = all_states[kaldi::Rand() % (opts.n_states-1)];
86  a.nextstate = start_state + 1 + (kaldi::Rand() % (opts.n_states-start_state-1));
87  }
88  a.ilabel = kaldi::Rand() % opts.n_syms;
89  a.olabel = kaldi::Rand() % opts.n_syms; // same input+output vocab.
90  a.weight = (Weight) (opts.weight_multiplier*(kaldi::Rand() % 4));
91 
92  fst->AddArc(start_state, a);
93  }
94 
95  // Trim resulting FST.
96  Connect(fst);
97  if (opts.acyclic)
98  assert(fst->Properties(kAcyclic, true) & kAcyclic);
99  if (fst->Start() == kNoStateId && !opts.allow_empty) {
100  goto start;
101  }
102  return fst;
103 }
fst::StdArc::StateId StateId
Definition: graph.dox:21
int Rand(struct RandomState *state)
Definition: kaldi-math.cc:46
fst::StdArc::Weight Weight
CompactLatticeWeight fst::RandomCompactLatticeWeight ( )

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

References rnnlm::i, kaldi::Rand(), RandomLatticeWeight(), and LatticeWeightTpl< BaseFloat >::Zero().

Referenced by CompactLatticeWeightTest().

48  {
50  if (w == LatticeWeight::Zero()) {
51  return CompactLatticeWeight(w, vector<int32>());
52  } else {
53  int32 len = kaldi::Rand() % 4;
54  vector<int32> str;
55  for(int32 i = 0; i < len; i++)
56  str.push_back(kaldi::Rand() % 10 + 1);
57  return CompactLatticeWeight(w, str);
58  }
59 }
int Rand(struct RandomState *state)
Definition: kaldi-math.cc:46
LatticeWeight RandomLatticeWeight()
LatticeWeightTpl< BaseFloat > LatticeWeight
CompactLatticeWeightTpl< LatticeWeight, int32 > CompactLatticeWeight
LatticeWeight fst::RandomLatticeWeight ( )

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

References kaldi::Rand(), kaldi::RandGauss(), and LatticeWeightTpl< BaseFloat >::Zero().

Referenced by LatticeWeightTest(), and RandomCompactLatticeWeight().

36  {
37  if (kaldi::Rand() % 3 == 0) {
38  return LatticeWeight::Zero();
39  } else if (kaldi::Rand() % 3 == 0) {
40  return LatticeWeight( 1, 2); // sometimes return special values..
41  } else if (kaldi::Rand() % 3 == 0) {
42  return LatticeWeight( 2, 1); // this tests more thoroughly certain properties...
43  } else {
44  return LatticeWeight( 100 * kaldi::RandGauss(), 100 * kaldi::RandGauss());
45  }
46 }
float RandGauss(struct RandomState *state=NULL)
Definition: kaldi-math.h:155
int Rand(struct RandomState *state)
Definition: kaldi-math.cc:46
LatticeWeightTpl< BaseFloat > LatticeWeight
VectorFst<Arc>* fst::RandPairFst ( RandFstOptions  opts = RandFstOptions())

Returns a random FST.

Useful for randomized algorithm testing. Only works if weight can be constructed from a pair of floats

Definition at line 108 of file rand-fst.h.

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

108  {
109  typedef typename Arc::StateId StateId;
110  typedef typename Arc::Weight Weight;
111 
112  VectorFst<Arc> *fst = new VectorFst<Arc>();
113 
114  start:
115 
116  // Create states.
117  vector<StateId> all_states;
118  for (size_t i = 0;i < (size_t)opts.n_states;i++) {
119  StateId this_state = fst->AddState();
120  if (i == 0) fst->SetStart(i);
121  all_states.push_back(this_state);
122  }
123  // Set final states.
124  for (size_t j = 0; j < (size_t)opts.n_final;j++) {
125  StateId id = all_states[kaldi::Rand() % opts.n_states];
126  Weight weight (opts.weight_multiplier*(kaldi::Rand() % 5), opts.weight_multiplier*(kaldi::Rand() % 5));
127  fst->SetFinal(id, weight);
128  }
129  // Create arcs.
130  for (size_t i = 0;i < (size_t)opts.n_arcs;i++) {
131  Arc a;
132  StateId start_state;
133  if(!opts.acyclic) { // no restriction on arcs.
134  start_state = all_states[kaldi::Rand() % opts.n_states];
135  a.nextstate = all_states[kaldi::Rand() % opts.n_states];
136  } else {
137  start_state = all_states[kaldi::Rand() % (opts.n_states-1)];
138  a.nextstate = start_state + 1 + (kaldi::Rand() % (opts.n_states-start_state-1));
139  }
140  a.ilabel = kaldi::Rand() % opts.n_syms;
141  a.olabel = kaldi::Rand() % opts.n_syms; // same input+output vocab.
142  a.weight = Weight (opts.weight_multiplier*(kaldi::Rand() % 4), opts.weight_multiplier*(kaldi::Rand() % 4));
143 
144  fst->AddArc(start_state, a);
145  }
146 
147  // Trim resulting FST.
148  Connect(fst);
149  if (opts.acyclic)
150  assert(fst->Properties(kAcyclic, true) & kAcyclic);
151  if (fst->Start() == kNoStateId && !opts.allow_empty) {
152  goto start;
153  }
154  return fst;
155 }
fst::StdArc::StateId StateId
Definition: graph.dox:21
int Rand(struct RandomState *state)
Definition: kaldi-math.cc:46
fst::StdArc::Weight Weight
VectorFst< StdArc > * ReadFstKaldi ( std::string  rxfilename)

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

References KALDI_ERR, kaldi::PrintableRxfilename(), and Input::Stream().

29  {
30  if (rxfilename == "") rxfilename = "-"; // interpret "" as stdin,
31  // for compatibility with OpenFst conventions.
32  kaldi::Input ki(rxfilename);
33  fst::FstHeader hdr;
34  if (!hdr.Read(ki.Stream(), rxfilename))
35  KALDI_ERR << "Reading FST: error reading FST header from "
36  << kaldi::PrintableRxfilename(rxfilename);
37  FstReadOptions ropts("<unspecified>", &hdr);
38  VectorFst<StdArc> *fst = VectorFst<StdArc>::Read(ki.Stream(), ropts);
39  if (!fst)
40  KALDI_ERR << "Could not read fst from "
41  << kaldi::PrintableRxfilename(rxfilename);
42  return fst;
43 }
Definition: graph.dox:21
std::string PrintableRxfilename(std::string rxfilename)
PrintableRxfilename turns the rxfilename into a more human-readable form for error reporting...
Definition: kaldi-io.cc:58
#define KALDI_ERR
Definition: kaldi-error.h:127
void fst::ReadFstKaldi ( std::string  rxfilename,
fst::StdVectorFst ofst 
)

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

References ReadFstKaldi().

45  {
46  fst::StdVectorFst *fst = ReadFstKaldi(rxfilename);
47  *ofst = *fst;
48  delete fst;
49 }
Definition: graph.dox:21
fst::StdVectorFst StdVectorFst
void ReadFstKaldi(std::string rxfilename, fst::StdVectorFst *ofst)
Definition: kaldi-fst-io.cc:45
void fst::ReadFstKaldi ( std::string  rxfilename,
VectorFst< StdArc > *  ofst 
)
void ReadFstKaldi ( std::istream &  is,
bool  binary,
VectorFst< Arc > *  fst 
)

Definition at line 78 of file kaldi-fst-io-inl.h.

References kaldi::ConvertStringToInteger(), rnnlm::d, KALDI_ERR, kaldi::SplitStringToIntegers(), kaldi::SplitStringToVector(), and StrToWeight().

Referenced by main(), VectorFstTplHolder< Arc >::Read(), and ReadFstKaldi().

79  {
80  typedef typename Arc::Weight Weight;
81  typedef typename Arc::StateId StateId;
82  if (binary) {
83  // We don't have access to the filename here, so write [unknown].
84  VectorFst<Arc> *ans =
85  VectorFst<Arc>::Read(is, fst::FstReadOptions(std::string("[unknown]")));
86  if (ans == NULL) {
87  KALDI_ERR << "Error reading FST from stream.";
88  }
89  *fst = *ans; // shallow copy.
90  delete ans;
91  } else {
92  // Consume the \r on Windows, the \n that the text-form FST format starts
93  // with, and any extra spaces that might have got in there somehow.
94  while (std::isspace(is.peek()) && is.peek() != '\n') is.get();
95  if (is.peek() == '\n') is.get(); // consume the newline.
96  else { // saw spaces but no newline.. this is not expected.
97  KALDI_ERR << "Reading FST: unexpected sequence of spaces "
98  << " at file position " << is.tellg();
99  }
100  using std::string;
101  using std::vector;
104  fst->DeleteStates();
105  string line;
106  size_t nline = 0;
107  string separator = FLAGS_fst_field_separator + "\r\n";
108  while (std::getline(is, line)) {
109  nline++;
110  vector<string> col;
111  // on Windows we'll write in text and read in binary mode.
112  kaldi::SplitStringToVector(line, separator.c_str(), true, &col);
113  if (col.size() == 0) break; // Empty line is a signal to stop, in our
114  // archive format.
115  if (col.size() > 5) {
116  KALDI_ERR << "Bad line in FST: " << line;
117  }
118  StateId s;
119  if (!ConvertStringToInteger(col[0], &s)) {
120  KALDI_ERR << "Bad line in FST: " << line;
121  }
122  while (s >= fst->NumStates())
123  fst->AddState();
124  if (nline == 1) fst->SetStart(s);
125 
126  bool ok = true;
127  Arc arc;
128  Weight w;
129  StateId d = s;
130  switch (col.size()) {
131  case 1:
132  fst->SetFinal(s, Weight::One());
133  break;
134  case 2:
135  if (!StrToWeight(col[1], true, &w)) ok = false;
136  else fst->SetFinal(s, w);
137  break;
138  case 3: // 3 columns not ok for Lattice format; it's not an acceptor.
139  ok = false;
140  break;
141  case 4:
142  ok = ConvertStringToInteger(col[1], &arc.nextstate) &&
143  ConvertStringToInteger(col[2], &arc.ilabel) &&
144  ConvertStringToInteger(col[3], &arc.olabel);
145  if (ok) {
146  d = arc.nextstate;
147  arc.weight = Weight::One();
148  fst->AddArc(s, arc);
149  }
150  break;
151  case 5:
152  ok = ConvertStringToInteger(col[1], &arc.nextstate) &&
153  ConvertStringToInteger(col[2], &arc.ilabel) &&
154  ConvertStringToInteger(col[3], &arc.olabel) &&
155  StrToWeight(col[4], false, &arc.weight);
156  if (ok) {
157  d = arc.nextstate;
158  fst->AddArc(s, arc);
159  }
160  break;
161  default:
162  ok = false;
163  }
164  while (d >= fst->NumStates()) fst->AddState();
165  if (!ok)
166  KALDI_ERR << "Bad line in FST: " << line;
167  }
168  }
169 }
fst::StdArc::StateId StateId
bool ConvertStringToInteger(const std::string &str, Int *out)
Converts a string into an integer via strtoll and returns false if there was any kind of problem (i...
Definition: text-utils.h:114
Definition: graph.dox:21
bool SplitStringToIntegers(const std::string &full, const char *delim, bool omit_empty_strings, std::vector< I > *out)
Split a string (e.g.
Definition: text-utils.h:64
void SplitStringToVector(const std::string &full, const char *delim, bool omit_empty_strings, std::vector< std::string > *out)
Split a string using any of the single character delimiters.
Definition: text-utils.cc:61
bool StrToWeight(const std::string &s, bool allow_zero, W *w)
#define KALDI_ERR
Definition: kaldi-error.h:127
fst::StdArc::Weight Weight
void RemoveAlignmentsFromCompactLattice ( MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, Int > > > *  fst)

Removes state-level alignments (the strings that are part of the weights).

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

Referenced by main(), and MinimumBayesRisk::MinimumBayesRisk().

223  {
224  typedef CompactLatticeWeightTpl<Weight, Int> W;
225  typedef ArcTpl<W> Arc;
226  typedef MutableFst<Arc> Fst;
227  typedef typename Arc::StateId StateId;
228  StateId num_states = fst->NumStates();
229  for (StateId s = 0; s < num_states; s++) {
230  for (MutableArcIterator<Fst> aiter(fst, s);
231  !aiter.Done();
232  aiter.Next()) {
233  Arc arc = aiter.Value();
234  arc.weight = W(arc.weight.Weight(), std::vector<Int>());
235  aiter.SetValue(arc);
236  }
237  W final_weight = fst->Final(s);
238  if (final_weight != W::Zero())
239  fst->SetFinal(s, W(final_weight.Weight(), std::vector<Int>()));
240  }
241 }
fst::StdArc::StateId StateId
Definition: graph.dox:21
void fst::RemoveArcsWithSomeInputSymbols ( const std::vector< I > &  symbols_in,
VectorFst< Arc > *  fst 
)

Definition at line 33 of file fstrmsymbols.cc.

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

Referenced by main().

34  {
35  typedef typename Arc::StateId StateId;
36 
37  kaldi::ConstIntegerSet<I> symbol_set(symbols_in);
38 
39  StateId num_states = fst->NumStates();
40  StateId dead_state = fst->AddState();
41  for (StateId s = 0; s < num_states; s++) {
42  for (MutableArcIterator<VectorFst<Arc> > iter(fst, s);
43  !iter.Done(); iter.Next()) {
44  if (symbol_set.count(iter.Value().ilabel) != 0) {
45  Arc arc = iter.Value();
46  arc.nextstate = dead_state;
47  iter.SetValue(arc);
48  }
49  }
50  }
51  // Connect() will actually remove the arcs, and the dead state.
52  Connect(fst);
53  if (fst->NumStates() == 0)
54  KALDI_WARN << "After Connect(), fst was empty.";
55 }
fst::StdArc::StateId StateId
Definition: graph.dox:21
#define KALDI_WARN
Definition: kaldi-error.h:130
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).

The algorithm is not optimal but is reasonably clever. It does not just remove epsilon arcs;it also combines pairs of input-epsilon and output-epsilon arcs into one. The algorithm preserves equivalence and stochasticity in the given semiring. If you want to preserve stochasticity in a different semiring (e.g. log), then use RemoveEpsLocalSpecial, which only words for StdArc but which preserves stochasticity, where possible (*) in the LogArc sense. The reason that we can't just cast to a different semiring is that in that case we would no longer be able to guarantee equivalence in the original semiring (this arises from what happens when we combine identical arcs). (*) by "where possible".. there are situations where we wouldn't be able to preserve stochasticity in the LogArc sense while maintaining equivalence in the StdArc sense, so in these situations we maintain equivalence.

Definition at line 309 of file