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

Namespaces

 internal
 
 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  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
 TrivialFactorWeightFst takes as template parameter a FactorIterator as defined above. More...
 
struct  TrivialFactorWeightOptions
 
class  UnweightedNgramFst
 The class UnweightedNgramFst is a DeterministicOnDemandFst whose states encode an n-gram history. More...
 
class  VectorFstTplHolder
 

Typedefs

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

Enumerations

enum  { kStateHasEpsilonArcsEntering = 0x1, kStateHasNonEpsilonArcsEntering = 0x2, kStateHasEpsilonArcsLeaving = 0x4, kStateHasNonEpsilonArcsLeaving = 0x8 }
 
enum  StatePropertiesEnum {
  kStateFinal = 0x1, kStateInitial = 0x2, kStateArcsIn = 0x4, kStateMultipleArcsIn = 0x8,
  kStateArcsOut = 0x10, kStateMultipleArcsOut = 0x20, kStateOlabelsOut = 0x40, kStateIlabelsOut = 0x80
}
 

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 >
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 Fst< StdArc > &fst, float delta, StdArc::Weight *min_sum, StdArc::Weight *max_sum)
 
template<class Arc , class I >
void TestMakeLinearAcceptor ()
 
template<class Arc >
void TestDeterminizeStarInLog ()
 
template<class Arc >
void TestSafeDeterminizeWrapper ()
 
void TestPushInLog ()
 
template<class Arc >
void TestAcceptorMinimize ()
 
template<class Arc >
void TestMakeSymbolsSame ()
 
template<class Arc >
void TestMakeSymbolsSameClass ()
 
template<class Arc >
VectorFst< Arc > * MakeLoopFstCompare (const vector< const ExpandedFst< Arc > * > &fsts)
 
template<class Arc >
void TestMakeLoopFst ()
 
template<class Arc >
void TestEqualAlign ()
 
template<class Arc >
void Print (const Fst< Arc > &fst, std::string message)
 
template<class Arc >
void TestRemoveUselessArcs ()
 
template<ReweightType rtype>
void PushInLog (VectorFst< StdArc > *fst, uint32 ptype, float delta=kDelta)
 
template<class Arc >
void MinimizeEncoded (VectorFst< Arc > *fst, float delta=kDelta)
 
template<class Arc >
void WriteFstKaldi (std::ostream &os, bool binary, const VectorFst< Arc > &t)
 
template<class W >
bool StrToWeight (const std::string &s, bool allow_zero, W *w)
 
template<class Arc >
void ReadFstKaldi (std::istream &is, bool binary, VectorFst< Arc > *fst)
 
VectorFst< StdArc > * ReadFstKaldi (std::string rxfilename)
 
Fst< StdArc > * ReadFstKaldiGeneric (std::string rxfilename, bool throw_on_err)
 
VectorFst< StdArc > * CastOrConvertToVectorFst (Fst< StdArc > *fst)
 
void ReadFstKaldi (std::string rxfilename, fst::StdVectorFst *ofst)
 
void WriteFstKaldi (const VectorFst< StdArc > &fst, std::string wxfilename)
 
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<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 147 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 771 of file fstext-utils-inl.h.

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

771  {
772  typedef typename Arc::Weight Weight;
773  typedef typename Arc::StateId StateId;
774  for (StateIterator<MutableFst<Arc> > siter(*fst);
775  !siter.Done();
776  siter.Next()) {
777  StateId s = siter.Value();
778  for (MutableArcIterator<MutableFst<Arc> > aiter(fst, s);
779  !aiter.Done();
780  aiter.Next()) {
781  Arc arc = aiter.Value();
782  arc.weight = Weight(arc.weight.Value() * scale);
783  aiter.SetValue(arc);
784  }
785  if (fst->Final(s) != Weight::Zero())
786  fst->SetFinal(s, Weight(fst->Final(s).Value() * scale));
787  }
788 }
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 543 of file lattice-weight.h.

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

545  {
546  return (ApproxEqual(w1.Weight(), w2.Weight(), delta) && w1.String() == w2.String());
547 }
bool ApproxEqual(const CompactLatticeWeightTpl< WeightType, IntType > &w1, const CompactLatticeWeightTpl< WeightType, IntType > &w2, float delta=kDelta)
VectorFst< StdArc > * CastOrConvertToVectorFst ( Fst< StdArc > *  fst)

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

References KALDI_ASSERT, and KALDI_WARN.

Referenced by main().

94  {
95  // This version currently supports ConstFst<StdArc> or VectorFst<StdArc>
96  std::string real_type = fst->Type();
97  KALDI_ASSERT(real_type == "vector" || real_type == "const");
98  if (real_type == "vector") {
99  return dynamic_cast<VectorFst<StdArc> *>(fst);
100  } else {
101  // As the 'fst' can't cast to VectorFst, I'm creating a new
102  // VectorFst<StdArc> initialized by 'fst', and deletes 'fst'.
103  VectorFst<StdArc> *new_fst = new VectorFst<StdArc>(*fst);
104  KALDI_WARN << "The 'fst' is deleted.";
105  delete fst;
106  return new_fst;
107  }
108 }
Definition: graph.dox:21
#define KALDI_WARN
Definition: kaldi-error.h:130
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
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:47
void ClearSymbols ( bool  clear_input,
bool  clear_output,
MutableFst< Arc > *  fst 
)

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

It does not alter the symbol tables.

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

Referenced by MakeLoopFstCompare().

744  {
745  for (StateIterator<MutableFst<Arc> > siter(*fst);
746  !siter.Done();
747  siter.Next()) {
748  typename Arc::StateId s = siter.Value();
749  for (MutableArcIterator<MutableFst<Arc> > aiter(fst, s);
750  !aiter.Done();
751  aiter.Next()) {
752  Arc arc = aiter.Value();
753  bool change = false;
754  if (clear_input && arc.ilabel != 0) {
755  arc.ilabel = 0;
756  change = true;
757  }
758  if (clear_output && arc.olabel != 0) {
759  arc.olabel = 0;
760  change = true;
761  }
762  if (change) {
763  aiter.SetValue(arc);
764  }
765  }
766  }
767 }
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 564 of file lattice-weight.h.

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

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

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

599  {
600  float f1 = w1.Value(), f2 = w2.Value();
601  if (f1 == f2) return 0;
602  else if (f1 > f2) return -1;
603  else return 1;
604 }
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
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  fst::CacheOptions cache_opts(true, num_states_cache);
271  fst::MapFstOptions mapfst_opts(cache_opts);
272  StdToLatticeMapper<Real> mapper;
273  MapFst<StdArc, ArcTpl<LatticeWeightTpl<Real> >,
274  StdToLatticeMapper<Real> > map_fst(ifst, mapper, mapfst_opts);
275  *ofst = map_fst;
276 }
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 764 of file lattice-weight.h.

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

Referenced by ConvertLattice().

766  {
767  w_out->SetValue1(w_in.Value1());
768  w_out->SetValue2(w_in.Value2());
769 }
void fst::ConvertLatticeWeight ( const CompactLatticeWeightTpl< LatticeWeightTpl< Float1 >, Int > &  w_in,
CompactLatticeWeightTpl< LatticeWeightTpl< Float2 >, Int > *  w_out 
)
inline

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

774  {
775  LatticeWeightTpl<Float2> weight2(w_in.Weight().Value1(),
776  w_in.Weight().Value2());
777  w_out->SetWeight(weight2);
778  w_out->SetString(w_in.String());
779 }
void fst::ConvertLatticeWeight ( const LatticeWeightTpl< Float1 > &  w_in,
TropicalWeightTpl< Float2 > *  w_out 
)
inline

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

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

785  {
786  TropicalWeightTpl<Float2> w1(w_in.Value1());
787  TropicalWeightTpl<Float2> w2(w_in.Value2());
788  *w_out = Times(w1, w2);
789 }
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 221 of file fstext-utils-inl.h.

References KALDI_ASSERT.

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

222  {
223  typedef typename Arc::Weight Weight;
224  typedef typename Arc::StateId StateId;
225  fsts_out->clear();
226  StateId start_state = fst.Start();
227  if (start_state == kNoStateId) return; // No output.
228  size_t n_arcs = fst.NumArcs(start_state);
229  bool start_is_final = (fst.Final(start_state) != Weight::Zero());
230  fsts_out->reserve(n_arcs + (start_is_final ? 1 : 0));
231 
232  if (start_is_final) {
233  fsts_out->resize(fsts_out->size() + 1);
234  StateId start_state_out = fsts_out->back().AddState();
235  fsts_out->back().SetFinal(start_state_out, fst.Final(start_state));
236  }
237 
238  for (ArcIterator<Fst<Arc> > start_aiter(fst, start_state);
239  !start_aiter.Done();
240  start_aiter.Next()) {
241  fsts_out->resize(fsts_out->size() + 1);
242  VectorFst<Arc> &ofst = fsts_out->back();
243  const Arc &first_arc = start_aiter.Value();
244  StateId cur_state = start_state,
245  cur_ostate = ofst.AddState();
246  ofst.SetStart(cur_ostate);
247  StateId next_ostate = ofst.AddState();
248  ofst.AddArc(cur_ostate, Arc(first_arc.ilabel, first_arc.olabel,
249  first_arc.weight, next_ostate));
250  cur_state = first_arc.nextstate;
251  cur_ostate = next_ostate;
252  while (1) {
253  size_t this_n_arcs = fst.NumArcs(cur_state);
254  KALDI_ASSERT(this_n_arcs <= 1); // or it violates our assumptions
255  // about the input.
256  if (this_n_arcs == 1) {
257  KALDI_ASSERT(fst.Final(cur_state) == Weight::Zero());
258  // or problem with ShortestPath.
259  ArcIterator<Fst<Arc> > aiter(fst, cur_state);
260  const Arc &arc = aiter.Value();
261  next_ostate = ofst.AddState();
262  ofst.AddArc(cur_ostate, Arc(arc.ilabel, arc.olabel,
263  arc.weight, next_ostate));
264  cur_state = arc.nextstate;
265  cur_ostate = next_ostate;
266  } else {
267  KALDI_ASSERT(fst.Final(cur_state) != Weight::Zero());
268  // or problem with ShortestPath.
269  ofst.SetFinal(cur_ostate, fst.Final(cur_state));
270  break;
271  }
272  }
273  }
274 }
fst::StdArc::StateId StateId
Definition: graph.dox:21
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 797 of file lattice-weight.h.

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

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

802  {
803  return w.Value();
804 }
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:129
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:129
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 388 of file fstext-utils-inl.h.

Referenced by main().

388  {
389  // DeterminizeInLog determinizes 'fst' in the log semiring.
390 
391  ArcSort(fst, ILabelCompare<StdArc>()); // helps DeterminizeStar to be faster.
392  VectorFst<LogArc> *fst_log = new VectorFst<LogArc>; // Want to determinize in log semiring.
393  Cast(*fst, fst_log);
394  VectorFst<StdArc> tmp;
395  *fst = tmp; // make fst empty to free up memory. [actually may make no difference..]
396  VectorFst<LogArc> *fst_det_log = new VectorFst<LogArc>;
397  Determinize(*fst_log, fst_det_log);
398  Cast(*fst_det_log, fst);
399  delete fst_log;
400  delete fst_det_log;
401 }
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 371 of file fstext-utils-inl.h.

References DeterminizeStar().

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

371  {
372  // DeterminizeStarInLog determinizes 'fst' in the log semiring, using
373  // the DeterminizeStar algorithm (which also removes epsilons).
374 
375  ArcSort(fst, ILabelCompare<StdArc>()); // helps DeterminizeStar to be faster.
376  VectorFst<LogArc> *fst_log = new VectorFst<LogArc>; // Want to determinize in log semiring.
377  Cast(*fst, fst_log);
378  VectorFst<StdArc> tmp;
379  *fst = tmp; // make fst empty to free up memory. [actually may make no difference..]
380  VectorFst<LogArc> *fst_det_log = new VectorFst<LogArc>;
381  DeterminizeStar(*fst_log, fst_det_log, delta, debug_ptr, max_states);
382  Cast(*fst_det_log, fst);
383  delete fst_log;
384  delete fst_det_log;
385 }
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...
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 343 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().

345  {
346  typedef FloatType T;
347  T a = w1.Value1() - w2.Value1(), b = w1.Value2() - w2.Value2();
348  if (a != a || b != b || a == -numeric_limits<T>::infinity()
349  || b == -numeric_limits<T>::infinity()) {
350  KALDI_WARN << "LatticeWeightTpl::Divide, NaN or invalid number produced. "
351  << "[dividing by zero?] Returning zero";
352  return LatticeWeightTpl<T>::Zero();
353  }
354  if (a == numeric_limits<T>::infinity() ||
355  b == numeric_limits<T>::infinity())
356  return LatticeWeightTpl<T>::Zero(); // not a valid number if only one is infinite.
357  return LatticeWeightTpl<T>(a, b);
358 }
#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 634 of file lattice-weight.h.

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

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

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

Referenced by main(), and TestEqualAlign().

807  {
808  srand(rand_seed);
809  KALDI_ASSERT(ofst->NumStates() == 0); // make sure ofst empty.
810  // make sure all states can reach final-state (or this algorithm may enter
811  // infinite loop.
812  KALDI_ASSERT(ifst.Properties(kCoAccessible, true) == kCoAccessible);
813 
814  typedef typename Arc::StateId StateId;
815  typedef typename Arc::Weight Weight;
816 
817  if (ifst.Start() == kNoStateId) {
818  KALDI_WARN << "Empty input fst.";
819  return false;
820  }
821  // First select path through ifst.
822  vector<StateId> path;
823  vector<size_t> arc_offsets; // arc taken out of each state.
824  vector<int> nof_ilabels;
825 
826  StateId num_ilabels = 0;
827  int retry_no = 0;
828 
829  // Under normal circumstances, this will be one-pass-only process
830  // Multiple tries might be needed in special cases, typically when
831  // the number of frames is close to number of transitions from
832  // the start node to the final node. It usually happens for really
833  // short utterances
834  do {
835  num_ilabels = 0;
836  arc_offsets.clear();
837  path.clear();
838  path.push_back(ifst.Start());
839 
840  while (1) {
841  // Select either an arc or final-prob.
842  StateId s = path.back();
843  size_t num_arcs = ifst.NumArcs(s);
844  size_t num_arcs_tot = num_arcs;
845  if (ifst.Final(s) != Weight::Zero()) num_arcs_tot++;
846  // kaldi::RandInt is a bit like Rand(), but gets around situations
847  // where RAND_MAX is very small.
848  // Change this to Rand() % num_arcs_tot if compile issues arise
849  size_t arc_offset = static_cast<size_t>(kaldi::RandInt(0, num_arcs_tot-1));
850 
851  if (arc_offset < num_arcs) { // an actual arc.
852  ArcIterator<Fst<Arc> > aiter(ifst, s);
853  aiter.Seek(arc_offset);
854  const Arc &arc = aiter.Value();
855  if (arc.nextstate == s) {
856  continue; // don't take this self-loop arc
857  } else {
858  arc_offsets.push_back(arc_offset);
859  path.push_back(arc.nextstate);
860  if (arc.ilabel != 0) num_ilabels++;
861  }
862  } else {
863  break; // Chose final-prob.
864  }
865  }
866 
867  nof_ilabels.push_back(num_ilabels);
868  } while (( ++retry_no < num_retries) && (num_ilabels > length));
869 
870  if (num_ilabels > length) {
871  std::stringstream ilabel_vec;
872  std::copy(nof_ilabels.begin(), nof_ilabels.end(),
873  std::ostream_iterator<int>(ilabel_vec, ","));
874  std::string s = ilabel_vec.str();
875  s.erase(s.end() - 1);
876  KALDI_WARN << "EqualAlign: the randomly constructed paths lengths: " << s;
877  KALDI_WARN << "EqualAlign: utterance has too few frames " << length
878  << " to align.";
879  return false; // can't make it shorter by adding self-loops!.
880  }
881 
882  StateId num_self_loops = 0;
883  vector<ssize_t> self_loop_offsets(path.size());
884  for (size_t i = 0; i < path.size(); i++)
885  if ( (self_loop_offsets[i] = FindSelfLoopWithILabel(ifst, path[i]))
886  != static_cast<ssize_t>(-1) )
887  num_self_loops++;
888 
889  if (num_self_loops == 0
890  && num_ilabels < length) {
891  KALDI_WARN << "No self-loops on chosen path; cannot match length.";
892  return false; // no self-loops to make it longer.
893  }
894 
895  StateId num_extra = length - num_ilabels; // Number of self-loops we need.
896 
897  StateId min_num_loops = 0;
898  if (num_extra != 0) min_num_loops = num_extra / num_self_loops; // prevent div by zero.
899  StateId num_with_one_more_loop = num_extra - (min_num_loops*num_self_loops);
900  KALDI_ASSERT(num_with_one_more_loop < num_self_loops || num_self_loops == 0);
901 
902  ofst->AddState();
903  ofst->SetStart(0);
904  StateId cur_state = 0;
905  StateId counter = 0; // tell us when we should stop adding one more loop.
906  for (size_t i = 0; i < path.size(); i++) {
907  // First, add any self-loops that are necessary.
908  StateId num_loops = 0;
909  if (self_loop_offsets[i] != static_cast<ssize_t>(-1)) {
910  num_loops = min_num_loops + (counter < num_with_one_more_loop ? 1 : 0);
911  counter++;
912  }
913  for (StateId j = 0; j < num_loops; j++) {
914  ArcIterator<Fst<Arc> > aiter(ifst, path[i]);
915  aiter.Seek(self_loop_offsets[i]);
916  Arc arc = aiter.Value();
917  KALDI_ASSERT(arc.nextstate == path[i]
918  && arc.ilabel != 0); // make sure self-loop with ilabel.
919  StateId next_state = ofst->AddState();
920  ofst->AddArc(cur_state, Arc(arc.ilabel, arc.olabel, arc.weight, next_state));
921  cur_state = next_state;
922  }
923  if (i+1 < path.size()) { // add forward transition.
924  ArcIterator<Fst<Arc> > aiter(ifst, path[i]);
925  aiter.Seek(arc_offsets[i]);
926  Arc arc = aiter.Value();
927  KALDI_ASSERT(arc.nextstate == path[i+1]);
928  StateId next_state = ofst->AddState();
929  ofst->AddArc(cur_state, Arc(arc.ilabel, arc.olabel, arc.weight, next_state));
930  cur_state = next_state;
931  } else { // add final-prob.
932  Weight weight = ifst.Final(path[i]);
933  KALDI_ASSERT(weight != Weight::Zero());
934  ofst->SetFinal(cur_state, weight);
935  }
936  }
937  return true;
938 }
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:94
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:129
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:218
#define KALDI_ASSERT_IS_INTEGER_TYPE(I)
Definition: kaldi-utils.h:129
Definition: graph.dox:21
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 }
Definition: graph.dox:21
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 794 of file fstext-utils-inl.h.

Referenced by EqualAlign().

794  {
795  for (ArcIterator<Fst<Arc> > aiter(fst, s); !aiter.Done(); aiter.Next())
796  if (aiter.Value().nextstate == s
797  && aiter.Value().ilabel != 0) return static_cast<ssize_t>(aiter.Position());
798  return static_cast<ssize_t>(-1);
799 }
Definition: graph.dox:21
bool FollowingInputSymbolsAreSame ( bool  end_is_epsilon,
const Fst< Arc > &  fst 
)

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

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

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

References FollowingInputSymbolsAreSameClass().

Referenced by TestMakeSymbolsSame().

497  {
498  IdentityFunction<typename Arc::Label> f;
499  return FollowingInputSymbolsAreSameClass(end_is_epsilon, fst, f);
500 }
Definition: graph.dox:21
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 504 of file fstext-utils-inl.h.

Referenced by FollowingInputSymbolsAreSame(), and TestMakeSymbolsSameClass().

504  {
505  typedef typename Arc::StateId StateId;
506  typedef typename Arc::Weight Weight;
507  typedef typename F::Result ClassType;
508  const ClassType noClass = f(kNoLabel), epsClass = f(0);
509  for (StateIterator<Fst<Arc> > siter(fst); !siter.Done(); siter.Next()) {
510  StateId s = siter.Value();
511  ClassType c = noClass;
512  for (ArcIterator<Fst<Arc> > aiter(fst, s); !aiter.Done(); aiter.Next()) {
513  const Arc &arc = aiter.Value();
514  if (c == noClass)
515  c = f(arc.ilabel);
516  else
517  if (c != f(arc.ilabel))
518  return false;
519  }
520  if (end_is_epsilon && c != noClass &&
521  c != epsClass && fst.Final(s) != Weight::Zero())
522  return false;
523  }
524  return true;
525 }
fst::StdArc::StateId StateId
Definition: graph.dox:21
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:44
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:44
#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:86
#define KALDI_ASSERT_IS_INTEGER_TYPE(I)
Definition: kaldi-utils.h:129
Definition: graph.dox:21
#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
Definition: graph.dox:21
LatticeWeightTpl< FloatType > Times(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2)
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:86
#define KALDI_ASSERT_IS_INTEGER_TYPE(I)
Definition: kaldi-utils.h:129
Definition: graph.dox:21
#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
Definition: graph.dox:21
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 329 of file fstext-utils-inl.h.

References KALDI_ASSERT.

Referenced by main().

331  {
332  KALDI_ASSERT(syms_out != NULL);
333  syms_out->clear();
334  for (SymbolTableIterator iter(symtab);
335  !iter.Done();
336  iter.Next()) {
337  if (include_eps || iter.Value() != 0) {
338  syms_out->push_back(iter.Value());
339  KALDI_ASSERT(syms_out->back() == iter.Value()); // an integer-range thing.
340  }
341  }
342 }
#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
Definition: graph.dox:21
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
Definition: graph.dox:21
fst::StdArc::Label Label
bool IsStochasticFst ( const Fst< LogArc > &  fst,
float  delta,
LogArc::Weight *  min_sum,
LogArc::Weight *  max_sum 
)
inline

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

References ApproxEqual(), and Plus().

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

1174  {
1175  typedef LogArc Arc;
1176  typedef Arc::StateId StateId;
1177  typedef Arc::Weight Weight;
1178  bool first_time = true;
1179  bool ans = true;
1180  for (StateIterator<Fst<Arc> > siter(fst); !siter.Done(); siter.Next()) {
1181  StateId s = siter.Value();
1182  Weight sum = fst.Final(s);
1183  for (ArcIterator<Fst<Arc> > aiter(fst, s); !aiter.Done(); aiter.Next()) {
1184  const Arc &arc = aiter.Value();
1185  sum = Plus(sum, arc.weight);
1186  }
1187  if (!ApproxEqual(Weight::One(), sum, delta)) ans = false;
1188  if (first_time) {
1189  first_time = false;
1190  if (max_sum) *max_sum = sum;
1191  if (min_sum) *min_sum = sum;
1192  } else {
1193  // note that max and min are reversed from their normal
1194  // meanings here (max and min w.r.t. the underlying probabilities).
1195  if (max_sum && sum.Value() < max_sum->Value()) *max_sum = sum;
1196  if (min_sum && sum.Value() > min_sum->Value()) *min_sum = sum;
1197  }
1198  }
1199  if (first_time) { // just avoid NaNs if FST was empty.
1200  if (max_sum) *max_sum = Weight::One();
1201  if (min_sum) *min_sum = Weight::One();
1202  }
1203  return ans;
1204 }
fst::StdArc::StateId StateId
Definition: graph.dox:21
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 1135 of file fstext-utils-inl.h.

References ApproxEqual(), and Plus().

1138  {
1139  typedef typename Arc::StateId StateId;
1140  typedef typename Arc::Weight Weight;
1141  NaturalLess<Weight> nl;
1142  bool first_time = true;
1143  bool ans = true;
1144  for (StateIterator<Fst<Arc> > siter(fst); !siter.Done(); siter.Next()) {
1145  StateId s = siter.Value();
1146  Weight sum = fst.Final(s);
1147  for (ArcIterator<Fst<Arc> > aiter(fst, s); !aiter.Done(); aiter.Next()) {
1148  const Arc &arc = aiter.Value();
1149  sum = Plus(sum, arc.weight);
1150  }
1151  if (!ApproxEqual(Weight::One(), sum, delta)) ans = false;
1152  if (first_time) {
1153  first_time = false;
1154  if (max_sum) *max_sum = sum;
1155  if (min_sum) *min_sum = sum;
1156  } else {
1157  if (max_sum && nl(*max_sum, sum)) *max_sum = sum;
1158  if (min_sum && nl(sum, *min_sum)) *min_sum = sum;
1159  }
1160  }
1161  if (first_time) { // just avoid NaNs if FST was empty.
1162  if (max_sum) *max_sum = Weight::One();
1163  if (min_sum) *min_sum = Weight::One();
1164  }
1165  return ans;
1166 }
fst::StdArc::StateId StateId
Definition: graph.dox:21
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 Fst< StdArc > &  fst,
float  delta,
StdArc::Weight *  min_sum,
StdArc::Weight *  max_sum 
)
inline

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

References IsStochasticFst(), and KALDI_ERR.

Referenced by main(), and TestPushSpecial().

1214  {
1215  bool ans = false;
1216  LogArc::Weight log_min, log_max;
1217  if (fst.Type() == "const") {
1218  ConstFst<LogArc> logfst;
1219  Cast(dynamic_cast<const ConstFst<StdArc>&>(fst), &logfst);
1220  ans = IsStochasticFst(logfst, delta, &log_min, &log_max);
1221  } else if (fst.Type() == "vector") {
1222  VectorFst<LogArc> logfst;
1223  Cast(dynamic_cast<const VectorFst<StdArc>&>(fst), &logfst);
1224  ans = IsStochasticFst(logfst, delta, &log_min, &log_max);
1225  } else {
1226  KALDI_ERR << "This version currently supports ConstFst<StdArc> "
1227  << "or VectorFst<StdArc>";
1228  }
1229  if (min_sum) *min_sum = StdArc::Weight(log_min.Value());
1230  if (max_sum) *max_sum = StdArc::Weight(log_max.Value());
1231  return ans;
1232 }
Definition: graph.dox:21
#define KALDI_ERR
Definition: kaldi-error.h:127
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 610 of file fstext-utils-inl.h.

References MakeFollowingInputSymbolsSameClass().

Referenced by TestMakeSymbolsSame().

610  {
611  IdentityFunction<typename Arc::Label> f;
612  MakeFollowingInputSymbolsSameClass(end_is_epsilon, fst, f);
613 }
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 616 of file fstext-utils-inl.h.

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

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

616  {
617  typedef typename Arc::StateId StateId;
618  typedef typename Arc::Weight Weight;
619  typedef typename F::Result ClassType;
620  vector<StateId> bad_states;
621  ClassType noClass = f(kNoLabel);
622  ClassType epsClass = f(0);
623  for (StateIterator<Fst<Arc> > siter(*fst); !siter.Done(); siter.Next()) {
624  StateId s = siter.Value();
625  ClassType c = noClass;
626  bool bad = false;
627  for (ArcIterator<Fst<Arc> > aiter(*fst, s); !aiter.Done(); aiter.Next()) {
628  const Arc &arc = aiter.Value();
629  if (c == noClass)
630  c = f(arc.ilabel);
631  else
632  if (c != f(arc.ilabel)) {
633  bad = true;
634  break;
635  }
636  }
637  if (end_is_epsilon && c != noClass &&
638  c != epsClass && fst->Final(s) != Weight::Zero())
639  bad = true;
640  if (bad)
641  bad_states.push_back(s);
642  }
643  vector<Arc> my_arcs;
644  for (size_t i = 0; i < bad_states.size(); i++) {
645  StateId s = bad_states[i];
646  my_arcs.clear();
647  for (ArcIterator<MutableFst<Arc> > aiter(*fst, s); !aiter.Done(); aiter.Next())
648  my_arcs.push_back(aiter.Value());
649 
650  for (size_t j = 0; j < my_arcs.size(); j++) {
651  Arc &arc = my_arcs[j];
652  if (arc.ilabel != 0) {
653  StateId newstate = fst->AddState();
654  // Create a new state for each non-eps arc in original FST, out of each bad state.
655  // Not as optimal as it could be, but does avoid some complicated weight-pushing
656  // issues in which, to maintain stochasticity, we would have to know which semiring
657  // we want to maintain stochasticity in.
658  fst->AddArc(newstate, Arc(arc.ilabel, 0, Weight::One(), arc.nextstate));
659  MutableArcIterator<MutableFst<Arc> > maiter(fst, s);
660  maiter.Seek(j);
661  maiter.SetValue(Arc(0, arc.olabel, arc.weight, newstate));
662  }
663  }
664  }
665 }
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 311 of file fstext-utils-inl.h.

References rnnlm::i.

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

311  {
312  typedef typename Arc::StateId StateId;
313  typedef typename Arc::Weight Weight;
314 
315  ofst->DeleteStates();
316  StateId cur_state = ofst->AddState();
317  ofst->SetStart(cur_state);
318  for (size_t i = 0; i < labels.size(); i++) {
319  StateId next_state = ofst->AddState();
320  Arc arc(labels[i], labels[i], Weight::One(), next_state);
321  ofst->AddArc(cur_state, arc);
322  cur_state = next_state;
323  }
324  ofst->SetFinal(cur_state, Weight::One());
325 }
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 290 of file fstext-utils-inl.h.

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

291  {
292  typedef typename Arc::StateId StateId;
293  typedef typename Arc::Weight Weight;
294 
295  ofst->DeleteStates();
296  StateId cur_state = ofst->AddState();
297  ofst->SetStart(cur_state);
298  for (size_t i = 0; i < labels.size(); i++) {
299  KALDI_ASSERT(labels[i].size() != 0);
300  StateId next_state = ofst->AddState();
301  for (size_t j = 0; j < labels[i].size(); j++) {
302  Arc arc(labels[i][j], labels[i][j], Weight::One(), next_state);
303  ofst->AddArc(cur_state, arc);
304  }
305  cur_state = next_state;
306  }
307  ofst->SetFinal(cur_state, Weight::One());
308 }
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 669 of file fstext-utils-inl.h.

References rnnlm::i, and KALDI_ASSERT.

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

669  {
670  typedef typename Arc::Weight Weight;
671  typedef typename Arc::StateId StateId;
672  typedef typename Arc::Label Label;
673 
674  VectorFst<Arc> *ans = new VectorFst<Arc>;
675  StateId loop_state = ans->AddState(); // = 0.
676  ans->SetStart(loop_state);
677  ans->SetFinal(loop_state, Weight::One());
678 
679  // "cache" is used as an optimization when some of the pointers in "fsts"
680  // may have the same value.
681  unordered_map<const ExpandedFst<Arc> *, Arc> cache;
682 
683  for (Label i = 0; i < static_cast<Label>(fsts.size()); i++) {
684  const ExpandedFst<Arc> *fst = fsts[i];
685  if (fst == NULL) continue;
686  { // optimization with cache: helpful if some members of "fsts" may
687  // contain the same pointer value (e.g. in GetHTransducer).
688  typename unordered_map<const ExpandedFst<Arc> *, Arc>::iterator
689  iter = cache.find(fst);
690  if (iter != cache.end()) {
691  Arc arc = iter->second;
692  arc.olabel = i;
693  ans->AddArc(0, arc);
694  continue;
695  }
696  }
697 
698  KALDI_ASSERT(fst->Properties(kAcceptor, true) == kAcceptor); // expect acceptor.
699 
700  StateId fst_num_states = fst->NumStates();
701  StateId fst_start_state = fst->Start();
702 
703  if (fst_start_state == kNoStateId)
704  continue; // empty fst.
705 
706  bool share_start_state =
707  fst->Properties(kInitialAcyclic, true) == kInitialAcyclic
708  && fst->NumArcs(fst_start_state) == 1
709  && fst->Final(fst_start_state) == Weight::Zero();
710 
711  vector<StateId> state_map(fst_num_states); // fst state -> ans state
712  for (StateId s = 0; s < fst_num_states; s++) {
713  if (s == fst_start_state && share_start_state) state_map[s] = loop_state;
714  else state_map[s] = ans->AddState();
715  }
716  if (!share_start_state) {
717  Arc arc(0, i, Weight::One(), state_map[fst_start_state]);
718  cache[fst] = arc;
719  ans->AddArc(0, arc);
720  }
721  for (StateId s = 0; s < fst_num_states; s++) {
722  // Add arcs out of state s.
723  for (ArcIterator<ExpandedFst<Arc> > aiter(*fst, s); !aiter.Done(); aiter.Next()) {
724  const Arc &arc = aiter.Value();
725  Label olabel = (s == fst_start_state && share_start_state ? i : 0);
726  Arc newarc(arc.ilabel, olabel, arc.weight, state_map[arc.nextstate]);
727  ans->AddArc(state_map[s], newarc);
728  if (s == fst_start_state && share_start_state)
729  cache[fst] = newarc;
730  }
731  if (fst->Final(s) != Weight::Zero()) {
732  KALDI_ASSERT(!(s == fst_start_state && share_start_state));
733  ans->AddArc(state_map[s], Arc(0, 0, fst->Final(s), loop_state));
734  }
735  }
736  }
737  return ans;
738 }
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 278 of file fstext-utils-test.cc.

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

Referenced by TestMakeLoopFst().

278  {
279  VectorFst<Arc> *ans = new VectorFst<Arc>;
280  typedef typename Arc::Label Label;
281  typedef typename Arc::StateId StateId;
282  typedef typename Arc::Weight Weight;
283 
284  for (Label i = 0; i < fsts.size(); i++) {
285  if (fsts[i] != NULL) {
286  VectorFst<Arc> i_fst; // accepts symbol i on output.
287  i_fst.AddState(); i_fst.AddState();
288  i_fst.SetStart(0); i_fst.SetFinal(1, Weight::One());
289  i_fst.AddArc(0, Arc(0, i, Weight::One(), 1));
290  VectorFst<Arc> other_fst(*(fsts[i])); // copy it.
291  ClearSymbols(false, true, &other_fst); // Clear output symbols so symbols
292  // are on input side.
293  Concat(&i_fst, other_fst); // now i_fst is "i_fst [concat] other_fst".
294  Union(ans, i_fst);
295  }
296  }
297  Closure(ans, CLOSURE_STAR);
298  return ans;
299 }
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 528 of file fstext-utils-inl.h.

References MakePrecedingInputSymbolsSameClass().

Referenced by TestMakeSymbolsSame().

528  {
529  IdentityFunction<typename Arc::Label> f;
530  MakePrecedingInputSymbolsSameClass(start_is_epsilon, fst, f);
531 }
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 534 of file fstext-utils-inl.h.

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

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

534  {
535  typedef typename F::Result ClassType;
536  typedef typename Arc::StateId StateId;
537  typedef typename Arc::Weight Weight;
538  vector<ClassType> classes;
539  ClassType noClass = f(kNoLabel);
540  ClassType epsClass = f(0);
541  if (start_is_epsilon) { // treat having-start-state as epsilon in-transition.
542  StateId start_state = fst->Start();
543  if (start_state < 0 || start_state == kNoStateId) // empty FST.
544  return;
545  classes.resize(start_state+1, noClass);
546  classes[start_state] = epsClass;
547  }
548 
549  // Find bad states (states with multiple input-symbols into them).
550  std::set<StateId> bad_states; // states that we need to change.
551  for (StateIterator<Fst<Arc> > siter(*fst); !siter.Done(); siter.Next()) {
552  StateId s = siter.Value();
553  for (ArcIterator<Fst<Arc> > aiter(*fst, s); !aiter.Done(); aiter.Next()) {
554  const Arc &arc = aiter.Value();
555  if (classes.size() <= static_cast<size_t>(arc.nextstate))
556  classes.resize(arc.nextstate+1, noClass);
557  if (classes[arc.nextstate] == noClass)
558  classes[arc.nextstate] = f(arc.ilabel);
559  else
560  if (classes[arc.nextstate] != f(arc.ilabel))
561  bad_states.insert(arc.nextstate);
562  }
563  }
564  if (bad_states.empty()) return; // Nothing to do.
565  kaldi::ConstIntegerSet<StateId> bad_states_ciset(bad_states); // faster lookup.
566 
567  // Work out list of arcs we have to change as (state, arc-offset).
568  // Can't do the actual changes in this pass, since we have to add new
569  // states which invalidates the iterators.
570  vector<pair<StateId, size_t> > arcs_to_change;
571  for (StateIterator<Fst<Arc> > siter(*fst); !siter.Done(); siter.Next()) {
572  StateId s = siter.Value();
573  for (ArcIterator<Fst<Arc> > aiter(*fst, s); !aiter.Done(); aiter.Next()) {
574  const Arc &arc = aiter.Value();
575  if (arc.ilabel != 0 &&
576  bad_states_ciset.count(arc.nextstate) != 0)
577  arcs_to_change.push_back(std::make_pair(s, aiter.Position()));
578  }
579  }
580  KALDI_ASSERT(!arcs_to_change.empty()); // since !bad_states.empty().
581 
582  std::map<pair<StateId, ClassType>, StateId> state_map;
583  // state_map is a map from (bad-state, input-symbol-class) to dummy-state.
584 
585  for (size_t i = 0; i < arcs_to_change.size(); i++) {
586  StateId s = arcs_to_change[i].first;
587  ArcIterator<MutableFst<Arc> > aiter(*fst, s);
588  aiter.Seek(arcs_to_change[i].second);
589  Arc arc = aiter.Value();
590 
591  // Transition is non-eps transition to "bad" state. Introduce new state (or find
592  // existing one).
593  pair<StateId, ClassType> p(arc.nextstate, f(arc.ilabel));
594  if (state_map.count(p) == 0) {
595  StateId newstate = state_map[p] = fst->AddState();
596  fst->AddArc(newstate, Arc(0, 0, Weight::One(), arc.nextstate));
597  }
598  StateId dst_state = state_map[p];
599  arc.nextstate = dst_state;
600 
601  // Initialize the MutableArcIterator only now, as the call to NewState()
602  // may have invalidated the first arc iterator.
603  MutableArcIterator<MutableFst<Arc> > maiter(fst, s);
604  maiter.Seek(arcs_to_change[i].second);
605  maiter.SetValue(arc);
606  }
607 }
fst::StdArc::StateId StateId
Definition: graph.dox:21
fst::StdArc::Weight Weight
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
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:129
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. The output will be topologically sorted.

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

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

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

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  internal::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 279 of file fstext-utils-inl.h.

References ConvertNbestToVector(), and KALDI_ASSERT.

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

281  {
282  KALDI_ASSERT(n > 0);
283  KALDI_ASSERT(fsts_out != NULL);
284  VectorFst<Arc> nbest_fst;
285  ShortestPath(fst, &nbest_fst, n);
286  ConvertNbestToVector(nbest_fst, fsts_out);
287 }
Definition: graph.dox:21
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 537 of file lattice-weight.h.

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

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

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

References LatticeWeightTpl< FloatType >::WriteFloatType().

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

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

References rnnlm::i.

674  {
675  strm << w.Weight();
676  CHECK(FLAGS_fst_weight_separator.size() == 1);
677  strm << FLAGS_fst_weight_separator[0]; // comma by default.
678  for(size_t i = 0; i < w.String().size(); i++) {
679  strm << w.String()[i];
680  if (i+1 < w.String().size())
681  strm << kStringSeparator; // '_'; defined in string-weight.h in OpenFst code.
682  }
683  return strm;
684 }
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 531 of file lattice-weight.h.

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

532  {
533  return (w1.Weight() == w2.Weight() && w1.String() == w2.String());
534 }
istream & operator>> ( istream &  strm,
LatticeWeightTpl< FloatType > &  w 
)
inline

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

References LatticeWeightTpl< FloatType >::ReadNoParen().

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

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

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

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

References KALDI_ASSERT.

Referenced by main().

1024  {
1025  KALDI_ASSERT(phi_label != kNoLabel); // just use regular compose in this case.
1026  typedef Fst<Arc> F;
1027  typedef PhiMatcher<SortedMatcher<F> > PM;
1028  CacheOptions base_opts;
1029  base_opts.gc_limit = 0; // Cache only the last state for fastest copy.
1030  // ComposeFstImplOptions templated on matcher for fst1, matcher for fst2.
1031  // The matcher for fst1 doesn't matter; we'll use fst2's matcher.
1032  ComposeFstImplOptions<SortedMatcher<F>, PM> impl_opts(base_opts);
1033 
1034  // the false below is something called phi_loop which is something I don't
1035  // fully understand, but I don't think we want it.
1036 
1037  // These pointers are taken ownership of, by ComposeFst.
1038  PM *phi_matcher =
1039  new PM(fst2, MATCH_INPUT, phi_label, false);
1040  SortedMatcher<F> *sorted_matcher =
1041  new SortedMatcher<F>(fst1, MATCH_NONE); // tell it
1042  // not to use this matcher, as this would mean we would
1043  // not follow phi transitions.
1044  impl_opts.matcher1 = sorted_matcher;
1045  impl_opts.matcher2 = phi_matcher;
1046  *ofst = ComposeFst<Arc>(fst1, fst2, impl_opts);
1047  Connect(ofst);
1048 }
#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 609 of file lattice-weight.h.

References Compare().

611  {
612  return (Compare(w1, w2) >= 0 ? w1 : w2);
613 }
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 460 of file fstext-utils-inl.h.

References PrecedingInputSymbolsAreSameClass().

Referenced by TestMakeSymbolsSame().

460  {
461  IdentityFunction<typename Arc::Label> f;
462  return PrecedingInputSymbolsAreSameClass(start_is_epsilon, fst, f);
463 }
Definition: graph.dox:21
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 466 of file fstext-utils-inl.h.

Referenced by PrecedingInputSymbolsAreSame(), and TestMakeSymbolsSameClass().

466  {
467  typedef typename F::Result ClassType;
468  typedef typename Arc::StateId StateId;
469  vector<ClassType> classes;
470  ClassType noClass = f(kNoLabel);
471 
472  if (start_is_epsilon) {
473  StateId start_state = fst.Start();
474  if (start_state < 0 || start_state == kNoStateId)
475  return true; // empty fst-- doesn't matter.
476  classes.resize(start_state+1, noClass);
477  classes[start_state] = 0;
478  }
479 
480  for (StateIterator<Fst<Arc> > siter(fst); !siter.Done(); siter.Next()) {
481  StateId s = siter.Value();
482  for (ArcIterator<Fst<Arc> > aiter(fst, s); !aiter.Done(); aiter.Next()) {
483  const Arc &arc = aiter.Value();
484  if (classes.size() <= arc.nextstate)
485  classes.resize(arc.nextstate+1, noClass);
486  if (classes[arc.nextstate] == noClass)
487  classes[arc.nextstate] = f(arc.ilabel);
488  else
489  if (classes[arc.nextstate] != f(arc.ilabel))
490  return false;
491  }
492  }
493  return true;
494 }
fst::StdArc::StateId StateId
Definition: graph.dox:21
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 359 of file fstext-utils-test.cc.

359  {
360  std::cout << message << "\n";
361  FstPrinter<Arc> fstprinter(fst, NULL, NULL, NULL, false, true, "\t");
362  fstprinter.Print(&std::cout, "standard output");
363 }
Definition: graph.dox:21
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 
)

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)
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)
fst::StdArc::Weight Weight
void PropagateFinal ( typename Arc::Label  phi_label,
MutableFst< Arc > *  fst 
)

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

References KALDI_WARN, and PropagateFinalInternal().

Referenced by main().

1085  {
1086  typedef typename Arc::StateId StateId;
1087  if (fst->Properties(kIEpsilons, true)) // just warn.
1088  KALDI_WARN << "PropagateFinal: this may not work as desired "
1089  "since your FST has input epsilons.";
1090  StateId num_states = fst->NumStates();
1091  for (StateId s = 0; s < num_states; s++)
1092  PropagateFinalInternal(phi_label, s, fst);
1093 }
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 1051 of file fstext-utils-inl.h.

References KALDI_ASSERT, and Times().

Referenced by PropagateFinal().

1054  {
1055  typedef typename Arc::Weight Weight;
1056  if (fst->Final(s) == Weight::Zero()) {
1057  // search for phi transition. We assume there
1058  // is just one-- phi nondeterminism is not allowed
1059  // anyway.
1060  int num_phis = 0;
1061  for (ArcIterator<Fst<Arc> > aiter(*fst, s);
1062  !aiter.Done(); aiter.Next()) {
1063  const Arc &arc = aiter.Value();
1064  if (arc.ilabel == phi_label) {
1065  num_phis++;
1066  if (arc.nextstate == s) continue; // don't expect
1067  // phi loops but ignore them anyway.
1068 
1069  // If this recurses infinitely, it means there
1070  // are loops of phi transitions, which there should
1071  // not be in a normal backoff LM. We could make this
1072  // routine work for this case, but currently there is
1073  // no need.
1074  PropagateFinalInternal(phi_label, arc.nextstate, fst);
1075  if (fst->Final(arc.nextstate) != Weight::Zero())
1076  fst->SetFinal(s, Times(fst->Final(arc.nextstate), arc.weight));
1077  }
1078  KALDI_ASSERT(num_phis <= 1 && "Phi nondeterminism found");
1079  }
1080  }
1081 }
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 210 of file push-lattice.cc.

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

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

211  {
212  CompactLatticePusher<Weight, IntType> pusher(clat);
213  return pusher.Push();
214 }
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 217 of file push-lattice.cc.

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

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

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

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

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

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

References ReadFstKaldi().

110  {
111  fst::StdVectorFst *fst = ReadFstKaldi(rxfilename);
112  *ofst = *fst;
113  delete fst;
114 }
Definition: graph.dox:21
fst::StdVectorFst StdVectorFst
void ReadFstKaldi(std::string rxfilename, fst::StdVectorFst *ofst)
Fst< StdArc > * ReadFstKaldiGeneric ( std::string  rxfilename,
bool  throw_on_err 
)

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

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

Referenced by main().

45  {
46  if (rxfilename == "") rxfilename = "-"; // interpret "" as stdin,
47  // for compatibility with OpenFst conventions.
48  kaldi::Input ki(rxfilename);
49  fst::FstHeader hdr;
50  // Read FstHeader which contains the type of FST
51  if (!hdr.Read(ki.Stream(), rxfilename)) {
52  if(throw_on_err) {
53  KALDI_ERR << "Reading FST: error reading FST header from "
54  << kaldi::PrintableRxfilename(rxfilename);
55  } else {
56  KALDI_WARN << "We fail to read FST header from "
57  << kaldi::PrintableRxfilename(rxfilename)
58  << ". A NULL pointer is returned.";
59  return NULL;
60  }
61  }
62  // Check the type of Arc
63  if (hdr.ArcType() != fst::StdArc::Type()) {
64  if(throw_on_err) {
65  KALDI_ERR << "FST with arc type " << hdr.ArcType() << " is not supported.";
66  } else {
67  KALDI_WARN << "Fst with arc type" << hdr.ArcType()
68  << " is not supported. A NULL pointer is returned.";
69  return NULL;
70  }
71  }
72  // Read the FST
73  FstReadOptions ropts("<unspecified>", &hdr);
74  Fst<StdArc> *fst = NULL;
75  if (hdr.FstType() == "const") {
76  fst = ConstFst<StdArc>::Read(ki.Stream(), ropts);
77  } else if (hdr.FstType() == "vector") {
78  fst = VectorFst<StdArc>::Read(ki.Stream(), ropts);
79  }
80  if (!fst) {
81  if(throw_on_err) {
82  KALDI_ERR << "Could not read fst from "
83  << kaldi::PrintableRxfilename(rxfilename);
84  } else {
85  KALDI_WARN << "Could not read fst from "
86  << kaldi::PrintableRxfilename(rxfilename)
87  << ". A NULL pointer is returned.";
88  return NULL;
89  }
90  }
91  return fst;
92 }
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
#define KALDI_WARN
Definition: kaldi-error.h:130
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 remove-eps-local-inl.h.

Referenced by TrainingGraphCompiler::CompileGraph(), TrainingGraphCompiler::CompileGraphs(), SimpleDecoder::GetBestPath(), FasterDecoder::GetBestPath(), BiglmFasterDecoder::GetBestPath(), kaldi::GetHmmAsFst(), NBestDecoder::GetNBestLattice(), main(), ArpaLmCompiler::RemoveRedundantStates(), SafeDeterminizeMinimizeWrapper(), SafeDeterminizeMinimizeWrapperInLog(), and TestRemoveEpsLocal().

309  {
310  RemoveEpsLocalClass<Arc> c(fst); // work gets done in initializer.
311 }
Definition: graph.dox:21
void RemoveEpsLocalSpecial ( MutableFst< StdArc > *  fst)
inline

As RemoveEpsLocal but takes care to preserve stochasticity when cast to LogArc.

Definition at line 314 of file remove-eps-local-inl.h.

Referenced by main(), and TestRemoveEpsLocalSpecial().

314  {
315  // work gets done in initializer.
316  RemoveEpsLocalClass<StdArc, ReweightPlusLogArc> c(fst);
317 }
Definition: graph.dox:21
void RemoveSomeInputSymbols