fst Namespace Reference

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

Namespaces

 internal
 
 pre_determinize_helpers
 

Classes

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

Typedefs

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

Enumerations

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

Functions

template<class Arc >
static VectorFst< Arc > * GenAcceptorFromSequence (const vector< typename Arc::Label > &symbols, float cost)
 
template<class Arc >
static float CheckPhones (const VectorFst< Arc > &linear_fst, const vector< typename Arc::Label > &phone_ids, const vector< typename Arc::Label > &disambig_ids, const vector< typename Arc::Label > &phone_seq, const vector< vector< typename Arc::Label > > &ilabel_info, int N, int P)
 
template<class Arc >
static VectorFst< Arc > * GenRandPhoneSeq (vector< typename Arc::Label > &phone_syms, vector< typename Arc::Label > &disambig_syms, typename Arc::Label subsequential_symbol, int num_subseq_syms, float seq_prob, vector< typename Arc::Label > *phoneseq_out)
 
static void TestContextFst (bool verbose, bool use_matcher)
 
void ComposeContext (const vector< int32 > &disambig_syms, int32 context_width, int32 central_position, VectorFst< StdArc > *ifst, VectorFst< StdArc > *ofst, vector< vector< int32 > > *ilabels_out, bool project_ifst=false)
 Used in the command-line tool fstcomposecontext. More...
 
void AddSubsequentialLoop (StdArc::Label subseq_symbol, MutableFst< StdArc > *fst)
 Modifies an FST so that it transuces the same paths, but the input side of the paths can all have the subsequential symbol '$' appended to them any number of times (we could easily specify the number of times, but accepting any number of repetitions is just more convenient). More...
 
void WriteILabelInfo (std::ostream &os, bool binary, const vector< vector< int32 > > &ilabel_info)
 Utility function for writing ilabel-info vectors to disk. More...
 
void ReadILabelInfo (std::istream &is, bool binary, vector< vector< int32 > > *ilabel_info)
 Utility function for reading ilabel-info vectors from disk. More...
 
SymbolTable * CreateILabelInfoSymbolTable (const vector< vector< int32 > > &ilabel_info, const SymbolTable &phones_symtab, std::string separator, std::string disambig_prefix)
 The following function is mainly of use for printing and debugging. More...
 
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)
 
void ComposeContextLeftBiphone (int32 nonterm_phones_offset, const vector< int32 > &disambig_syms_in, const VectorFst< StdArc > &ifst, VectorFst< StdArc > *ofst, std::vector< std::vector< int32 > > *ilabels)
 This is a variant of the function ComposeContext() which is to be used with our "grammar FST" framework (see The ContextFst object, i.e. More...
 
int32 GetEncodingMultiple (int32 nonterm_phones_offset)
 
void ComposeContextLeftBiphone (int32 nonterm_phones_offset, const vector< int32 > &disambig_syms, const VectorFst< StdArc > &ifst, VectorFst< StdArc > *ofst, vector< vector< int32 > > *ilabels)
 This is a variant of the function ComposeContext() which is to be used with our "grammar FST" framework (see The ContextFst object, i.e. More...
 
template<class Arc >
void WriteFstKaldi (std::ostream &os, bool binary, const VectorFst< Arc > &t)
 
template<class W >
bool StrToWeight (const std::string &s, bool allow_zero, W *w)
 
template<class Arc >
void ReadFstKaldi (std::istream &is, bool binary, VectorFst< Arc > *fst)
 
VectorFst< StdArc > * ReadFstKaldi (std::string rxfilename)
 
Fst< StdArc > * ReadFstKaldiGeneric (std::string rxfilename, bool throw_on_err)
 
VectorFst< StdArc > * CastOrConvertToVectorFst (Fst< StdArc > *fst)
 
void ReadFstKaldi (std::string rxfilename, fst::StdVectorFst *ofst)
 
void WriteFstKaldi (const VectorFst< StdArc > &fst, std::string wxfilename)
 
fst::VectorFst< fst::StdArc > * ReadAndPrepareLmFst (std::string rxfilename)
 
void ReadFstKaldi (std::string rxfilename, VectorFst< StdArc > *ofst)
 
template<class Weight , class Int >
void ConvertLattice (const ExpandedFst< ArcTpl< Weight > > &ifst, MutableFst< ArcTpl< CompactLatticeWeightTpl< Weight, Int > > > *ofst, bool invert=true)
 Convert lattice from a normal FST to a CompactLattice FST. More...
 
template<class Weight , class Int >
void ConvertLattice (const ExpandedFst< ArcTpl< CompactLatticeWeightTpl< Weight, Int > > > &ifst, MutableFst< ArcTpl< Weight > > *ofst, bool invert=true)
 Convert lattice CompactLattice format to Lattice. More...
 
template<class WeightIn , class WeightOut >
void ConvertLattice (const ExpandedFst< ArcTpl< WeightIn > > &ifst, MutableFst< ArcTpl< WeightOut > > *ofst)
 Convert between CompactLattices and Lattices of different floating point types... More...
 
template<class Weight , class ScaleFloat >
void ScaleLattice (const 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 ()
 
static ConstFst< StdArc > * ReadConstFstFromStream (std::istream &is)
 
void PrepareForGrammarFst (int32 nonterm_phones_offset, VectorFst< StdArc > *fst)
 This function prepares 'ifst' for use in GrammarFst: it ensures that it has the expected properties, changing it slightly as needed. More...
 
void CopyToVectorFst (GrammarFst *grammar_fst, VectorFst< StdArc > *vector_fst)
 This function copies a GrammarFst to a VectorFst (intended mostly for testing and comparison purposes). More...
 
template<class T >
ArcticWeightTpl< T > Plus (const ArcticWeightTpl< T > &w1, const ArcticWeightTpl< T > &w2)
 
ArcticWeightTpl< floatPlus (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< floatTimes (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< floatDivide (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)
 
ConstFst< StdArc > * ReadAsConstFst (std::string rxfilename)
 
bool PrintProxyFstPath (const VectorFst< StdArc > &proxy, vector< vector< StdArc::Label > > *path, vector< StdArc::Weight > *weight, StdArc::StateId cur_state, vector< StdArc::Label > cur_path, StdArc::Weight cur_weight)
 

Detailed Description

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

../doc/grammar.dox).

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

Typedef Documentation

◆ ArcticWeight

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

◆ BaseFloat

typedef float BaseFloat

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

◆ CompactLatticeWeight

◆ CompactLatticeWeightCommonDivisor

◆ Label

typedef fst::StdArc::Label Label

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

◆ LatticeWeight

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

◆ StateId

typedef fst::StdArc::StateId StateId

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

◆ StatePropertiesType

typedef unsigned char StatePropertiesType

Definition at line 122 of file factor.h.

◆ StdArc

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

◆ StdVectorFst

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

◆ VectorFstHolder

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

◆ Weight

typedef fst::StdArc::Weight Weight

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

Enumeration Type Documentation

◆ anonymous enum

anonymous enum
Enumerator
kStateHasEpsilonArcsEntering 
kStateHasNonEpsilonArcsEntering 
kStateHasEpsilonArcsLeaving 
kStateHasNonEpsilonArcsLeaving 

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

◆ NonterminalValues

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

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

Enumerator
kNontermBos 
kNontermBegin 
kNontermEnd 
kNontermReenter 
kNontermUserDefined 
kNontermMediumNumber 
kNontermBigNumber 

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

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

◆ StatePropertiesEnum

Enumerator
kStateFinal 
kStateInitial 
kStateArcsIn 
kStateMultipleArcsIn 
kStateArcsOut 
kStateMultipleArcsOut 
kStateOlabelsOut 
kStateIlabelsOut 

Definition at line 112 of file factor.h.

Function Documentation

◆ AcousticLatticeScale()

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()(), DiscriminativeSupervisionSplitter::PrepareLattice(), and NnetBatchDecoder::ProcessOutputUtterance().

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 }

◆ AddSelfLoops()

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
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
struct rnnlm::@11::@12 n
fst::StdArc::Label Label
fst::StdArc::Weight Weight

◆ AddSubsequentialLoop()

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

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

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

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

References rnnlm::i.

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

297  {
298  typedef StdArc Arc;
299  typedef typename Arc::StateId StateId;
300  typedef typename Arc::Weight Weight;
301 
302  vector<StateId> final_states;
303  for (StateIterator<MutableFst<Arc> > siter(*fst); !siter.Done(); siter.Next()) {
304  StateId s = siter.Value();
305  if (fst->Final(s) != Weight::Zero()) final_states.push_back(s);
306  }
307 
308  StateId superfinal = fst->AddState();
309  Arc arc(subseq_symbol, 0, Weight::One(), superfinal);
310  fst->AddArc(superfinal, arc); // loop at superfinal.
311  fst->SetFinal(superfinal, Weight::One());
312 
313  for (size_t i = 0; i < final_states.size(); i++) {
314  StateId s = final_states[i];
315  fst->AddArc(s, Arc(subseq_symbol, 0, fst->Final(s), superfinal));
316  // No, don't remove the final-weights of the original states..
317  // this is so we can add the subsequential loop in cases where
318  // there is no context, and it won't hurt.
319  // fst->SetFinal(s, Weight::Zero());
320  arc.nextstate = final_states[i];
321  }
322 }
fst::StdArc::StateId StateId
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
fst::StdArc StdArc
fst::StdArc::Weight Weight

◆ ApplyProbabilityScale()

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

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

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

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

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

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
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
fst::StdArc::Weight Weight

◆ ApproxEqual() [1/2]

◆ ApproxEqual() [2/2]

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

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

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

573  {
574  return (ApproxEqual(w1.Weight(), w2.Weight(), delta) && w1.String() == w2.String());
575 }
bool ApproxEqual(const CompactLatticeWeightTpl< WeightType, IntType > &w1, const CompactLatticeWeightTpl< WeightType, IntType > &w2, float delta=kDelta)

◆ CastOrConvertToVectorFst()

VectorFst< StdArc > * CastOrConvertToVectorFst ( Fst< StdArc > *  fst)

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

References KALDI_ASSERT.

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, we carete a new
102  // VectorFst<StdArc> initialized by 'fst', and delete 'fst'.
103  VectorFst<StdArc> *new_fst = new VectorFst<StdArc>(*fst);
104  delete fst;
105  return new_fst;
106  }
107 }
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:168

◆ CheckPhones()

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

Definition at line 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

◆ ClearSymbols()

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

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

It does not alter the symbol tables.

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

Referenced by MakeLoopFstCompare().

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
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21

◆ CompactLatticeHasAlignment()

bool CompactLatticeHasAlignment ( const ExpandedFst< ArcTpl< CompactLatticeWeightTpl< Weight, Int > > > &  fst)

Returns true if lattice has alignments, i.e.

it has any nonempty strings inside its weights.

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

Referenced by LatticeScale().

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
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21

◆ CompactLatticeWeightTest()

void fst::CompactLatticeWeightTest ( )

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

124  {
125  for(int32 i = 0; i < 100; i++) {
127  CompactLatticeWeight l3 = Plus(l1, l2);
128  CompactLatticeWeight l4 = Times(l1, l2);
129 
130  KALDI_ASSERT(Plus(l3, l3) == l3);
131  KALDI_ASSERT(Plus(l1, l2) == Plus(l2, l1)); // commutativity of plus
132  KALDI_ASSERT(Plus(l3, CompactLatticeWeight::Zero()) == l3); // x + 0 = x
133  KALDI_ASSERT(Times(l3, CompactLatticeWeight::One()) == l3); // x * 1 = x
134  KALDI_ASSERT(Times(l3, CompactLatticeWeight::Zero()) == CompactLatticeWeight::Zero()); // x * 0 = 0
135  NaturalLess<CompactLatticeWeight> nl;
136  bool a = nl(l1, l2);
137  bool b = (Plus(l1, l2) == l1 && l1 != l2);
138  KALDI_ASSERT(a == b);
139 
140  KALDI_ASSERT(Compare(l1, Plus(l1, l2)) != 1); // so do not have l1 > l1 + l2
142  KALDI_ASSERT(Times(Plus(l1, l2), Plus(l5, l6)) ==
143  Plus(Times(l1, l5), Plus(Times(l1, l6),
144  Plus(Times(l2, l5), Times(l2, l6))))); // * distributes over +
145  KALDI_ASSERT(l1.Member() && l2.Member() && l3.Member() && l4.Member()
146  && l5.Member() && l6.Member());
147  if (l2 != CompactLatticeWeight::Zero()) {
148  KALDI_ASSERT(ApproxEqual(Divide(Times(l1, l2), l2, DIVIDE_RIGHT), l1)); // (a*b) / b = a if b != 0
149  KALDI_ASSERT(ApproxEqual(Divide(Times(l2, l1), l2, DIVIDE_LEFT), l1)); // (a*b) / b = a if b != 0
150  }
151  KALDI_ASSERT(ApproxEqual(l1, l1.Quantize()));
152 
153  std::ostringstream s1;
154  s1 << l1;
155  std::istringstream s2(s1.str());
156  s2 >> l2;
157  KALDI_ASSERT(ApproxEqual(l1, l2));
158  std::cout << s1.str() << '\n';
159 
160  {
161  std::ostringstream s1b;
162  l1.Write(s1b);
163  std::istringstream s2b(s1b.str());
164  l3.Read(s2b);
165  KALDI_ASSERT(l1 == l3);
166  }
167 
169  std::cout << "l5 = " << l5 << '\n';
170  std::cout << "l6 = " << l6 << '\n';
171  l1 = divisor(l5, l6);
172  std::cout << "div = " << l1 << '\n';
173  if (l1 != CompactLatticeWeight::Zero()) {
174  l2 = Divide(l5, l1, DIVIDE_LEFT);
175  l3 = Divide(l6, l1, DIVIDE_LEFT);
176  std::cout << "l2 = " << l2 << '\n';
177  std::cout << "l3 = " << l3 << '\n';
178  l4 = divisor(l2, l3); // make sure l2 is now one.
179  std::cout << "l4 = " << l4 << '\n';
180  KALDI_ASSERT(ApproxEqual(l4, CompactLatticeWeight::One()));
181  } else {
182  KALDI_ASSERT(l5 == CompactLatticeWeight::Zero()
183  && l6 == CompactLatticeWeight::Zero());
184  }
185  }
186 }
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:168
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:264
CompactLatticeWeightTpl< LatticeWeight, int32 > CompactLatticeWeight
CompactLatticeWeightCommonDivisorTpl< LatticeWeight, int32 > CompactLatticeWeightCommonDivisor

◆ Compare() [1/3]

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

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

Definition at line 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(), LatticeDeterminizer< Weight, IntType >::MakeSubsetUnique(), NaturalLess< LatticeWeightTpl< FloatType > >::operator()(), NaturalLess< LatticeWeightTpl< float > >::operator()(), NaturalLess< LatticeWeightTpl< double > >::operator()(), NaturalLess< CompactLatticeWeightTpl< LatticeWeightTpl< FloatType >, IntType > >::operator()(), NaturalLess< CompactLatticeWeightTpl< LatticeWeightTpl< float >, int32 > >::operator()(), NaturalLess< CompactLatticeWeightTpl< LatticeWeightTpl< double >, int32 > >::operator()(), PruneSpecialClass< Arc >::Task::operator<(), Plus(), LatticeDeterminizer< Weight, IntType >::ProcessFinal(), and PruneSpecialClass< Arc >::ProcessState().

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 }

◆ Compare() [2/3]

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

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

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

593  {
594  int c1 = Compare(w1.Weight(), w2.Weight());
595  if (c1 != 0) return c1;
596  int l1 = w1.String().size(), l2 = w2.String().size();
597  // Use opposite order on the string lengths, so that if the costs are the same,
598  // the shorter string wins.
599  if (l1 > l2) return -1;
600  else if (l1 < l2) return 1;
601  for(int i = 0; i < l1; i++) {
602  if (w1.String()[i] < w2.String()[i]) return -1;
603  else if (w1.String()[i] > w2.String()[i]) return 1;
604  }
605  return 0;
606 }
int Compare(const TropicalWeight &w1, const TropicalWeight &w2)

◆ Compare() [3/3]

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

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

655  {
656  float f1 = w1.Value(), f2 = w2.Value();
657  if (f1 == f2) return 0;
658  else if (f1 > f2) return -1;
659  else return 1;
660 }

◆ ComposeContext()

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

Used in the command-line tool fstcomposecontext.

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

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

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

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

Referenced by main().

250  {
251  KALDI_ASSERT(ifst != NULL && ofst != NULL);
252  KALDI_ASSERT(context_width > 0);
253  KALDI_ASSERT(central_position >= 0);
254  KALDI_ASSERT(central_position < context_width);
255 
256  vector<int32> disambig_syms(disambig_syms_in);
257  std::sort(disambig_syms.begin(), disambig_syms.end());
258 
259  vector<int32> all_syms;
260  GetInputSymbols(*ifst, false/*no eps*/, &all_syms);
261  std::sort(all_syms.begin(), all_syms.end());
262  vector<int32> phones;
263  for (size_t i = 0; i < all_syms.size(); i++)
264  if (!std::binary_search(disambig_syms.begin(),
265  disambig_syms.end(), all_syms[i]))
266  phones.push_back(all_syms[i]);
267 
268  // Get subsequential symbol that does not clash with
269  // any disambiguation symbol or symbol in the FST.
270  int32 subseq_sym = 1;
271  if (!all_syms.empty())
272  subseq_sym = std::max(subseq_sym, all_syms.back() + 1);
273  if (!disambig_syms.empty())
274  subseq_sym = std::max(subseq_sym, disambig_syms.back() + 1);
275 
276  // if central_position == context_width-1, it's left-context, and no
277  // subsequential symbol is needed.
278  if (central_position != context_width-1) {
279  AddSubsequentialLoop(subseq_sym, ifst);
280  if (project_ifst) {
281  fst::Project(ifst, fst::PROJECT_INPUT);
282  }
283  }
284 
285  InverseContextFst inv_c(subseq_sym, phones, disambig_syms,
286  context_width, central_position);
287 
288  // The following statement is equivalent to the following
289  // (if FSTs had the '*' operator for composition):
290  // (*ofst) = inv(inv_c) * (*ifst)
291  ComposeDeterministicOnDemandInverse(*ifst, &inv_c, ofst);
292 
293  inv_c.SwapIlabelInfo(ilabels_out);
294 }
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 == tr...
void ComposeDeterministicOnDemandInverse(const Fst< Arc > &right, DeterministicOnDemandFst< Arc > *left, MutableFst< Arc > *fst_composed)
This function does &#39;*fst_composed = Compose(Inverse(*fst2), fst1)&#39; Note that the arguments are revers...
void AddSubsequentialLoop(StdArc::Label subseq_symbol, MutableFst< StdArc > *fst)
Modifies an FST so that it transuces the same paths, but the input side of the paths can all have the...
Definition: context-fst.cc:296
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:168

◆ ComposeContextLeftBiphone() [1/2]

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

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

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

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

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

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

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

Referenced by GetEncodingMultiple(), and main().

201  {
202 
203  vector<int32> disambig_syms(disambig_syms_in);
204  std::sort(disambig_syms.begin(), disambig_syms.end());
205 
206  vector<int32> all_syms;
207  GetInputSymbols(ifst, false/*no eps*/, &all_syms);
208  std::sort(all_syms.begin(), all_syms.end());
209  vector<int32> phones;
210  for (size_t i = 0; i < all_syms.size(); i++)
211  if (!std::binary_search(disambig_syms.begin(),
212  disambig_syms.end(), all_syms[i]) &&
213  all_syms[i] < nonterm_phones_offset)
214  phones.push_back(all_syms[i]);
215 
216 
217  InverseLeftBiphoneContextFst inv_c(nonterm_phones_offset,
218  phones, disambig_syms);
219 
220  // The following statement is equivalent to the following
221  // (if FSTs had the '*' operator for composition):
222  // (*ofst) = inv(inv_c) * (*ifst)
223  ComposeDeterministicOnDemandInverse(ifst, &inv_c, ofst);
224 
225  inv_c.SwapIlabelInfo(ilabels);
226 }
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 == tr...
void ComposeDeterministicOnDemandInverse(const Fst< Arc > &right, DeterministicOnDemandFst< Arc > *left, MutableFst< Arc > *fst_composed)
This function does &#39;*fst_composed = Compose(Inverse(*fst2), fst1)&#39; Note that the arguments are revers...

◆ ComposeContextLeftBiphone() [2/2]

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

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

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

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

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

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

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

Referenced by GetEncodingMultiple(), and main().

201  {
202 
203  vector<int32> disambig_syms(disambig_syms_in);
204  std::sort(disambig_syms.begin(), disambig_syms.end());
205 
206  vector<int32> all_syms;
207  GetInputSymbols(ifst, false/*no eps*/, &all_syms);
208  std::sort(all_syms.begin(), all_syms.end());
209  vector<int32> phones;
210  for (size_t i = 0; i < all_syms.size(); i++)
211  if (!std::binary_search(disambig_syms.begin(),
212  disambig_syms.end(), all_syms[i]) &&
213  all_syms[i] < nonterm_phones_offset)
214  phones.push_back(all_syms[i]);
215 
216 
217  InverseLeftBiphoneContextFst inv_c(nonterm_phones_offset,
218  phones, disambig_syms);
219 
220  // The following statement is equivalent to the following
221  // (if FSTs had the '*' operator for composition):
222  // (*ofst) = inv(inv_c) * (*ifst)
223  ComposeDeterministicOnDemandInverse(ifst, &inv_c, ofst);
224 
225  inv_c.SwapIlabelInfo(ilabels);
226 }
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 == tr...
void ComposeDeterministicOnDemandInverse(const Fst< Arc > &right, DeterministicOnDemandFst< Arc > *left, MutableFst< Arc > *fst_composed)
This function does &#39;*fst_composed = Compose(Inverse(*fst2), fst1)&#39; Note that the arguments are revers...

◆ ComputeStateInfo()

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

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

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

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

References kStateHasEpsilonArcsEntering, kStateHasEpsilonArcsLeaving, kStateHasNonEpsilonArcsEntering, and kStateHasNonEpsilonArcsLeaving.

Referenced by 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
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21

◆ ConvertFstToLattice()

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

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

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

Referenced by ConvertLattice().

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 }

◆ ConvertLattice() [1/7]

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

Convert lattice from a normal FST to a CompactLattice FST.

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

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

References Factor(), and KALDI_PARANOID_ASSERT.

Referenced by ConvertLattice(), kaldi::ConvertLatticeToUnweightedAcceptor(), kaldi::ConvertToCompactLattice(), kaldi::ConvertToLattice(), DiscriminativeExampleSplitter::CreateOutputLattice(), 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:181
fst::StdArc::Weight Weight

◆ ConvertLattice() [2/7]

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

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

References ConvertLattice().

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.
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21

◆ ConvertLattice() [3/7]

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

Convert lattice CompactLattice format to Lattice.

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

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

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

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

◆ ConvertLattice() [4/7]

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

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

References ConvertLattice().

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.
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21

◆ ConvertLattice() [5/7]

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

Converts CompactLattice with double to Lattice with float.

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

References ConvertLattice().

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.
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21

◆ ConvertLattice() [6/7]

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

Converts CompactLattice with float to Lattice with double.

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

References ConvertFstToLattice(), and ConvertLattice().

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.
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21

◆ ConvertLattice() [7/7]

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

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

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

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

References ConvertLatticeWeight(), and KALDI_PARANOID_ASSERT.

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:181

◆ ConvertLatticeWeight() [1/3]

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

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

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

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

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

Referenced by ConvertLattice().

822  {
823  w_out->SetValue1(w_in.Value1());
824  w_out->SetValue2(w_in.Value2());
825 }

◆ ConvertLatticeWeight() [2/3]

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

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

830  {
831  LatticeWeightTpl<Float2> weight2(w_in.Weight().Value1(),
832  w_in.Weight().Value2());
833  w_out->SetWeight(weight2);
834  w_out->SetString(w_in.String());
835 }

◆ ConvertLatticeWeight() [3/3]

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

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

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

841  {
842  TropicalWeightTpl<Float2> w1(w_in.Value1());
843  TropicalWeightTpl<Float2> w2(w_in.Value2());
844  *w_out = Times(w1, w2);
845 }
CompactLatticeWeightTpl< WeightType, IntType > Times(const CompactLatticeWeightTpl< WeightType, IntType > &w1, const CompactLatticeWeightTpl< WeightType, IntType > &w2)

◆ ConvertNbestToVector()

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(), MinimizeEncoded(), 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
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
fst::StdArc::Weight Weight
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:168

◆ ConvertToCost() [1/3]

◆ ConvertToCost() [2/3]

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

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

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

◆ ConvertToCost() [3/3]

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

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

858  {
859  return w.Value();
860 }

◆ CopyToVectorFst()

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

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

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

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

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

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

Referenced by main().

868  {
869  typedef GrammarFstArc::StateId GrammarStateId; // int64
870  typedef StdArc::StateId StdStateId; // int
871  typedef StdArc::Label Label;
872  typedef StdArc::Weight Weight;
873 
874  std::vector<std::pair<GrammarStateId, StdStateId> > queue;
875  std::unordered_map<GrammarStateId, StdStateId> state_map;
876 
877  vector_fst->DeleteStates();
878  state_map[grammar_fst->Start()] = vector_fst->AddState(); // state 0.
879  vector_fst->SetStart(0);
880 
881  queue.push_back(
882  std::pair<GrammarStateId, StdStateId>(grammar_fst->Start(), 0));
883 
884  while (!queue.empty()) {
885  std::pair<GrammarStateId, StdStateId> p = queue.back();
886  queue.pop_back();
887  GrammarStateId grammar_state = p.first;
888  StdStateId std_state = p.second;
889  vector_fst->SetFinal(std_state, grammar_fst->Final(grammar_state));
890  ArcIterator<GrammarFst> aiter(*grammar_fst, grammar_state);
891  for (; !aiter.Done(); aiter.Next()) {
892  const GrammarFstArc &grammar_arc = aiter.Value();
893  StdArc std_arc;
894  std_arc.ilabel = grammar_arc.ilabel;
895  std_arc.olabel = grammar_arc.olabel;
896  std_arc.weight = grammar_arc.weight;
897  GrammarStateId next_grammar_state = grammar_arc.nextstate;
898  StdStateId next_std_state;
899  std::unordered_map<GrammarStateId, StdStateId>::const_iterator
900  state_iter = state_map.find(next_grammar_state);
901  if (state_iter == state_map.end()) {
902  next_std_state = vector_fst->AddState();
903  state_map[next_grammar_state] = next_std_state;
904  queue.push_back(std::pair<GrammarStateId, StdStateId>(
905  next_grammar_state, next_std_state));
906  } else {
907  next_std_state = state_iter->second;
908  }
909  std_arc.nextstate = next_std_state;
910  vector_fst->AddArc(std_state, std_arc);
911  }
912  }
913 }
fst::StdArc::StateId StateId
fst::StdArc StdArc
fst::StdArc::Label Label
fst::StdArc::Weight Weight

◆ CreateBackoffFst()

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 }
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
fst::StdArc StdArc
fst::StdVectorFst StdVectorFst

◆ CreateFactorFst()

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:133
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
fst::StdArc::Label Label
fst::StdArc::Weight Weight

◆ CreateILabelInfoSymbolTable()

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

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

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

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

Referenced by main().

347  { // e.g. separator = "/", initial-disambig="#-1"
348  KALDI_ASSERT(!info.empty() && !info[0].empty());
349  SymbolTable *ans = new SymbolTable("ilabel-info-symtab");
350  int64 s = ans->AddSymbol(phones_symtab.Find(static_cast<int64>(0)));
351  assert(s == 0);
352  for (size_t i = 1; i < info.size(); i++) {
353  if (info[i].size() == 0) {
354  KALDI_ERR << "Invalid ilabel-info";
355  }
356  if (info[i].size() == 1 &&
357  info[i][0] <= 0) {
358  if (info[i][0] == 0) { // special symbol at start that we want to call #-1.
359  s = ans->AddSymbol(initial_disambig);
360  if (s != i) {
361  KALDI_ERR << "Disambig symbol " << initial_disambig
362  << " already in vocab";
363  }
364  } else {
365  std::string disambig_sym = phones_symtab.Find(-info[i][0]);
366  if (disambig_sym == "") {
367  KALDI_ERR << "Disambig symbol " << -info[i][0]
368  << " not in phone symbol-table";
369  }
370  s = ans->AddSymbol(disambig_sym);
371  if (s != i) {
372  KALDI_ERR << "Disambig symbol " << disambig_sym
373  << " already in vocab";
374  }
375  }
376  } else {
377  // is a phone-context-window.
378  std::string newsym;
379  for (size_t j = 0; j < info[i].size(); j++) {
380  std::string phonesym = phones_symtab.Find(info[i][j]);
381  if (phonesym == "") {
382  KALDI_ERR << "Symbol " << info[i][j]
383  << " not in phone symbol-table";
384  }
385  if (j != 0) newsym += separator;
386  newsym += phonesym;
387  }
388  int64 s = ans->AddSymbol(newsym);
389  if (s != static_cast<int64>(i)) {
390  KALDI_ERR << "Some problem with duplicate symbols";
391  }
392  }
393  }
394  return ans;
395 }
#define KALDI_ERR
Definition: kaldi-error.h:126
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:168

◆ CreateMapFst()

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:133
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
fst::StdArc::Label Label
fst::StdArc::Weight Weight

◆ CreateNewSymbols()

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

◆ CreateResultFst()

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 }
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
fst::StdArc StdArc
fst::StdVectorFst StdVectorFst

◆ CreateSuperFinal()

Arc::StateId CreateSuperFinal ( MutableFst< Arc > *  fst)

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

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

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
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
fst::StdArc::Weight Weight

◆ DefaultLatticeScale()

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 }

◆ DeleteISymbols()

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
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
fst::StdArc::Label Label

◆ DeleteTestFst()

void fst::DeleteTestFst ( StdVectorFst fst)

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

111  {
112  delete fst;
113 }
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21

◆ DeterminizeInLog()

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 }
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21

◆ DeterminizeLatticeDeletePhones()

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

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

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

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

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

◆ DeterminizeLatticePhonePrunedFirstPass()

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

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

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

Definition at line 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 }
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
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.

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

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

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

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

◆ DeterminizeStarInLog()

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

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

References DeterminizeStar().

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

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 }
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
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...

◆ Divide() [1/5]

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

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

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 }

◆ Divide() [2/5]

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

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

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

◆ Divide() [3/5]

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

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

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

◆ Divide() [4/5]

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

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

373  {
374  typedef FloatType T;
375  T a = w1.Value1() - w2.Value1(), b = w1.Value2() - w2.Value2();
376  if (a != a || b != b || a == -numeric_limits<T>::infinity()
377  || b == -numeric_limits<T>::infinity()) {
378  KALDI_WARN << "LatticeWeightTpl::Divide, NaN or invalid number produced. "
379  << "[dividing by zero?] Returning zero";
380  return LatticeWeightTpl<T>::Zero();
381  }
382  if (a == numeric_limits<T>::infinity() ||
383  b == numeric_limits<T>::infinity())
384  return LatticeWeightTpl<T>::Zero(); // not a valid number if only one is infinite.
385  return LatticeWeightTpl<T>(a, b);
386 }
#define KALDI_WARN
Definition: kaldi-error.h:129

◆ Divide() [5/5]

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

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

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

692  {
693  if (w1.Weight() == WeightType::Zero()) {
694  if (w2.Weight() != WeightType::Zero()) {
695  return CompactLatticeWeightTpl<WeightType, IntType>::Zero();
696  } else {
697  KALDI_ERR << "Division by zero [0/0]";
698  }
699  } else if (w2.Weight() == WeightType::Zero()) {
700  KALDI_ERR << "Error: division by zero";
701  }
702  WeightType w = Divide(w1.Weight(), w2.Weight());
703 
704  const vector<IntType> v1 = w1.String(), v2 = w2.String();
705  if (v2.size() > v1.size()) {
706  KALDI_ERR << "Cannot divide, length mismatch";
707  }
708  typename vector<IntType>::const_iterator v1b = v1.begin(),
709  v1e = v1.end(), v2b = v2.begin(), v2e = v2.end();
710  if (div == DIVIDE_LEFT) {
711  if (!std::equal(v2b, v2e, v1b)) { // v2 must be identical to first part of v1.
712  KALDI_ERR << "Cannot divide, data mismatch";
713  }
714  return CompactLatticeWeightTpl<WeightType, IntType>(
715  w, vector<IntType>(v1b+(v2e-v2b), v1e)); // return last part of v1.
716  } else if (div == DIVIDE_RIGHT) {
717  if (!std::equal(v2b, v2e, v1e-(v2e-v2b))) { // v2 must be identical to last part of v1.
718  KALDI_ERR << "Cannot divide, data mismatch";
719  }
720  return CompactLatticeWeightTpl<WeightType, IntType>(
721  w, vector<IntType>(v1b, v1e-(v2e-v2b))); // return first part of v1.
722 
723  } else {
724  KALDI_ERR << "Cannot divide CompactLatticeWeightTpl with DIVIDE_ANY";
725  }
726  return CompactLatticeWeightTpl<WeightType,IntType>::Zero(); // keep compiler happy.
727 }
#define KALDI_ERR
Definition: kaldi-error.h:126
CompactLatticeWeightTpl< WeightType, IntType > Divide(const CompactLatticeWeightTpl< WeightType, IntType > &w1, const CompactLatticeWeightTpl< WeightType, IntType > &w2, DivideType div=DIVIDE_ANY)

◆ EnsureEpsilonProperty()

void EnsureEpsilonProperty ( VectorFst< Arc > *  fst)

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

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

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

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

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

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

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

Referenced by main(), and TestEnsureEpsilonProperty().

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
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
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

◆ EqualAlign()

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

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

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

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

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

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

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:129
fst::StdArc::Weight Weight
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:168
int32 RandInt(int32 min_val, int32 max_val, struct RandomState *state)
Definition: kaldi-math.cc:94

◆ ExpandInputSequences()

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:133
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
struct rnnlm::@11::@12 n
fst::StdArc::Label Label
fst::StdArc::Weight Weight

◆ Factor() [1/2]

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(), 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:133
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
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

◆ Factor() [2/2]

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

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

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

References CreateFactorFst(), and Factor().

155  {
156  typedef typename Arc::Label Label;
157  vector<vector<Label> > symbols;
158  Factor(fst, ofst2, &symbols);
159  CreateFactorFst(symbols, ofst1);
160 }
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
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

◆ FileExists()

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 }

◆ FindSelfLoopWithILabel()

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

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

Referenced by EqualAlign().

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 }
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21

◆ FollowingInputSymbolsAreSame()

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

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

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

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

References FollowingInputSymbolsAreSameClass().

Referenced by MinimizeEncoded(), and TestMakeSymbolsSame().

497  {
498  IdentityFunction<typename Arc::Label> f;
499  return FollowingInputSymbolsAreSameClass(end_is_epsilon, fst, f);
500 }
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
bool FollowingInputSymbolsAreSameClass(bool end_is_epsilon, const Fst< Arc > &fst, const F &f)

◆ FollowingInputSymbolsAreSameClass()

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

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

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

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
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
fst::StdArc::Weight Weight

◆ GenAcceptorFromSequence()

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
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
int Rand(struct RandomState *state)
Definition: kaldi-math.cc:44
fst::StdArc::Weight Weight

◆ GenRandPhoneSeq()

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

Definition at line 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:168

◆ GetEncodingMultiple()

int32 fst::GetEncodingMultiple ( int32  nonterm_phones_offset)
inline

◆ GetInputSymbols()

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(), ComposeContextLeftBiphone(), 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:133
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:168

◆ GetLinearSymbolSequence()

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(), MinimizeEncoded(), MinimumBayesRisk::MinimumBayesRisk(), NnetBatchDecoder::ProcessOutputUtterance(), 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
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
LatticeWeightTpl< FloatType > Times(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2)
fst::StdArc::Weight Weight

◆ GetOutputSymbols()

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:133
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:168

◆ GetStateProperties()

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
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
unsigned char StatePropertiesType
Definition: factor.h:122
fst::StdArc::Weight Weight

◆ GetSymbols()

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:168

◆ GraphLatticeScale()

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 }

◆ HighestNumberedInputSymbol()

Arc::Label HighestNumberedInputSymbol ( const Fst< Arc > &  fst)

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

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

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

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
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
fst::StdArc::Label Label

◆ HighestNumberedOutputSymbol()

Arc::Label HighestNumberedOutputSymbol ( const Fst< Arc > &  fst)

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

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

Referenced by LatticeWordAligner::LatticeWordAligner().

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
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
fst::StdArc::Label Label

◆ IsStochasticFst() [1/2]

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

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

References ApproxEqual(), and Plus().

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

1176  {
1177  typedef LogArc Arc;
1178  typedef Arc::StateId StateId;
1179  typedef Arc::Weight Weight;
1180  bool first_time = true;
1181  bool ans = true;
1182  if (min_sum) *min_sum = LogArc::Weight::One();
1183  if (max_sum) *max_sum = LogArc::Weight::One();
1184  for (StateIterator<Fst<Arc> > siter(fst); !siter.Done(); siter.Next()) {
1185  StateId s = siter.Value();
1186  Weight sum = fst.Final(s);
1187  for (ArcIterator<Fst<Arc> > aiter(fst, s); !aiter.Done(); aiter.Next()) {
1188  const Arc &arc = aiter.Value();
1189  sum = Plus(sum, arc.weight);
1190  }
1191  if (!ApproxEqual(Weight::One(), sum, delta)) ans = false;
1192  if (first_time) {
1193  first_time = false;
1194  if (max_sum) *max_sum = sum;
1195  if (min_sum) *min_sum = sum;
1196  } else {
1197  // note that max and min are reversed from their normal
1198  // meanings here (max and min w.r.t. the underlying probabilities).
1199  if (max_sum && sum.Value() < max_sum->Value()) *max_sum = sum;
1200  if (min_sum && sum.Value() > min_sum->Value()) *min_sum = sum;
1201  }
1202  }
1203  if (first_time) { // just avoid NaNs if FST was empty.
1204  if (max_sum) *max_sum = Weight::One();
1205  if (min_sum) *min_sum = Weight::One();
1206  }
1207  return ans;
1208 }
fst::StdArc::StateId StateId
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
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:264

◆ IsStochasticFst() [2/2]

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

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

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

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

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

References ApproxEqual(), and Plus().

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  if (min_sum) *min_sum = Arc::Weight::One();
1145  if (max_sum) *max_sum = Arc::Weight::One();
1146  for (StateIterator<Fst<Arc> > siter(fst); !siter.Done(); siter.Next()) {
1147  StateId s = siter.Value();
1148  Weight sum = fst.Final(s);
1149  for (ArcIterator<Fst<Arc> > aiter(fst, s); !aiter.Done(); aiter.Next()) {
1150  const Arc &arc = aiter.Value();
1151  sum = Plus(sum, arc.weight);
1152  }
1153  if (!ApproxEqual(Weight::One(), sum, delta)) ans = false;
1154  if (first_time) {
1155  first_time = false;
1156  if (max_sum) *max_sum = sum;
1157  if (min_sum) *min_sum = sum;
1158  } else {
1159  if (max_sum && nl(*max_sum, sum)) *max_sum = sum;
1160  if (min_sum && nl(sum, *min_sum)) *min_sum = sum;
1161  }
1162  }
1163  if (first_time) { // just avoid NaNs if FST was empty.
1164  if (max_sum) *max_sum = Weight::One();
1165  if (min_sum) *min_sum = Weight::One();
1166  }
1167  return ans;
1168 }
fst::StdArc::StateId StateId
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
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:264

◆ IsStochasticFstInLog()

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

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

References IsStochasticFst(), and KALDI_ERR.

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

1218  {
1219  bool ans = false;
1220  LogArc::Weight log_min = LogArc::Weight::One(),
1221  log_max = LogArc::Weight::Zero();
1222  if (fst.Type() == "const") {
1223  ConstFst<LogArc> logfst;
1224  Cast(dynamic_cast<const ConstFst<StdArc>&>(fst), &logfst);
1225  ans = IsStochasticFst(logfst, delta, &log_min, &log_max);
1226  } else if (fst.Type() == "vector") {
1227  VectorFst<LogArc> logfst;
1228  Cast(dynamic_cast<const VectorFst<StdArc>&>(fst), &logfst);
1229  ans = IsStochasticFst(logfst, delta, &log_min, &log_max);
1230  } else {
1231  KALDI_ERR << "This version currently supports ConstFst<StdArc> "
1232  << "or VectorFst<StdArc>";
1233  }
1234  if (min_sum) *min_sum = StdArc::Weight(log_min.Value());
1235  if (max_sum) *max_sum = StdArc::Weight(log_max.Value());
1236  return ans;
1237 }
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
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...
#define KALDI_ERR
Definition: kaldi-error.h:126
fst::StdArc::Weight Weight

◆ LatticeScale()

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

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

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

Referenced by main().

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 }

◆ LatticeWeightTest()

void fst::LatticeWeightTest ( )

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

62  {
63  for(int32 i = 0; i < 100; i++) {
65  LatticeWeight l3 = Plus(l1, l2);
66  LatticeWeight l4 = Times(l1, l2);
67  BaseFloat f1 = l1.Value1() + l1.Value2(), f2 = l2.Value1() + l2.Value2(), f3 = l3.Value1() + l3.Value2(),
68  f4 = l4.Value1() + l4.Value2();
69  kaldi::AssertEqual(std::min(f1, f2), f3);
70  kaldi::AssertEqual(f1 + f2, f4);
71 
72  KALDI_ASSERT(Plus(l3, l3) == l3);
73  KALDI_ASSERT(Plus(l1, l2) == Plus(l2, l1)); // commutativity of plus
74  KALDI_ASSERT(Times(l1, l2) == Times(l2, l1)); // commutativity of Times (true for this semiring, not always)
75  KALDI_ASSERT(Plus(l3, LatticeWeight::Zero()) == l3); // x + 0 = x
76  KALDI_ASSERT(Times(l3, LatticeWeight::One()) == l3); // x * 1 = x
77  KALDI_ASSERT(Times(l3, LatticeWeight::Zero()) == LatticeWeight::Zero()); // x * 0 = 0
78 
79  KALDI_ASSERT(l3.Reverse().Reverse() == l3);
80 
81  NaturalLess<LatticeWeight> nl;
82  bool a = nl(l1, l2);
83  bool b = (Plus(l1, l2) == l1 && l1 != l2);
84  KALDI_ASSERT(a == b);
85 
86  KALDI_ASSERT(Compare(l1, Plus(l1, l2)) != 1); // so do not have l1 > l1 + l2
88  {
89  LatticeWeight wa = Times(Plus(l1, l2), Plus(l5, l6)),
90  wb = Plus(Times(l1, l5), Plus(Times(l1, l6),
91  Plus(Times(l2, l5), Times(l2, l6))));
92  if (!ApproxEqual(wa, wb)) {
93  std::cout << "l1 = " << l1 << ", l2 = " << l2
94  << ", l5 = " << l5 << ", l6 = " << l6 << "\n";
95  std::cout << "ERROR: " << wa << " != " << wb << "\n";
96  }
97  // KALDI_ASSERT(Times(Plus(l1, l2), Plus(l5, l6))
98  // == Plus(Times(l1, l5), Plus(Times(l1,l6),
99  // Plus(Times(l2, l5), Times(l2, l6))))); // * distributes over +
100  }
101  KALDI_ASSERT(l1.Member() && l2.Member() && l3.Member() && l4.Member()
102  && l5.Member() && l6.Member());
103  if (l2 != LatticeWeight::Zero())
104  KALDI_ASSERT(ApproxEqual(Divide(Times(l1, l2), l2), l1)); // (a*b) / b = a if b != 0
105  KALDI_ASSERT(ApproxEqual(l1, l1.Quantize()));
106 
107  std::ostringstream s1;
108  s1 << l1;
109  std::istringstream s2(s1.str());
110  s2 >> l2;
111  KALDI_ASSERT(ApproxEqual(l1, l2, 0.001));
112  std::cout << s1.str() << '\n';
113  {
114  std::ostringstream s1b;
115  l1.Write(s1b);
116  std::istringstream s2b(s1b.str());
117  l3.Read(s2b);
118  KALDI_ASSERT(l1 == l3);
119  }
120  }
121 }
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:168
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:275
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:264

◆ MakeFollowingInputSymbolsSame()

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

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

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

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

References MakeFollowingInputSymbolsSameClass().

Referenced by MinimizeEncoded(), and TestMakeSymbolsSame().

610  {
611  IdentityFunction<typename Arc::Label> f;
612  MakeFollowingInputSymbolsSameClass(end_is_epsilon, fst, f);
613 }
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
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.

◆ MakeFollowingInputSymbolsSameClass()

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

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

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

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

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

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
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
fst::StdArc::Weight Weight

◆ MakeLinearAcceptor()

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(), MinimizeEncoded(), 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

◆ MakeLinearAcceptorWithAlternatives()

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.

Referenced by MinimizeEncoded().

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:168

◆ MakeLoopFst()

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(), MinimizeEncoded(), 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
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
fst::StdArc::Label Label
fst::StdArc::Weight Weight
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:168

◆ MakeLoopFstCompare()

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

◆ MakePrecedingInputSymbolsSame()

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

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

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

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

References MakePrecedingInputSymbolsSameClass().

Referenced by MinimizeEncoded(), and TestMakeSymbolsSame().

528  {
529  IdentityFunction<typename Arc::Label> f;
530  MakePrecedingInputSymbolsSameClass(start_is_epsilon, fst, f);
531 }
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
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.

◆ MakePrecedingInputSymbolsSameClass()

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

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

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

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

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

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
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
fst::StdArc::Weight Weight
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:168

◆ MapInputSymbols()

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 MinimizeEncoded(), and 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:133
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21

◆ MinimizeCompactLattice()

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

This function minimizes the compact lattice.

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

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

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

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

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

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

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

◆ MinimizeEncoded()

◆ NbestAsFsts()

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 MinimizeEncoded(), 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 }
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
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:168

◆ NumArcs()

Arc::StateId NumArcs ( const ExpandedFst< Arc > &  fst)

Returns the total number of arcs in an FST.

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

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

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
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21

◆ operator!=() [1/2]

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 }

◆ operator!=() [2/2]

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

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

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

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

◆ operator<<() [1/2]

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

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

References LatticeWeightTpl< FloatType >::WriteFloatType().

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

◆ operator<<() [2/2]

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

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

References rnnlm::i.

730  {
731  strm << w.Weight();
732  CHECK(FLAGS_fst_weight_separator.size() == 1);
733  strm << FLAGS_fst_weight_separator[0]; // comma by default.
734  for(size_t i = 0; i < w.String().size(); i++) {
735  strm << w.String()[i];
736  if (i+1 < w.String().size())
737  strm << kStringSeparator; // '_'; defined in string-weight.h in OpenFst code.
738  }
739  return strm;
740 }

◆ operator==() [1/2]

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().

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

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 }

◆ operator==() [2/2]

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

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

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

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

◆ operator>>() [1/2]

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

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

References LatticeWeightTpl< FloatType >::ReadNoParen().

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

◆ operator>>() [2/2]

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

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

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

743  {
744  std::string s;
745  strm >> s;
746  if (strm.fail()) {
747  return strm;
748  }
749  CHECK(FLAGS_fst_weight_separator.size() == 1);
750  size_t pos = s.find_last_of(FLAGS_fst_weight_separator); // normally ","
751  if (pos == std::string::npos) {
752  strm.clear(std::ios::badbit);
753  return strm;
754  }
755  // get parts of str before and after the separator (default: ',');
756  std::string s1(s, 0, pos), s2(s, pos+1);
757  std::istringstream strm1(s1);
758  WeightType weight;
759  strm1 >> weight;
760  w.SetWeight(weight);
761  if (strm1.fail() || !strm1.eof()) {
762  strm.clear(std::ios::badbit);
763  return strm;
764  }
765  // read string part.
766  vector<IntType> string;
767  const char *c = s2.c_str();
768  while(*c != '\0') {
769  if (*c == kStringSeparator) // '_'
770  c++;
771  char *c2;
772  long int i = strtol(c, &c2, 10);
773  if (c2 == c || static_cast<long int>(static_cast<IntType>(i)) != i) {
774  strm.clear(std::ios::badbit);
775  return strm;
776  }
777  c = c2;
778  string.push_back(static_cast<IntType>(i));
779  }
780  w.SetString(string);
781  return strm;
782 }

◆ PenalizeArcsWithSomeInputSymbols()

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

Definition at line 58 of file fstrmsymbols.cc.

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

Referenced by main().

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
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
LatticeWeightTpl< FloatType > Times(const LatticeWeightTpl< FloatType > &w1, const LatticeWeightTpl< FloatType > &w2)
fst::StdArc::Label Label
fst::StdArc::Weight Weight

◆ PhiCompose()

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

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

References KALDI_ASSERT.

Referenced by main(), and MinimizeEncoded().

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:168

◆ Plus() [1/5]

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

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

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

◆ Plus() [2/5]

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

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

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

◆ Plus() [3/5]

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

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

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

◆ Plus() [4/5]

◆ Plus() [5/5]

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

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

References Compare().

667  {
668  return (Compare(w1, w2) >= 0 ? w1 : w2);
669 }
int Compare(const TropicalWeight &w1, const TropicalWeight &w2)

◆ PrecedingInputSymbolsAreSame()

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

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

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

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

References PrecedingInputSymbolsAreSameClass().

Referenced by MinimizeEncoded(), and TestMakeSymbolsSame().

460  {
461  IdentityFunction<typename Arc::Label> f;
462  return PrecedingInputSymbolsAreSameClass(start_is_epsilon, fst, f);
463 }
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
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...

◆ PrecedingInputSymbolsAreSameClass()

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 MinimizeEncoded(), 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
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21

◆ PreDeterminize()

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)
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21
struct rnnlm::@11::@12 n
Arc::StateId CreateSuperFinal(MutableFst< Arc > *fst)
#define KALDI_ERR
Definition: kaldi-error.h:126
fst::StdArc::Label Label
fst::StdArc::Weight Weight
vector< T > * InsertMember(const vector< T > m, vector< vector< T > *> *S)
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:168
#define KALDI_VLOG(v)
Definition: kaldi-error.h:135
void CopySetToVector(const std::set< T > s, vector< T > *v)

◆ PrepareForGrammarFst()

void PrepareForGrammarFst ( int32  nonterm_phones_offset,
VectorFst< StdArc > *  fst 
)

This function prepares 'ifst' for use in GrammarFst: it ensures that it has the expected properties, changing it slightly as needed.

'ifst' is expected to be a fully compiled HCLG graph that is intended to be used in GrammarFst. The user will most likely want to copy it to the ConstFst type after calling this function.

The following describes what this function does, and the reasons why it has to do these things:

  • To keep the ArcIterator code simple (to avoid branches in loops), even for expanded states we store the destination fst-instance index separately per state, not per arc. This requires that any transitions across FST boundaries from a single FST must be to a single destination FST (for a given source state). We fix this problem by introducing epsilon arcs and new states whenever we find a state that would cause a problem for the above.
  • In order to signal to the GrammarFst code that a particular state has cross-FST-boundary transitions, we set the final-prob to a nonzero value on that state. Specifically, we use a weight with Value() == 4096.0. When the GrammarFst code sees that value it knows that it was not a 'real' final-prob. Prior to doing this we ensure, by adding epsilon transitions as needed, that the state did not previously have a final-prob.
  • For arcs that are final arcs in an FST that represents a nonterminal (these arcs would have #nonterm_exit on them), we ensure that the states that they transition to have unit final-prob (i.e. final-prob equal to One()), by incorporating any final-prob into the arc itself. This avoids the GrammarFst code having to inspect those final-probs when expanding states.
Parameters
[in]nonterm_phones_offsetThe integer id of the symbols #nonterm_bos in the phones.txt file.
[in,out]fstThe FST to be (slightly) modified.

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

References GrammarFstPreparer::Prepare().

Referenced by main().

862  {
863  GrammarFstPreparer p(nonterm_phones_offset, fst);
864  p.Prepare();
865 }
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21

◆ Print()

void fst::Print ( const Fst< Arc > &  fst,
std::string  message 
)

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

Referenced by TransitionModel::GetPhones(), NnetDiscriminativeStats::NnetDiscriminativeStats(), DiscriminativeObjectiveInfo::PrintAll(), SplitExampleStats::SplitExampleStats(), and GeneralDescriptor::~GeneralDescriptor().

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 }
For an extended explanation of the framework of which grammar-fsts are a part, please see Support for...
Definition: graph.dox:21

◆ PrintProxyFstPath()

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;