fst Namespace Reference

For optional argument declarations. More...

Namespaces
namespace	internal
	Private helper functions for Push.
namespace	script
Classes
class	DefaultAccumulator
	This class accumulates arc weights using the semiring Plus(). More...
class	LogAccumulator
class	FastLogAccumulatorData
	Stores shareable data for fast log accumulator copies. More...
class	FastLogAccumulator
class	CacheLogAccumulatorData
class	CacheLogAccumulator
class	ReplaceAccumulatorData
	Stores shareable data for replace accumulator copies. More...
class	ReplaceAccumulator
class	NullAddOn
	Nothing to save. More...
class	AddOnPair
	Create a new add-on from a pair of add-ons. More...
class	AddOnImpl
class	ArcTpl
class	StringArc
	Arc with integer labels and state Ids and string weights. More...
struct	GallicArc
struct	ReverseArc
	Arc with the reverse of the weight found in its template arg. More...
struct	LexicographicArc
	Arc with integer labels and state Ids and lexicographic weights. More...
struct	ProductArc
	Arc with integer labels and state Ids and product weights. More...
struct	PowerArc
struct	SparsePowerArc
struct	ExpectationArc
class	AnyArcFilter
	True for all arcs. More...
class	EpsilonArcFilter
	True for (input/output) epsilon arcs. More...
class	InputEpsilonArcFilter
	True for input epsilon arcs. More...
class	OutputEpsilonArcFilter
	True for output epsilon arcs. More...
class	MultiLabelArcFilter
class	ArcMergeCompare
class	ArcMergeEqual
class	ArcSortFstImpl
	Implementation of delayed ArcSortFst. More...
class	ArcSortFst
class	ArcIterator< ArcSortFst< A, C > >
	Specialization for ArcSortFst. More...
class	ILabelCompare
	Compare class for comparing input labels of arcs. More...
class	OLabelCompare
	Compare class for comparing output labels of arcs. More...
class	StdArcSortFst
	Useful aliases when using StdArc. More...
class	ArcSumCompare
class	ArcSumEqual
struct	CacheOptions
class	CacheBaseImpl
struct	CacheState
class	CacheImpl
	A CacheBaseImpl with a commonly used CacheState. More...
class	CacheStateIterator
class	CacheArcIterator
struct	ClosureFstOptions
class	ClosureFst
class	StateIterator< ClosureFst< A > >
	Specialization for ClosureFst. More...
class	ArcIterator< ClosureFst< A > >
	Specialization for ClosureFst. More...
struct	CompactFstOptions
class	CompactFstData
class	CompactFstImpl
class	CompactFst
class	StateIterator< CompactFst< A, C, U > >
class	ArcIterator< CompactFst< A, C, U > >
class	StringCompactor
	bool Done() const { return pos_ >= num_arcs_; } More...
class	WeightedStringCompactor
	Compactor for weighted string FSTs. More...
class	UnweightedAcceptorCompactor
	Compactor for unweighted acceptor FSTs. More...
class	AcceptorCompactor
	Compactor for weighted acceptor FSTs. More...
class	UnweightedCompactor
	Compactor for unweighted FSTs. More...
class	CheckSummer
	Check sums. More...
class	ComplementFstImpl
class	ComplementFst
class	StateIterator< ComplementFst< A > >
	Specialization for ComplementFst. More...
class	ArcIterator< ComplementFst< A > >
	Specialization for ComplementFst. More...
class	IntegerFilterState
	Filter state that is a signed integral type. More...
class	WeightFilterState
	Filter state that is a weight (class). More...
class	PairFilterState
	Filter state that is the combination of two filter states. More...
class	SequenceComposeFilter
	This filter requires epsilons on FST1 to be read before epsilons on FST2. More...
class	AltSequenceComposeFilter
	This filter requires epsilons on FST2 to be read before epsilons on FST1. More...
class	MatchComposeFilter
class	MultiEpsFilter
struct	ComposeFstOptions
struct	ComposeFstImplOptions
class	ComposeFstImplBase
class	ComposeFstImpl
class	ComposeFst
class	StateIterator< ComposeFst< A > >
	Specialization for ComposeFst. More...
class	ArcIterator< ComposeFst< A > >
	Specialization for ComposeFst. More...
struct	ComposeOptions
class	ConcatFst
class	StateIterator< ConcatFst< A > >
	Specialization for ConcatFst. More...
class	ArcIterator< ConcatFst< A > >
	Specialization for ConcatFst. More...
class	CcVisitor
	Finds and returns connected components. Use with Visit(). More...
class	SccVisitor
class	ConstFstImpl
class	ConstFst
class	StateIterator< ConstFst< A, U > >
class	ArcIterator< ConstFst< A, U > >
class	DefaultCommonDivisor
	The default common divisor uses the semiring Plus. More...
class	LabelCommonDivisor
class	GallicCommonDivisor
struct	DeterminizeFstOptions
	Options for finite-state transducer determinization. More...
class	DeterminizeFstImplBase
class	DeterminizeFsaImpl
class	DeterminizeFstImpl
class	DeterminizeFst
class	StateIterator< DeterminizeFst< A > >
	Specialization for DeterminizeFst. More...
class	ArcIterator< DeterminizeFst< A > >
	Specialization for DeterminizeFst. More...
struct	DeterminizeOptions
struct	DfsState
	An Fst state's DFS stack state. More...
struct	DifferenceFstOptions
class	DifferenceFst
class	StateIterator< DifferenceFst< A > >
	Specialization for DifferenceFst. More...
class	ArcIterator< DifferenceFst< A > >
	Specialization for DifferenceFst. More...
class	EditFstImpl
class	EditFst
	END EditFstImpl IMPLEMENTATION. More...
class	EncodeTable
class	EncodeMapper
class	EncodeFst
class	DecodeFst
class	StateIterator< EncodeFst< A > >
	Specialization for EncodeFst. More...
class	ArcIterator< EncodeFst< A > >
	Specialization for EncodeFst. More...
class	StateIterator< DecodeFst< A > >
	Specialization for DecodeFst. More...
class	ArcIterator< DecodeFst< A > >
	Specialization for DecodeFst. More...
struct	EquivalenceUtil
class	ExpandedFst
	A generic FST plus state count. More...
class	ImplToExpandedFst
class	ExpectationWeight
class	StringReader
class	FarHeader
	FST archive header class. More...
class	FarWriter
	This class creates an archive of FSTs. More...
class	FarReader
	This class iterates through an existing archive of FSTs. More...
class	FstWriter
class	STTableFarWriter
class	FstReader
class	STTableFarReader
struct	KeyInfo
class	STTableWriter
class	STTableReader
class	PdtComposeOptions
class	PdtComposeOptions< Arc, false >
struct	ExpandFstOptions
class	ExpandFstImpl
	Implementation class for ExpandFst. More...
class	ExpandFst
class	StateIterator< ExpandFst< A > >
	Specialization for ExpandFst. More...
class	ArcIterator< ExpandFst< A > >
	Specialization for ExpandFst. More...
class	PdtInfo
	Compute various information about PDTs, helper class for pdtinfo.cc. More...
class	PdtStack
struct	PdtStateTuple
	State tuple for PDT expansion. More...
class	PdtStateHash
	Hash function object for PDT state tuples. More...
class	PdtStateTable
	Tuple to PDT state bijection. More...
class	PdtBalanceData
	Store balancing parenthesis data for a PDT. More...
struct	ReplaceParenHash
	Hash to paren IDs. More...
struct	PdtShortestPathOptions
class	PdtShortestPathData
class	PdtShortestPath
struct	FactorWeightOptions
class	IdentityFactor
	Factor trivially. More...
class	StringFactor
	Factor a StringWeight w as 'ab' where 'a' is a label. More...
class	GallicFactor
	Factor a GallicWeight using StringFactor. More...
class	FactorWeightFstImpl
	Implementation class for FactorWeight. More...
class	FactorWeightFst
class	StateIterator< FactorWeightFst< A, F > >
	Specialization for FactorWeightFst. More...
class	ArcIterator< FactorWeightFst< A, F > >
	Specialization for FactorWeightFst. More...
class	FloatLimits
	numeric limits class More...
class	FloatWeightTpl
	weight class to be templated on floating-points types More...
class	TropicalWeightTpl
	Tropical semiring: (min, +, inf, 0). More...
class	LogWeightTpl
	Log semiring: (log(e^-x + e^y), +, inf, 0). More...
class	MinMaxWeightTpl
	MinMax semiring: (min, max, inf, -inf). More...
struct	FstReadOptions
struct	FstWriteOptions
class	FstHeader
class	Fst
class	StateIteratorBase
struct	StateIteratorData
	StateIterator initialization data. More...
class	StateIterator
class	ArcIteratorBase
struct	ArcIteratorData
	ArcIterator initialization data. More...
class	ArcIterator
class	FstImpl
class	ImplToFst
class	GenericRegister
class	GenericRegisterer
class	Heap
	A templated heap implementation that support in-place update of values. More...
struct	IntersectFstOptions
class	IntersectFst
class	StateIterator< IntersectFst< A > >
	Specialization for IntersectFst. More...
class	ArcIterator< IntersectFst< A > >
	Specialization for IntersectFst. More...
class	IntervalSet
struct	InvertMapper
	Mapper to implement inversion of an arc. More...
class	InvertFst
class	StateIterator< InvertFst< A > >
	Specialization for InvertFst. More...
class	ArcIterator< InvertFst< A > >
	Specialization for InvertFst. More...
class	LabelReachableData
	Stores shareable data for label reachable class copies. More...
class	LabelReachable
class	LexicographicWeight
class	Mutex
class	MutexLock
class	RefCounter
	Reference counting - single-thread implementation. More...
class	LookAheadSelector
class	LookAheadSelector< M, M, MT >
class	LookAheadSelector< M1, M2, MATCH_INPUT >
class	LookAheadSelector< M1, M2, MATCH_OUTPUT >
class	LookAheadComposeFilter
class	PushWeightsComposeFilter
class	PushLabelsComposeFilter
class	DefaultLookAhead
	MATCH_NONE. More...
class	DefaultLookAhead< A, MATCH_INPUT >
	Specializes for MATCH_INPUT to allow lookahead. More...
class	DefaultLookAhead< A, MATCH_OUTPUT >
	Specializes for MATCH_OUTPUT to allow lookahead. More...
class	DefaultLookAhead< StdArc, MATCH_INPUT >
	Specializes for StdArc to allow weight and label pushing. More...
class	DefaultLookAhead< StdArc, MATCH_OUTPUT >
	Specializes for StdArc to allow weight and label pushing. More...
class	DefaultLookAhead< LogArc, MATCH_INPUT >
	Specializes for LogArc to allow weight and label pushing. More...
class	DefaultLookAhead< LogArc, MATCH_OUTPUT >
	Specializes for LogArc to allow weight and label pushing. More...
class	LookAheadMatcherBase
class	TrivialLookAheadMatcher
	Don't really lookahead, just declare future looks good regardless. More...
class	ArcLookAheadMatcher
class	LabelLookAheadMatcher
class	LabelLookAheadRelabeler
	Label-lookahead relabeling class. More...
class	LookAheadMatcher
struct	MapFstOptions
class	MapFstImpl
	Implementation of delayed MapFst. More...
class	MapFst
class	StateIterator< MapFst< A, B, C > >
	Specialization for MapFst. More...
class	ArcIterator< MapFst< A, B, C > >
	Specialization for MapFst. More...
struct	IdentityMapper
	Mapper that returns its input. More...
struct	SuperFinalMapper
struct	WeightConvertMapper
struct	ToGallicMapper
	Mapper from A to GallicArc. More...
struct	FromGallicMapper
	Mapper from GallicArc to A. More...
struct	GallicToNewSymbolsMapper
	Mapper from GallicArc to A. More...
struct	PlusMapper
	Mapper to add a constant to all weights. More...
struct	TimesMapper
	Mapper to (right) multiply a constant to all weights. More...
struct	InvertWeightMapper
	Mapper to reciprocate all non-Zero() weights. More...
struct	RmWeightMapper
	Mapper to map all non-Zero() weights to One(). More...
struct	QuantizeMapper
	Mapper to quantize all weights. More...
struct	ReverseWeightMapper
class	NullMatcherFstInit
	Default MatcherFst initializer - does nothing. More...
class	MatcherFst
class	StateIterator< MatcherFst< F, M, N, I > >
	Specialization fo MatcherFst. More...
class	ArcIterator< MatcherFst< F, M, N, I > >
	Specialization for MatcherFst. More...
class	Matcher< MatcherFst< F, M, N, I > >
	Specialization for MatcherFst. More...
class	LookAheadMatcher< MatcherFst< F, M, N, I > >
	Specialization for MatcherFst. More...
class	MatcherBase
class	SortedMatcher
class	RhoMatcher
class	SigmaMatcher
class	PhiMatcher
class	MultiEpsMatcher
class	Matcher
class	StateComparator
class	CyclicMinimizer
class	AcyclicMinimizer
class	MutableFst
	An expanded FST plus mutators (use MutableArcIterator to modify arcs). More...
class	MutableArcIteratorBase
struct	MutableArcIteratorData
class	MutableArcIterator
class	ImplToMutableFst
class	PairWeight
class	Partition
	Defines a partitioning of states. Typically used to represent equivalence classes for Fst operations like minimization. More...
class	PartitionIterator
	iterate over members of a class in a partition More...
class	PowerWeight
class	ProductWeight
	Product semiring: W1 * W2. More...
class	ProjectMapper
	Mapper to implement projection per arc. More...
class	ProjectFst
class	StateIterator< ProjectFst< A > >
	Specialization for ProjectFst. More...
class	ArcIterator< ProjectFst< A > >
	Specialization for ProjectFst. More...
class	PruneOptions
class	PruneCompare
class	QueueBase
class	TrivialQueue
class	FifoQueue
	First-in, first-out queue discipline, templated on the StateId. More...
class	LifoQueue
	Last-in, first-out queue discipline, templated on the StateId. More...
class	ShortestFirstQueue
class	StateWeightCompare
class	NaturalShortestFirstQueue
class	TopOrderQueue
class	StateOrderQueue
class	SccQueue
class	AutoQueue
struct	TrivialAStarEstimate
class	AStarWeightCompare
class	NaturalAStarQueue
struct	TrivialStateEquivClass
class	PruneQueue
class	NaturalPruneQueue
struct	UniformArcSelector
	Randomly selects a transition using the uniform distribution. More...
struct	LogProbArcSelector
struct	FastLogProbArcSelector
struct	RandGenOptions
	Options for random path generation. More...
class	TropicalWeightGenerator_
class	LogWeightGenerator_
class	MinMaxWeightGenerator_
class	StringWeightGenerator
class	ProductWeightGenerator
class	LexicographicWeightGenerator
class	GallicWeightGenerator
class	PowerWeightGenerator
class	SignedLogWeightGenerator_
class	SparsePowerWeightGenerator
class	RationalFstImpl
	Implementation class for delayed unions, concatenations and closures. More...
class	RationalFst
class	StateIterator< RationalFst< A > >
	Specialization for RationalFst. More...
class	ArcIterator< RationalFst< A > >
	Specialization for RationalFst. More...
struct	FstRegisterEntry
	This class represents a single entry in a FstRegister. More...
class	FstRegister
class	FstRegisterer
class	RelabelFstImpl
	Implementation for delayed relabeling. More...
class	RelabelFst
	Delayed implementation of arc relabeling. More...
class	StateIterator< RelabelFst< A > >
	Specialization for RelabelFst. More...
class	ArcIterator< RelabelFst< A > >
	Specialization for RelabelFst. More...
class	ReplaceUtil
struct	ReplaceStateTuple
	Tuple of information that uniquely defines a state in replace. More...
class	ReplaceRootSelector
class	ReplaceFingerprint
class	ReplaceFstStateFingerprint
class	ReplaceHash
class	VectorHashReplaceStateTable
class	DefaultReplaceStateTable
struct	ReplaceFstOptions
class	ReplaceFstImpl
	Implementation class for replace class Fst. More...
class	ReplaceFst
	Recursivively replaces arcs in the root Fst with other Fsts. This version is a delayed Fst. More...
class	StateIterator< ReplaceFst< A, T > >
	Specialization for ReplaceFst. More...
class	ArcIterator< ReplaceFst< A, T > >
class	RmEpsilonOptions
class	RmEpsilonState
	Computation state of the epsilon-removal algorithm. More...
struct	RmEpsilonFstOptions
class	RmEpsilonFstImpl
	Implementation of delayed RmEpsilonFst. More...
class	RmEpsilonFst
class	StateIterator< RmEpsilonFst< A > >
	Specialization for RmEpsilonFst. More...
class	ArcIterator< RmEpsilonFst< A > >
	Specialization for RmEpsilonFst. More...
class	FstCompiler
class	FstDrawer
class	FstInfo
class	FstPrinter
struct	ShortestDistanceOptions
class	ShortestDistanceState
struct	ShortestPathOptions
class	ShortestPathCompare
class	SignedLogWeightTpl
struct	SparseTupleWeightPlusMapper
struct	SparseTupleWeightTimesMapper
struct	SparseTupleWeightDivideMapper
struct	SparseTupleWeightApproxMapper
class	SparsePowerWeight
class	SparseTupleWeight
class	SparseTupleWeightIterator
class	IntervalReachVisitor
class	StateReachable
class	HashStateTable
class	CompactHashStateTable
class	VectorStateTable
class	ErasableStateTable
class	VectorHashStateTable
struct	ComposeStateTuple
	Represents the composition state. More...
class	ComposeHash
	Hashing of composition state tuples. More...
class	GenericComposeStateTable
	A HashStateTable over composition tuples. More...
class	ComposeFingerprint
	Fingerprint for general composition tuples. More...
class	ComposeState1Fingerprint
	Useful when the first composition state determines the tuple. More...
class	ComposeState2Fingerprint
	Useful when the second composition state determines the tuple. More...
class	ProductComposeStateTable
class	StringDetComposeStateTable
class	DetStringComposeStateTable
class	ErasableComposeStateTable
class	StringWeight
	String semiring: (longest_common_prefix/suffix, ., Infinity, Epsilon). More...
class	StringWeightIterator
	Traverses string in forward direction. More...
class	StringWeightReverseIterator
	Traverses string in forward direction. More...
struct	GallicWeight
	Product of string weight and an arbitray weight. More...
class	StringCompiler
	Functor compiling a string in an FST. More...
class	StringPrinter
	Functor to print a string FST as a string. More...
struct	SymbolTableReadOptions
class	SymbolTableImpl
class	SymbolTable
	Symbol (string) to int and reverse mapping. More...
class	SymbolTableIterator
	Iterator class for symbols in a symbol table. More...
class	SynchronizeFstImpl
	Implementation class for SynchronizeFst. More...
class	SynchronizeFst
class	StateIterator< SynchronizeFst< A > >
	Specialization for SynchronizeFst. More...
class	ArcIterator< SynchronizeFst< A > >
	Specialization for SynchronizeFst. More...
class	TopOrderVisitor
	DFS visitor class to return topological ordering. More...
class	TupleWeight
	n-tuple weight, element of the n-th catersian power of W More...
class	UnionFind
class	UnionFst
class	StateIterator< UnionFst< A > >
	Specialization for UnionFst. More...
class	ArcIterator< UnionFst< A > >
	Specialization for UnionFst. More...
class	CompactSet
class	VectorFstBaseImpl
struct	VectorState
	Arcs implemented by an STL vector per state. More...
class	VectorFstImpl
class	WeightFromString
	Converts a string into a weight. More...
class	VectorFst
class	StateIterator< VectorFst< A > >
class	ArcIterator< VectorFst< A > >
class	MutableArcIterator< VectorFst< A > >
class	CopyVisitor
	Copies input FST to mutable FST following queue order. More...
class	PartialVisitor
	Visits input FST up to a state limit following queue order. More...
class	NaturalLess
class	EpsMapper
class	WeightedTester
class	UnweightedTester
class	UnweightedTester< StdArc >
class	AlgoTester
class	FstTester
struct	CustomArc
	A user-defined arc type. More...
class	CustomCompactor
	A user-defined compactor for test FST. More...
class	WeightTester
Typedefs
typedef ArcTpl< TropicalWeight >	StdArc
typedef ArcTpl< LogWeight >	LogArc
typedef ArcTpl< SignedLogWeight >	SignedLogArc
typedef ArcTpl< MinMaxWeight >	MinMaxArc
typedef CacheOptions	ArcSortFstOptions
typedef ILabelCompare< StdArc >	StdILabelCompare
typedef OLabelCompare< StdArc >	StdOLabelCompare
typedef ClosureFst< StdArc >	StdClosureFst
	Useful alias when using StdArc.
typedef CompactFst< StdArc, StringCompactor< StdArc > >	StdCompactStringFst
	Uselful aliases when using StdArc.
typedef CompactFst< StdArc, WeightedStringCompactor < StdArc > >	StdCompactWeightedStringFst
typedef CompactFst< StdArc, AcceptorCompactor< StdArc > >	StdCompactAcceptorFst
typedef CompactFst< StdArc, UnweightedCompactor< StdArc > >	StdCompactUnweightedFst
typedef CompactFst< StdArc, UnweightedAcceptorCompactor < StdArc > >	StdCompactUnweightedAcceptorFst
typedef ComplementFst< StdArc >	StdComplementFst
	Useful alias when using StdArc.
typedef IntegerFilterState < signed char >	CharFilterState
typedef IntegerFilterState< short >	ShortFilterState
typedef IntegerFilterState< int >	IntFilterState
typedef ComposeFst< StdArc >	StdComposeFst
	Useful alias when using StdArc.
typedef RationalFstOptions	ConcatFstOptions
typedef ConcatFst< StdArc >	StdConcatFst
	Useful alias when using StdArc.
typedef ConstFst< StdArc >	StdConstFst
	A useful alias when using StdArc.
typedef DeterminizeFst< StdArc >	StdDeterminizeFst
	Useful aliases when using StdArc.
typedef DifferenceFst< StdArc >	StdDifferenceFst
	Useful alias when using StdArc.
typedef ComposeOptions	DifferenceOptions
typedef EncodeFst< StdArc >	StdEncodeFst
	Useful aliases when using StdArc.
typedef DecodeFst< StdArc >	StdDecodeFst
typedef ExpandedFst< StdArc >	StdExpandedFst
	A useful alias when using StdArc.
typedef FloatWeightTpl< float >	FloatWeight
	Single precision FloatWeight.
typedef TropicalWeightTpl< float >	TropicalWeight
	Single precision TropicalWeight.
typedef LogWeightTpl< float >	LogWeight
	Single precision LogWeight.
typedef MinMaxWeightTpl< float >	MinMaxWeight
	Single precision MinMaxWeight.
typedef Fst< StdArc >	StdFst
	namespace internal
typedef MutableFst< StdArc >	StdMutableFst
	A useful alias when using StdArc.
typedef VectorFst< StdArc >	StdVectorFst
	A useful alias when using StdArc.
typedef IntersectFst< StdArc >	StdIntersectFst
	Useful alias when using StdArc.
typedef InvertFst< StdArc >	StdInvertFst
	Useful alias when using StdArc.
typedef ProjectFst< StdArc >	StdProjectFst
	Useful alias when using StdArc.
typedef RelabelFst< StdArc >	StdRelabelFst
	Useful alias when using StdArc.
typedef ReplaceFst< StdArc, DefaultReplaceStateTable < StdArc, ssize_t > >	StdReplaceFst
typedef RmEpsilonFst< StdArc >	StdRmEpsilonFst
	Useful alias when using StdArc.
typedef UnionFst< StdArc >	StdUnionFst
	Useful alias when using StdArc.
typedef ComposeOptions	IntersectOptions
typedef int	FstOnceType
typedef WeightConvertMapper < StdArc, LogArc >	StdToLogMapper
	Consider using more efficient Cast (fst.h) instead.
typedef WeightConvertMapper < LogArc, StdArc >	LogToStdMapper
typedef MatcherFst< ConstFst < StdArc > , ArcLookAheadMatcher < SortedMatcher< ConstFst < StdArc > > >, arc_lookahead_fst_type >	StdArcLookAheadFst
typedef MatcherFst< ConstFst < LogArc > , ArcLookAheadMatcher < SortedMatcher< ConstFst < LogArc > > >, arc_lookahead_fst_type >	LogArcLookAheadFst
typedef MatcherFst< ConstFst < StdArc > , LabelLookAheadMatcher < SortedMatcher< ConstFst < StdArc > >, ilabel_lookahead_flags, FastLogAccumulator< StdArc > >, ilabel_lookahead_fst_type, LabelLookAheadRelabeler < StdArc > >	StdILabelLookAheadFst
typedef MatcherFst< ConstFst < LogArc > , LabelLookAheadMatcher < SortedMatcher< ConstFst < LogArc > >, ilabel_lookahead_flags, FastLogAccumulator< LogArc > >, ilabel_lookahead_fst_type, LabelLookAheadRelabeler < LogArc > >	LogILabelLookAheadFst
typedef MatcherFst< ConstFst < StdArc > , LabelLookAheadMatcher < SortedMatcher< ConstFst < StdArc > >, olabel_lookahead_flags, FastLogAccumulator< StdArc > >, olabel_lookahead_fst_type, LabelLookAheadRelabeler < StdArc > >	StdOLabelLookAheadFst
typedef MatcherFst< ConstFst < LogArc > , LabelLookAheadMatcher < SortedMatcher< ConstFst < LogArc > >, olabel_lookahead_flags, FastLogAccumulator< LogArc > >, olabel_lookahead_fst_type, LabelLookAheadRelabeler < LogArc > >	LogOLabelLookAheadFst
typedef LogProbArcSelector < StdArc >	StdArcSelector
	Convenience definitions.
typedef LogProbArcSelector < LogArc >	LogArcSelector
typedef TropicalWeightGenerator_ < float >	TropicalWeightGenerator
typedef LogWeightGenerator_ < float >	LogWeightGenerator
typedef MinMaxWeightGenerator_ < float >	MinMaxWeightGenerator
typedef SignedLogWeightGenerator_ < float >	SignedLogWeightGenerator
typedef CacheOptions	RationalFstOptions
typedef CacheOptions	RelabelFstOptions
typedef SignedLogWeightTpl< float >	SignedLogWeight
typedef CacheOptions	SynchronizeFstOptions
typedef RationalFstOptions	UnionFstOptions
Enumerations
enum	ComposeFilter { AUTO_FILTER, SEQUENCE_FILTER, ALT_SEQUENCE_FILTER, MATCH_FILTER }
enum	EncodeType { ENCODE = 1, DECODE = 2 }
enum	EpsNormalizeType { EPS_NORM_INPUT, EPS_NORM_OUTPUT }
enum	FarEntryType { FET_LINE, FET_FILE }
enum	FarTokenType { FTT_SYMBOL, FTT_BYTE, FTT_UTF8 }
enum	FarType { FAR_DEFAULT = 0, FAR_STTABLE = 1, FAR_SSTABLE = 2 }
enum	MatchType {   MATCH_INPUT, MATCH_OUTPUT, MATCH_BOTH, MATCH_NONE,   MATCH_UNKNOWN }
	Specifies matcher action. More...
enum	MapFinalAction { MAP_NO_SUPERFINAL, MAP_ALLOW_SUPERFINAL, MAP_REQUIRE_SUPERFINAL }
	This determines how final weights are mapped. More...
enum	MapSymbolsAction { MAP_CLEAR_SYMBOLS, MAP_COPY_SYMBOLS, MAP_NOOP_SYMBOLS }
	This determines how symbol tables are mapped. More...
enum	MapType {   IDENTITY_MAPPER, INVERT_MAPPER, PLUS_MAPPER, QUANTIZE_MAPPER,   RMWEIGHT_MAPPER, SUPERFINAL_MAPPER, TIMES_MAPPER }
	Convenience function for mapping with one of several predefined map types. More...
enum	MatcherRewriteMode { MATCHER_REWRITE_AUTO = 0, MATCHER_REWRITE_ALWAYS, MATCHER_REWRITE_NEVER }
	Specifies whether during matching we rewrite both the input and output sides. More...
enum	ProjectType { PROJECT_INPUT = 1, PROJECT_OUTPUT = 2 }
	This specifies whether to project on input or output. More...
enum	QueueType {   TRIVIAL_QUEUE = 0, FIFO_QUEUE = 1, LIFO_QUEUE = 2, SHORTEST_FIRST_QUEUE = 3,   TOP_ORDER_QUEUE = 4, STATE_ORDER_QUEUE = 5, SCC_QUEUE = 6, AUTO_QUEUE = 7,   OTHER_QUEUE = 8 }
	State queue types. More...
enum	ClosureType { CLOSURE_STAR = 0, CLOSURE_PLUS = 1 }
	This specifies whether to add the empty string. More...
enum	ReweightType { REWEIGHT_TO_INITIAL, REWEIGHT_TO_FINAL }
enum	StringType { STRING_LEFT = 0, STRING_RIGHT = 1, STRING_LEFT_RESTRICT = 2, STRING_RIGHT_RESTRICT }
enum	DivideType { DIVIDE_LEFT, DIVIDE_RIGHT, DIVIDE_ANY }
	Determines direction of division. More...
Functions
int	KeySize (const char *filename)
FarType	FarTypeFromString (const string &str)
	Return the 'FarType' value corresponding to a far type name.
string	FarTypeToString (FarType type)
	Return the textual name corresponding to a 'FarType;.
FarEntryType	StringToFarEntryType (const string &s)
FarTokenType	StringToFarTokenType (const string &s)
string	LoadArcTypeFromFar (const string &far_fname)
string	LoadArcTypeFromFst (const string &fst_fname)
bool	IsSTTable (const string &filename)
template<class A >
void	ArcMerge (MutableFst< A > *fst)
template<class Arc , class Compare >
void	ArcSort (MutableFst< Arc > *fst, Compare comp)
template<class A >
void	ArcSum (MutableFst< A > *fst)
template<class Arc >
void	Closure (MutableFst< Arc > *fst, ClosureType closure_type)
template<class Arc >
void	Closure (RationalFst< Arc > *fst, ClosureType closure_type)
template<class F , class G >
void	Cast (const F &, G *)
void	SplitToVector (char *line, const char *delim, std::vector< char * > *vec, bool omit_empty_strings)
template<typename To , typename From >
To	down_cast (From *f)
	Downcasting.
template<class Dest , class Source >
Dest	bit_cast (const Source &source)
	Bitcasting.
template<class Label >
bool	UTF8StringToLabels (const string &, std::vector< Label > *)
template<class Label >
bool	LabelsToUTF8String (const std::vector< Label > &, string *)
template<class Arc >
void	Compose (const Fst< Arc > &ifst1, const Fst< Arc > &ifst2, MutableFst< Arc > *ofst, const ComposeOptions &opts=ComposeOptions())
template<class Arc >
void	Concat (MutableFst< Arc > *fst1, const Fst< Arc > &fst2)
template<class Arc >
void	Concat (const Fst< Arc > &fst1, MutableFst< Arc > *fst2)
template<class Arc >
void	Concat (RationalFst< Arc > *fst1, const Fst< Arc > &fst2)
template<class Arc >
void	Concat (const Fst< Arc > &fst1, RationalFst< Arc > *fst2)
template<class Arc >
void	Connect (MutableFst< Arc > *fst)
template<class Arc >
void	Determinize (const Fst< Arc > &ifst, MutableFst< Arc > *ofst, const DeterminizeOptions< Arc > &opts=DeterminizeOptions< Arc >())
template<class Arc , class V , class ArcFilter >
void	DfsVisit (const Fst< Arc > &fst, V *visitor, ArcFilter filter)
template<class Arc , class V >
void	DfsVisit (const Fst< Arc > &fst, V *visitor)
template<class Arc >
void	Difference (const Fst< Arc > &ifst1, const Fst< Arc > &ifst2, MutableFst< Arc > *ofst, const DifferenceOptions &opts=DifferenceOptions())
template<class A >
void	Encode (MutableFst< A > *fst, EncodeMapper< A > *mapper)
	Complexity: O(nstates + narcs).
template<class A >
void	Decode (MutableFst< A > *fst, const EncodeMapper< A > &mapper)
template<class Arc >
void	EpsNormalize (const Fst< Arc > &ifst, MutableFst< Arc > *ofst, EpsNormalizeType type=EPS_NORM_INPUT)
template<class Arc >
bool	Equal (const Fst< Arc > &fst1, const Fst< Arc > &fst2, float delta=kDelta)
	Tests if two Fsts have the same states and arcs in the same order.
template<class Arc >
bool	Equivalent (const Fst< Arc > &fst1, const Fst< Arc > &fst2, double delta=kDelta)
template<class A >
A::Weight	Final (const ExpandedFst< A > &fst, typename A::StateId s)
	ExpandedFst case - abstract methods.
template<class A >
ssize_t	NumArcs (const ExpandedFst< A > &fst, typename A::StateId s)
template<class A >
ssize_t	NumInputEpsilons (const ExpandedFst< A > &fst, typename A::StateId s)
template<class A >
ssize_t	NumOutputEpsilons (const ExpandedFst< A > &fst, typename A::StateId s)
template<class Arc >
Arc::StateId	CountStates (const Fst< Arc > &fst)
template<class X1 , class X2 >
ExpectationWeight< X1, X2 >	Plus (const ExpectationWeight< X1, X2 > &w, const ExpectationWeight< X1, X2 > &v)
template<class X1 , class X2 >
ExpectationWeight< X1, X2 >	Times (const ExpectationWeight< X1, X2 > &w, const ExpectationWeight< X1, X2 > &v)
template<class X1 , class X2 >
ExpectationWeight< X1, X2 >	Divide (const ExpectationWeight< X1, X2 > &w, const ExpectationWeight< X1, X2 > &v, DivideType typ=DIVIDE_ANY)
template<class Arc >
void	FarCompileStrings (const vector< string > &in_fnames, const string &out_fname, const string &fst_type, const FarType &far_type, int32 generate_keys, FarEntryType fet, FarTokenType tt, const string &symbols_fname, bool allow_negative_labels, bool file_list_input, const string &key_prefix, const string &key_suffix)
template<class Arc >
void	FarCreate (const vector< string > &in_fnames, const string &out_fname, const int32 generate_keys, const bool file_list_input, const FarType &far_type, const string &key_prefix, const string &key_suffix)
template<class Arc >
void	FarExtract (const vector< string > &ifilenames, const int32 &generate_filenames, const string &begin_key, const string &end_key, const string &filename_prefix, const string &filename_suffix)
template<class Arc >
void	CountStatesAndArcs (const Fst< Arc > &fst, size_t *nstate, size_t *narc)
template<class Arc >
void	FarInfo (const vector< string > &filenames, const string &begin_key, const string &end_key, const bool list_fsts)
template<class Arc >
void	FarPrintStrings (const vector< string > &ifilenames, const FarEntryType entry_type, const FarTokenType far_token_type, const string &begin_key, const string &end_key, const bool print_key, const string &symbols_fname, const int32 generate_filenames, const string &filename_prefix, const string &filename_suffix)
template<class H >
bool	ReadSTTableHeader (const string &filename, H *header)
template<class Arc >
void	Compose (const Fst< Arc > &ifst1, const vector< pair< typename Arc::Label, typename Arc::Label > > &parens, const Fst< Arc > &ifst2, MutableFst< Arc > *ofst, const ComposeOptions &opts=ComposeOptions())
template<class Arc >
void	Compose (const Fst< Arc > &ifst1, const Fst< Arc > &ifst2, const vector< pair< typename Arc::Label, typename Arc::Label > > &parens, MutableFst< Arc > *ofst, const ComposeOptions &opts=ComposeOptions())
uint64	ExpandProperties (uint64 inprops)
	Properties for an expanded PDT.
template<class Arc >
void	Expand (const Fst< Arc > &ifst, const vector< pair< typename Arc::Label, typename Arc::Label > > &parens, MutableFst< Arc > *ofst, bool connect=true, bool keep_parentheses=false)
template<class A >
void	PrintPdtInfo (const PdtInfo< A > &pdtinfo)
template<typename S , typename K >
bool	operator== (const PdtStateTuple< S, K > &x, const PdtStateTuple< S, K > &y)
	Equality of PDT state tuples.
template<class Arc >
void	Replace (const vector< pair< typename Arc::Label, const Fst< Arc > * > > &ifst_array, MutableFst< Arc > *ofst, vector< pair< typename Arc::Label, typename Arc::Label > > *parens, typename Arc::Label root)
template<class Arc , class RevArc >
void	Reverse (const Fst< Arc > &ifst, const vector< pair< typename Arc::Label, typename Arc::Label > > &parens, MutableFst< RevArc > *ofst)
	Reverses a pushdown transducer (PDT) encoded as an FST.
template<class Arc , class Queue >
void	ShortestPath (const Fst< Arc > &ifst, const vector< pair< typename Arc::Label, typename Arc::Label > > &parens, MutableFst< Arc > *ofst, const PdtShortestPathOptions< Arc, Queue > &opts)
template<class Arc >
void	ShortestPath (const Fst< Arc > &ifst, const vector< pair< typename Arc::Label, typename Arc::Label > > &parens, MutableFst< Arc > *ofst)
template<class T >
bool	operator== (const FloatWeightTpl< T > &w1, const FloatWeightTpl< T > &w2)
bool	operator== (const FloatWeightTpl< double > &w1, const FloatWeightTpl< double > &w2)
bool	operator== (const FloatWeightTpl< float > &w1, const FloatWeightTpl< float > &w2)
template<class T >
bool	operator!= (const FloatWeightTpl< T > &w1, const FloatWeightTpl< T > &w2)
bool	operator!= (const FloatWeightTpl< double > &w1, const FloatWeightTpl< double > &w2)
bool	operator!= (const FloatWeightTpl< float > &w1, const FloatWeightTpl< float > &w2)
template<class T >
bool	ApproxEqual (const FloatWeightTpl< T > &w1, const FloatWeightTpl< T > &w2, float delta=kDelta)
template<class T >
ostream &	operator<< (ostream &strm, const FloatWeightTpl< T > &w)
template<class T >
istream &	operator>> (istream &strm, FloatWeightTpl< T > &w)
template<class T >
TropicalWeightTpl< T >	Plus (const TropicalWeightTpl< T > &w1, const TropicalWeightTpl< T > &w2)
TropicalWeightTpl< float >	Plus (const TropicalWeightTpl< float > &w1, const TropicalWeightTpl< float > &w2)
TropicalWeightTpl< double >	Plus (const TropicalWeightTpl< double > &w1, const TropicalWeightTpl< double > &w2)
template<class T >
TropicalWeightTpl< T >	Times (const TropicalWeightTpl< T > &w1, const TropicalWeightTpl< T > &w2)
TropicalWeightTpl< float >	Times (const TropicalWeightTpl< float > &w1, const TropicalWeightTpl< float > &w2)
TropicalWeightTpl< double >	Times (const TropicalWeightTpl< double > &w1, const TropicalWeightTpl< double > &w2)
template<class T >
TropicalWeightTpl< T >	Divide (const TropicalWeightTpl< T > &w1, const TropicalWeightTpl< T > &w2, DivideType typ=DIVIDE_ANY)
TropicalWeightTpl< float >	Divide (const TropicalWeightTpl< float > &w1, const TropicalWeightTpl< float > &w2, DivideType typ=DIVIDE_ANY)
TropicalWeightTpl< double >	Divide (const TropicalWeightTpl< double > &w1, const TropicalWeightTpl< double > &w2, DivideType typ=DIVIDE_ANY)
template<class T >
T	LogExp (T x)
template<class T >
LogWeightTpl< T >	Plus (const LogWeightTpl< T > &w1, const LogWeightTpl< T > &w2)
LogWeightTpl< float >	Plus (const LogWeightTpl< float > &w1, const LogWeightTpl< float > &w2)
LogWeightTpl< double >	Plus (const LogWeightTpl< double > &w1, const LogWeightTpl< double > &w2)
template<class T >
LogWeightTpl< T >	Times (const LogWeightTpl< T > &w1, const LogWeightTpl< T > &w2)
LogWeightTpl< float >	Times (const LogWeightTpl< float > &w1, const LogWeightTpl< float > &w2)
LogWeightTpl< double >	Times (const LogWeightTpl< double > &w1, const LogWeightTpl< double > &w2)
template<class T >
LogWeightTpl< T >	Divide (const LogWeightTpl< T > &w1, const LogWeightTpl< T > &w2, DivideType typ=DIVIDE_ANY)
LogWeightTpl< float >	Divide (const LogWeightTpl< float > &w1, const LogWeightTpl< float > &w2, DivideType typ=DIVIDE_ANY)
LogWeightTpl< double >	Divide (const LogWeightTpl< double > &w1, const LogWeightTpl< double > &w2, DivideType typ=DIVIDE_ANY)
template<class T >
MinMaxWeightTpl< T >	Plus (const MinMaxWeightTpl< T > &w1, const MinMaxWeightTpl< T > &w2)
	Min.
MinMaxWeightTpl< float >	Plus (const MinMaxWeightTpl< float > &w1, const MinMaxWeightTpl< float > &w2)
MinMaxWeightTpl< double >	Plus (const MinMaxWeightTpl< double > &w1, const MinMaxWeightTpl< double > &w2)
template<class T >
MinMaxWeightTpl< T >	Times (const MinMaxWeightTpl< T > &w1, const MinMaxWeightTpl< T > &w2)
	Max.
MinMaxWeightTpl< float >	Times (const MinMaxWeightTpl< float > &w1, const MinMaxWeightTpl< float > &w2)
MinMaxWeightTpl< double >	Times (const MinMaxWeightTpl< double > &w1, const MinMaxWeightTpl< double > &w2)
template<class T >
MinMaxWeightTpl< T >	Divide (const MinMaxWeightTpl< T > &w1, const MinMaxWeightTpl< T > &w2, DivideType typ=DIVIDE_ANY)
	Defined only for special cases.
MinMaxWeightTpl< float >	Divide (const MinMaxWeightTpl< float > &w1, const MinMaxWeightTpl< float > &w2, DivideType typ=DIVIDE_ANY)
MinMaxWeightTpl< double >	Divide (const MinMaxWeightTpl< double > &w1, const MinMaxWeightTpl< double > &w2, DivideType typ=DIVIDE_ANY)
bool	IsFstHeader (istream &, const string &)
template<class Arc >
uint64	TestProperties (const Fst< Arc > &fst, uint64 mask, uint64 *known)
template<class A >
void	FstToString (const Fst< A > &fst, string *result)
	Fst Serialization.
template<class A >
Fst< A > *	StringToFst (const string &s)
template<class Label >
bool	UTF8StringToLabels (const string &str, vector< Label > *labels)
template<class Label >
bool	LabelsToUTF8String (const vector< Label > &labels, string *str)
template<class Arc >
void	Intersect (const Fst< Arc > &ifst1, const Fst< Arc > &ifst2, MutableFst< Arc > *ofst, const IntersectOptions &opts=IntersectOptions())
template<typename T >
ostream &	operator<< (ostream &strm, const IntervalSet< T > &s)
template<class Arc >
void	Invert (MutableFst< Arc > *fst)
template<class W1 , class W2 >
LexicographicWeight< W1, W2 >	Plus (const LexicographicWeight< W1, W2 > &w, const LexicographicWeight< W1, W2 > &v)
template<class W1 , class W2 >
LexicographicWeight< W1, W2 >	Times (const LexicographicWeight< W1, W2 > &w, const LexicographicWeight< W1, W2 > &v)
template<class W1 , class W2 >
LexicographicWeight< W1, W2 >	Divide (const LexicographicWeight< W1, W2 > &w, const LexicographicWeight< W1, W2 > &v, DivideType typ=DIVIDE_ANY)
int	FstOnceInit (FstOnceType *once, void(*init)(void))
template<class M1 , class M2 >
MatchType	LookAheadMatchType (const M1 &m1, const M2 &m2)
template<class Arc >
MatchType	LookAheadMatchType (const Fst< Arc > &fst1, const Fst< Arc > &fst2)
template<class A , class C >
void	Map (MutableFst< A > *fst, C *mapper)
template<class A , class C >
void	Map (MutableFst< A > *fst, C mapper)
template<class A , class B , class C >
void	Map (const Fst< A > &ifst, MutableFst< B > *ofst, C *mapper)
template<class A , class B , class C >
void	Map (const Fst< A > &ifst, MutableFst< B > *ofst, C mapper)
template<class Arc >
void	Map (MutableFst< Arc > *ofst, MapType map_type, float delta=kDelta, typename Arc::Weight weight_thresh=Arc::Weight::Zero())
template<class A >
void	MergeStates (const Partition< typename A::StateId > &partition, MutableFst< A > *fst)
template<class A >
void	AcceptorMinimize (MutableFst< A > *fst)
template<class A >
void	Minimize (MutableFst< A > *fst, MutableFst< A > *sfst=0, float delta=kDelta)
template<class A >
A::Weight	Final (const MutableFst< A > &fst, typename A::StateId s)
	MutableFst case - abstract methods.
template<class A >
ssize_t	NumArcs (const MutableFst< A > &fst, typename A::StateId s)
template<class A >
ssize_t	NumInputEpsilons (const MutableFst< A > &fst, typename A::StateId s)
template<class A >
ssize_t	NumOutputEpsilons (const MutableFst< A > &fst, typename A::StateId s)
template<class W1 , class W2 >
istream &	operator>> (istream &strm, PairWeight< W1, W2 > &w)
template<class W1 , class W2 >
bool	operator== (const PairWeight< W1, W2 > &w, const PairWeight< W1, W2 > &v)
template<class W1 , class W2 >
bool	operator!= (const PairWeight< W1, W2 > &w1, const PairWeight< W1, W2 > &w2)
template<class W1 , class W2 >
bool	ApproxEqual (const PairWeight< W1, W2 > &w1, const PairWeight< W1, W2 > &w2, float delta=kDelta)
template<class W1 , class W2 >
ostream &	operator<< (ostream &strm, const PairWeight< W1, W2 > &w)
template<class W , unsigned int n>
PowerWeight< W, n >	Plus (const PowerWeight< W, n > &w1, const PowerWeight< W, n > &w2)
	Semiring plus operation.
template<class W , unsigned int n>
PowerWeight< W, n >	Times (const PowerWeight< W, n > &w1, const PowerWeight< W, n > &w2)
	Semiring times operation.
template<class W , unsigned int n>
PowerWeight< W, n >	Divide (const PowerWeight< W, n > &w1, const PowerWeight< W, n > &w2, DivideType type=DIVIDE_ANY)
	Semiring divide operation.
template<class W , unsigned int n>
PowerWeight< W, n >	Times (const W &s, const PowerWeight< W, n > &w)
	Semimodule left scalar product.
template<class W , unsigned int n>
PowerWeight< W, n >	Times (const PowerWeight< W, n > &w, const W &s)
	Semimodule right scalar product.
template<class W , unsigned int n>
W	DotProduct (const PowerWeight< W, n > &w1, const PowerWeight< W, n > &w2)
	Semimodule dot product.
template<class W1 , class W2 >
ProductWeight< W1, W2 >	Plus (const ProductWeight< W1, W2 > &w, const ProductWeight< W1, W2 > &v)
template<class W1 , class W2 >
ProductWeight< W1, W2 >	Times (const ProductWeight< W1, W2 > &w, const ProductWeight< W1, W2 > &v)
template<class W1 , class W2 >
ProductWeight< W1, W2 >	Divide (const ProductWeight< W1, W2 > &w, const ProductWeight< W1, W2 > &v, DivideType typ=DIVIDE_ANY)
template<class Arc >
void	Project (MutableFst< Arc > *fst, ProjectType project_type)
uint64	SetStartProperties (uint64 inprops)
	Definitions of inlined functions.
template<typename Weight >
uint64	SetFinalProperties (uint64 inprops, Weight old_weight, Weight new_weight)
	Definitions of template functions.
uint64	AddStateProperties (uint64 inprops)
template<typename A >
uint64	AddArcProperties (uint64 inprops, typename A::StateId s, const A &arc, const A *prev_arc)
uint64	DeleteStatesProperties (uint64 inprops)
uint64	DeleteAllStatesProperties (uint64 inprops, uint64 staticProps)
uint64	DeleteArcsProperties (uint64 inprops)
uint64	ClosureProperties (uint64 inprops, bool star, bool delayed)
	Properties for a concatenatively-closed FST.
uint64	ComplementProperties (uint64 inprops)
	Properties for a complemented FST.
uint64	ComposeProperties (uint64 inprops1, uint64 inprops2)
	Properties for a composed FST.
uint64	ConcatProperties (uint64 inprops1, uint64 inprops2, bool delayed)
	Properties for a concatenated FST.
uint64	DeterminizeProperties (uint64 inprops, bool has_subsequential_label)
	Properties for a determinized FST.
uint64	FactorWeightProperties (uint64 inprops)
	Properties for factored weight FST.
uint64	InvertProperties (uint64 inprops)
	Properties for an inverted FST.
uint64	ProjectProperties (uint64 inprops, bool project_input)
	Properties for a projected FST.
uint64	RelabelProperties (uint64 inprops)
	Properties for a relabeled FST.
uint64	ReplaceProperties (const vector< uint64 > &inprops, ssize_t root, bool epsilon_on_replace, bool no_empty_fsts)
	Properties for a replace FST.
uint64	ReverseProperties (uint64 inprops)
	Properties for a reversed FST. (the superinitial state limits this set).
uint64	ReweightProperties (uint64 inprops)
	Properties for re-weighted FST.
uint64	RmEpsilonProperties (uint64 inprops, bool delayed)
	Properties for an epsilon-removed FST.
uint64	ShortestPathProperties (uint64 props)
uint64	SynchronizeProperties (uint64 inprops)
	Properties for a synchronized FST.
uint64	UnionProperties (uint64 inprops1, uint64 inprops2, bool delayed)
	Properties for a unioned FST.
template<class Arc , class ArcFilter >
void	Prune (MutableFst< Arc > *fst, const PruneOptions< Arc, ArcFilter > &opts)
template<class Arc >
void	Prune (MutableFst< Arc > *fst, typename Arc::Weight weight_threshold, typename Arc::StateId state_threshold=kNoStateId, double delta=kDelta)
template<class Arc , class ArcFilter >
void	Prune (const Fst< Arc > &ifst, MutableFst< Arc > *ofst, const PruneOptions< Arc, ArcFilter > &opts)
template<class Arc >
void	Prune (const Fst< Arc > &ifst, MutableFst< Arc > *ofst, typename Arc::Weight weight_threshold, typename Arc::StateId state_threshold=kNoStateId, float delta=kDelta)
template<class Arc >
void	Push (MutableFst< Arc > *fst, ReweightType type, float delta=kDelta, bool remove_total_weight=false)
	namespace internal
template<class Arc , ReweightType rtype>
void	Push (const Fst< Arc > &ifst, MutableFst< Arc > *ofst, uint32 ptype, float delta=kDelta)
template<class Arc , class ArcSelector >
bool	RandEquivalent (const Fst< Arc > &fst1, const Fst< Arc > &fst2, ssize_t num_paths, float delta, const RandGenOptions< ArcSelector > &opts)
template<class Arc >
bool	RandEquivalent (const Fst< Arc > &fst1, const Fst< Arc > &fst2, ssize_t num_paths, float delta=kDelta, int seed=time(0), int path_length=INT_MAX)
template<class Arc , class ArcSelector >
void	RandGen (const Fst< Arc > &ifst, MutableFst< Arc > *ofst, const RandGenOptions< ArcSelector > &opts)
template<class Arc >
void	RandGen (const Fst< Arc > &ifst, MutableFst< Arc > *ofst)
template<class A >
void	Union (RationalFst< A > *fst1, const Fst< A > &fst2)
template<class A >
void	Concat (RationalFst< A > *fst1, const Fst< A > &fst2)
template<class A >
void	Concat (const Fst< A > &fst1, RationalFst< A > *fst2)
template<class A >
void	Closure (RationalFst< A > *fst, ClosureType closure_type)
template<class A >
Fst< A > *	Convert (const Fst< A > &fst, const string &ftype)
	Converts an fst to type 'type'.
template<class A >
void	Relabel (MutableFst< A > *fst, const vector< pair< typename A::Label, typename A::Label > > &ipairs, const vector< pair< typename A::Label, typename A::Label > > &opairs)
template<class A >
void	Relabel (MutableFst< A > *fst, const SymbolTable *new_isymbols, const SymbolTable *new_osymbols)
template<class A >
void	Relabel (MutableFst< A > *fst, const SymbolTable *old_isymbols, const SymbolTable *new_isymbols, bool attach_new_isymbols, const SymbolTable *old_osymbols, const SymbolTable *new_osymbols, bool attach_new_osymbols)
template<class Arc >
void	Replace (const vector< pair< typename Arc::Label, const Fst< Arc > * > > &, MutableFst< Arc > *, typename Arc::Label, bool)
template<class S , class P >
bool	operator== (const ReplaceStateTuple< S, P > &x, const ReplaceStateTuple< S, P > &y)
	Equality of replace state tuples.
template<class Arc >
void	Replace (const vector< pair< typename Arc::Label, const Fst< Arc > * > > &ifst_array, MutableFst< Arc > *ofst, typename Arc::Label root)
template<class Arc , class RevArc >
void	Reverse (const Fst< Arc > &ifst, MutableFst< RevArc > *ofst)
template<class Arc >
void	Reweight (MutableFst< Arc > *fst, const vector< typename Arc::Weight > &potential, ReweightType type)
template<class Arc , class Queue >
void	RmEpsilon (MutableFst< Arc > *fst, vector< typename Arc::Weight > *distance, const RmEpsilonOptions< Arc, Queue > &opts)
template<class Arc >
void	RmEpsilon (MutableFst< Arc > *fst, bool connect=true, typename Arc::Weight weight_threshold=Arc::Weight::Zero(), typename Arc::StateId state_threshold=kNoStateId, float delta=kDelta)
template<class A >
void	RmFinalEpsilon (MutableFst< A > *fst)
template<class A >
void	PrintFstInfo (const FstInfo< A > &fstinfo, bool pipe=false)
template<class Arc , class Queue , class ArcFilter >
void	ShortestDistance (const Fst< Arc > &fst, vector< typename Arc::Weight > *distance, const ShortestDistanceOptions< Arc, Queue, ArcFilter > &opts)
template<class Arc >
void	ShortestDistance (const Fst< Arc > &fst, vector< typename Arc::Weight > *distance, bool reverse=false, float delta=kDelta)
template<class Arc >
Arc::Weight	ShortestDistance (const Fst< Arc > &fst)
template<class Arc , class Queue , class ArcFilter >
void	SingleShortestPath (const Fst< Arc > &ifst, MutableFst< Arc > *ofst, vector< typename Arc::Weight > *distance, ShortestPathOptions< Arc, Queue, ArcFilter > &opts)
template<class Arc , class RevArc >
void	NShortestPath (const Fst< RevArc > &ifst, MutableFst< Arc > *ofst, const vector< typename Arc::Weight > &distance, size_t n, float delta=kDelta, typename Arc::Weight weight_threshold=Arc::Weight::Zero(), typename Arc::StateId state_threshold=kNoStateId)
template<class Arc , class Queue , class ArcFilter >
void	ShortestPath (const Fst< Arc > &ifst, MutableFst< Arc > *ofst, vector< typename Arc::Weight > *distance, ShortestPathOptions< Arc, Queue, ArcFilter > &opts)
template<class Arc >
void	ShortestPath (const Fst< Arc > &ifst, MutableFst< Arc > *ofst, size_t n=1, bool unique=false, bool first_path=false, typename Arc::Weight weight_threshold=Arc::Weight::Zero(), typename Arc::StateId state_threshold=kNoStateId)
template<class T >
SignedLogWeightTpl< T >	Plus (const SignedLogWeightTpl< T > &w1, const SignedLogWeightTpl< T > &w2)
template<class T >
SignedLogWeightTpl< T >	Times (const SignedLogWeightTpl< T > &w1, const SignedLogWeightTpl< T > &w2)
template<class T >
SignedLogWeightTpl< T >	Divide (const SignedLogWeightTpl< T > &w1, const SignedLogWeightTpl< T > &w2, DivideType typ=DIVIDE_ANY)
template<class T >
bool	ApproxEqual (const SignedLogWeightTpl< T > &w1, const SignedLogWeightTpl< T > &w2, float delta=kDelta)
template<class T >
bool	operator== (const SignedLogWeightTpl< T > &w1, const SignedLogWeightTpl< T > &w2)
template<class W , class K >
SparsePowerWeight< W, K >	Plus (const SparsePowerWeight< W, K > &w1, const SparsePowerWeight< W, K > &w2)
	Semimodule plus operation.
template<class W , class K >
SparsePowerWeight< W, K >	Times (const SparsePowerWeight< W, K > &w1, const SparsePowerWeight< W, K > &w2)
	Semimodule times operation.
template<class W , class K >
SparsePowerWeight< W, K >	Divide (const SparsePowerWeight< W, K > &w1, const SparsePowerWeight< W, K > &w2, DivideType type=DIVIDE_ANY)
	Semimodule divide operation.
template<class W , class K >
const W &	DotProduct (const SparsePowerWeight< W, K > &w1, const SparsePowerWeight< W, K > &w2)
	Semimodule dot product.
template<class W , class K >
bool	ApproxEqual (const SparsePowerWeight< W, K > &w1, const SparsePowerWeight< W, K > &w2, float delta=kDelta)
template<class W , class K >
SparsePowerWeight< W, K >	Times (const W &k, const SparsePowerWeight< W, K > &w2)
template<class W , class K >
SparsePowerWeight< W, K >	Times (const SparsePowerWeight< W, K > &w1, const W &k)
template<class W , class K >
istream &	operator>> (istream &strm, SparseTupleWeight< W, K > &w)
template<class W , class K , class M >
void	SparseTupleWeightMap (SparseTupleWeight< W, K > *ret, const SparseTupleWeight< W, K > &w1, const SparseTupleWeight< W, K > &w2, const M &operator_mapper)
template<class W , class K >
bool	operator== (const SparseTupleWeight< W, K > &w1, const SparseTupleWeight< W, K > &w2)
template<class W , class K >
bool	operator!= (const SparseTupleWeight< W, K > &w1, const SparseTupleWeight< W, K > &w2)
template<class W , class K >
ostream &	operator<< (ostream &strm, const SparseTupleWeight< W, K > &w)
template<typename S , typename F >
bool	operator== (const ComposeStateTuple< S, F > &x, const ComposeStateTuple< S, F > &y)
	Equality of composition state tuples.
template<class Arc >
void	StateSort (MutableFst< Arc > *fst, const vector< typename Arc::StateId > &order)
template<typename L , StringType S>
bool	operator== (const StringWeight< L, S > &, const StringWeight< L, S > &)
template<typename L , StringType S>
bool	operator!= (const StringWeight< L, S > &w1, const StringWeight< L, S > &w2)
template<typename L , StringType S>
bool	ApproxEqual (const StringWeight< L, S > &w1, const StringWeight< L, S > &w2, float delta=kDelta)
template<typename L , StringType S>
ostream &	operator<< (ostream &strm, const StringWeight< L, S > &w)
template<typename L , StringType S>
istream &	operator>> (istream &strm, StringWeight< L, S > &w)
template<typename L , StringType S>
StringWeight< L, S >	Plus (const StringWeight< L, S > &w1, const StringWeight< L, S > &w2)
template<typename L >
StringWeight< L, STRING_LEFT >	Plus (const StringWeight< L, STRING_LEFT > &w1, const StringWeight< L, STRING_LEFT > &w2)
	Longest common prefix for left string semiring.
template<typename L >
StringWeight< L, STRING_RIGHT >	Plus (const StringWeight< L, STRING_RIGHT > &w1, const StringWeight< L, STRING_RIGHT > &w2)
	Longest common suffix for right string semiring.
template<typename L , StringType S>
StringWeight< L, S >	Times (const StringWeight< L, S > &w1, const StringWeight< L, S > &w2)
template<typename L , StringType S>
StringWeight< L, S >	Divide (const StringWeight< L, S > &w1, const StringWeight< L, S > &w2, DivideType typ)
template<typename L >
StringWeight< L, STRING_RIGHT >	Divide (const StringWeight< L, STRING_RIGHT > &w1, const StringWeight< L, STRING_RIGHT > &w2, DivideType typ)
	Right division in the right string semiring.
template<typename L >
StringWeight< L, STRING_RIGHT_RESTRICT >	Divide (const StringWeight< L, STRING_RIGHT_RESTRICT > &w1, const StringWeight< L, STRING_RIGHT_RESTRICT > &w2, DivideType typ)
	Right division in the right restricted string semiring.
bool	CompatSymbols (const SymbolTable *syms1, const SymbolTable *syms2, bool warning=true)
	Tests compatibilty between two sets of symbol tables.
template<class Label >
SymbolTable *	RelabelSymbolTable (const SymbolTable *table, const vector< pair< Label, Label > > &pairs)
template<class Arc >
void	Synchronize (const Fst< Arc > &ifst, MutableFst< Arc > *ofst)
uint64	KnownProperties (uint64 props)
bool	CompatProperties (uint64 props1, uint64 props2)
	Tests compatibility between two sets of properties.
template<class Arc >
uint64	ComputeProperties (const Fst< Arc > &fst, uint64 mask, uint64 *known, bool use_stored)
template<class Arc >
bool	TopSort (MutableFst< Arc > *fst)
template<class W , unsigned int n>
istream &	operator>> (istream &strm, TupleWeight< W, n > &w)
template<class W , unsigned int n>
bool	operator== (const TupleWeight< W, n > &w1, const TupleWeight< W, n > &w2)
template<class W , unsigned int n>
bool	operator!= (const TupleWeight< W, n > &w1, const TupleWeight< W, n > &w2)
template<class W , unsigned int n>
bool	ApproxEqual (const TupleWeight< W, n > &w1, const TupleWeight< W, n > &w2, float delta=kDelta)
template<class W , unsigned int n>
ostream &	operator<< (ostream &strm, const TupleWeight< W, n > &w)
template<class Arc >
void	Union (MutableFst< Arc > *fst1, const Fst< Arc > &fst2)
template<class Arc >
void	Union (RationalFst< Arc > *fst1, const Fst< Arc > &fst2)
template<typename T >
istream &	ReadType (istream &strm, T *t)
	Read some types from an input stream.
	READ_POD_TYPE (bool)
	READ_POD_TYPE (char)
	READ_POD_TYPE (signed char)
	READ_POD_TYPE (unsigned char)
	READ_POD_TYPE (short)
	READ_POD_TYPE (int)
	READ_POD_TYPE (long)
	READ_POD_TYPE (unsigned long long)
	READ_POD_TYPE (float)
	READ_POD_TYPE (double)
istream &	ReadType (istream &strm, string *s)
	String case.
template<typename S , typename T >
istream &	ReadType (istream &strm, pair< S, T > *p)
	Pair case.
template<typename S , typename T >
istream &	ReadType (istream &strm, pair< const S, T > *p)
template<typename C >
void	StlReserve (C *c, int64 n)
	General case - no-op.
template<typename S , typename T >
void	StlReserve (vector< S, T > *c, int64 n)
	Specialization for vectors.
	READ_STL_SEQ_TYPE (vector)
	READ_STL_SEQ_TYPE (list)
	READ_STL_ASSOC_TYPE (set)
	READ_STL_ASSOC_TYPE (unordered_set)
	READ_STL_ASSOC_TYPE (map)
	READ_STL_ASSOC_TYPE (unordered_map)
template<typename T >
ostream &	WriteType (ostream &strm, const T t)
	Write some types to an output stream.
	WRITE_POD_TYPE (bool)
	WRITE_POD_TYPE (char)
	WRITE_POD_TYPE (signed char)
	WRITE_POD_TYPE (unsigned char)
	WRITE_POD_TYPE (short)
	WRITE_POD_TYPE (int)
	WRITE_POD_TYPE (long)
	WRITE_POD_TYPE (unsigned long long)
	WRITE_POD_TYPE (float)
	WRITE_POD_TYPE (double)
ostream &	WriteType (ostream &strm, const string &s)
	String case.
template<typename S , typename T >
ostream &	WriteType (ostream &strm, const pair< S, T > &p)
	Pair case.
	WRITE_STL_SEQ_TYPE (vector)
	WRITE_STL_SEQ_TYPE (list)
	WRITE_STL_ASSOC_TYPE (set)
	WRITE_STL_ASSOC_TYPE (unordered_set)
	WRITE_STL_ASSOC_TYPE (map)
	WRITE_STL_ASSOC_TYPE (unordered_map)
int64	StrToInt64 (const string &s, const string &src, size_t nline, bool allow_negative)
	Utilities for converting between int64 or Weight and string.
template<typename Weight >
Weight	StrToWeight (const string &s, const string &src, size_t nline)
void	Int64ToStr (int64 n, string *s)
template<typename Weight >
void	WeightToStr (Weight w, string *s)
template<typename Label >
void	ReadLabelPairs (const string &filename, vector< pair< Label, Label > > *pairs, bool allow_negative=false)
	Utilities for reading/writing label pairs.
template<typename Label >
void	WriteLabelPairs (const string &filename, const vector< pair< Label, Label > > &pairs)
void	ConvertToLegalCSymbol (string *s)
	Utilities for converting a type name to a legal C symbol.
template<class Arc >
bool	Verify (const Fst< Arc > &fst, bool allow_negative_labels=false)
	Verifies that an Fst's contents are sane.
template<class Arc , class V , class Q , class ArcFilter >
void	Visit (const Fst< Arc > &fst, V *visitor, Q *queue, ArcFilter filter)
template<class Arc , class V , class Q >
void	Visit (const Fst< Arc > &fst, V *visitor, Q *queue)
template<class W >
W	Power (W w, size_t n)
void	SplitToVector (char *full, const char *delim, vector< char * > *vec, bool omit_empty_strings)
	REGISTER_FST (VectorFst, StdArc)
	Register VectorFst, ConstFst and EditFst for common arcs types.
	REGISTER_FST (ConstFst, StdArc)
	REGISTER_FST (EditFst, StdArc)
	REGISTER_FST (VectorFst, CustomArc)
	REGISTER_FST (ConstFst, CustomArc)
Variables
const int	kDfsWhite = 0
	An Fst state's DFS status.
const int	kDfsGrey = 1
	Discovered & unfinished.
const int	kDfsBlack = 2
	Finished.
const uint32	kFactorFinalWeights = 0x00000001
const uint32	kFactorArcWeights = 0x00000002
const int	kNoStateId = -1
	Not a valid state ID.
const int	kNoLabel = -1
	Not a valid label.
const uint32	kInputLookAheadMatcher = 0x00000001
const uint32	kOutputLookAheadMatcher = 0x00000002
	Matcher is a lookahead matcher when 'match_type' is MATCH_OUTPUT.
const uint32	kLookAheadWeight = 0x00000004
const uint32	kLookAheadPrefix = 0x00000008
const uint32	kLookAheadNonEpsilons = 0x00000010
	Look-ahead of matcher FST non-epsilon arcs?
const uint32	kLookAheadEpsilons = 0x00000020
	Look-ahead of matcher FST epsilon arcs?
const uint32	kLookAheadNonEpsilonPrefix = 0x00000040
const uint32	kLookAheadKeepRelabelData = 0x00000080
	For LabelLookAheadMatcher, save relabeling data to file.
const uint32	kLookAheadFlags = 0x000000ff
	Flags used for lookahead matchers.
const char	arc_lookahead_fst_type [] = "arc_lookahead"
	Arc look-ahead matchers.
const char	ilabel_lookahead_fst_type [] = "ilabel_lookahead"
	Label look-ahead matchers.
const char	olabel_lookahead_fst_type [] = "olabel_lookahead"
const uint32	kMatcherFlags = 0x00000000
	Flags used for basic matchers (see also lookahead.h).
const uint32	kMultiEpsList = 0x00000001
	Return multi-epsilon arcs for Find(kNoLabel).
const uint32	kMultiEpsLoop = 0x00000002
	Return a kNolabel loop for Find(multi_eps).
const uint64	kExpanded = 0x0000000000000001ULL
	The Fst is an ExpandedFst.
const uint64	kMutable = 0x0000000000000002ULL
	The Fst is a MutableFst.
const uint64	kAcceptor = 0x0000000000010000ULL
	ilabel == olabel for each arc
const uint64	kNotAcceptor = 0x0000000000020000ULL
	ilabel != olabel for some arc
const uint64	kIDeterministic = 0x0000000000040000ULL
	ilabels unique leaving each state
const uint64	kNonIDeterministic = 0x0000000000080000ULL
	ilabels not unique leaving some state
const uint64	kODeterministic = 0x0000000000100000ULL
	olabels unique leaving each state
const uint64	kNonODeterministic = 0x0000000000200000ULL
	olabels not unique leaving some state
const uint64	kEpsilons = 0x0000000000400000ULL
	FST has input/output epsilons.
const uint64	kNoEpsilons = 0x0000000000800000ULL
	FST has no input/output epsilons.
const uint64	kIEpsilons = 0x0000000001000000ULL
	FST has input epsilons.
const uint64	kNoIEpsilons = 0x0000000002000000ULL
	FST has no input epsilons.
const uint64	kOEpsilons = 0x0000000004000000ULL
	FST has output epsilons.
const uint64	kNoOEpsilons = 0x0000000008000000ULL
	FST has no output epsilons.
const uint64	kILabelSorted = 0x0000000010000000ULL
	ilabels sorted wrt < for each state
const uint64	kNotILabelSorted = 0x0000000020000000ULL
	ilabels not sorted wrt < for some state
const uint64	kOLabelSorted = 0x0000000040000000ULL
	olabels sorted wrt < for each state
const uint64	kNotOLabelSorted = 0x0000000080000000ULL
	olabels not sorted wrt < for some state
const uint64	kWeighted = 0x0000000100000000ULL
	Non-trivial arc or final weights.
const uint64	kUnweighted = 0x0000000200000000ULL
	Only trivial arc and final weights.
const uint64	kCyclic = 0x0000000400000000ULL
	FST has cycles.
const uint64	kAcyclic = 0x0000000800000000ULL
	FST has no cycles.
const uint64	kInitialCyclic = 0x0000001000000000ULL
	FST has cycles containing the initial state.
const uint64	kInitialAcyclic = 0x0000002000000000ULL
	FST has no cycles containing the initial state.
const uint64	kTopSorted = 0x0000004000000000ULL
	FST is topologically sorted.
const uint64	kNotTopSorted = 0x0000008000000000ULL
	FST is not topologically sorted.
const uint64	kAccessible = 0x0000010000000000ULL
	All states reachable from the initial state.
const uint64	kNotAccessible = 0x0000020000000000ULL
	Not all states reachable from the initial state.
const uint64	kCoAccessible = 0x0000040000000000ULL
	All states can reach a final state.
const uint64	kNotCoAccessible = 0x0000080000000000ULL
	Not all states can reach a final state.
const uint64	kString = 0x0000100000000000ULL
const uint64	kNotString = 0x0000200000000000ULL
	Not a string FST.
const uint64	kNullProperties
	Properties of an empty machine.
const uint64	kCopyProperties
	Properties that are preserved when an FST is copied.
const uint64	kSetStartProperties
	Properties that are preserved when an FST start state is set.
const uint64	kSetFinalProperties
	Properties that are preserved when an FST final weight is set.
const uint64	kAddStateProperties
	Properties that are preserved when an FST state is added.
const uint64	kAddArcProperties
	Properties that are preserved when an FST arc is added.
const uint64	kSetArcProperties = kExpanded | kMutable
	Properties that are preserved when an FST arc is set.
const uint64	kDeleteStatesProperties
	Properties that are preserved when FST states are deleted.
const uint64	kDeleteArcsProperties
	Properties that are preserved when FST arcs are deleted.
const uint64	kStateSortProperties
	Properties that are preserved when an FST's states are reordered.
const uint64	kArcSortProperties
	Properties that are preserved when an FST's arcs are reordered.
const uint64	kILabelInvariantProperties
	Properties that are preserved when an FST's input labels are changed.
const uint64	kOLabelInvariantProperties
	Properties that are preserved when an FST's output labels are changed.
const uint64	kWeightInvariantProperties
const uint64	kAddSuperFinalProperties
const uint64	kRmSuperFinalProperties
const uint64	kBinaryProperties = 0x0000000000000003ULL
	All binary properties.
const uint64	kTrinaryProperties = 0x00003fffffff0000ULL
	All trinary properties.
const uint64	kPosTrinaryProperties
	1st bit of trinary properties
const uint64	kNegTrinaryProperties
	2nd bit of trinary properties
const uint64	kFstProperties = kBinaryProperties | kTrinaryProperties
	All properties.
const char *	PropertyNames []
	Property string names (indexed by bit position).
const uint32	kPushWeights = 0x0001
const uint32	kPushLabels = 0x0002
const uint32	kPushRemoveTotalWeight = 0x0004
const uint32	kPushRemoveCommonAffix = 0x0008
const int	kStringInfinity = -1
	Label for the infinite string.
const int	kStringBad = -2
	Label for a non-string.
const char	kStringSeparator = '_'
	Label separator in strings.
const float	kDelta = 1.0F/1024.0F
	A representable float near .001.
const uint64	kLeftSemiring = 0x0000000000000001ULL
	For all a,b,c: Times(c, Plus(a,b)) = Plus(Times(c,a), Times(c, b)).
const uint64	kRightSemiring = 0x0000000000000002ULL
	For all a,b,c: Times(Plus(a,b), c) = Plus(Times(a,c), Times(b, c)).
const uint64	kSemiring = kLeftSemiring | kRightSemiring
const uint64	kCommutative = 0x0000000000000004ULL
	For all a,b: Times(a,b) = Times(b,a).
const uint64	kIdempotent = 0x0000000000000008ULL
	For all a: Plus(a, a) = a.
const uint64	kPath = 0x0000000000000010ULL
	For all a,b: Plus(a,b) = a or Plus(a,b) = b.
const int	kLineLen = 8096
	Maximum line length in textual symbols file.

---

Detailed Description

For optional argument declarations.

for ShortestDistanceOptions

for RandArcSelection

for ProjectType

for ComposeOptions, ComposeFilter

Convenience file that includes all FstScript functionality.

Forward declarations for the FST and FST-script classes.

for ComposeFilter

Convenience templates for defining arg packs for the FstClass operations.

for DISALLOW_COPY_AND_ASSIGN

for ComposeOptions

For FarTypeToString.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Copyright 2005-2010 Google, Inc. Author: jpr@google.com (Jake Ratkiewicz)

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Copyright 2005-2010 Google, Inc. Author: jpr@google.com (Jake Ratkiewicz) Definitions of 'scriptable' versions of FAR operations, that is, those that can be called with FstClass-type arguments.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Copyright 2005-2010 Google, Inc. Author: allauzen@google.com (Cyril Allauzen)

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Copyright 2005-2010 Google, Inc. Author: jpr@google.com (Jake Ratkiewicz) Generic class representing a globally-stored correspondence between objects of KeyType and EntryType. KeyType must: a) be such as can be stored as a key in a map<> b) be concatenable with a const char* with the + operator (or you must subclass and redefine LoadEntryFromSharedObject) EntryType must be default constructible.

The third template parameter should be the type of a subclass of this class (think CRTP). This is to allow GetRegister() to instantiate and return an object of the appropriate type.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Copyright 2005-2010 Google, Inc. Author: jpr@google.com (Jake Ratkiewicz) See operation-templates.h for a discussion about why these are needed; the short story is that all FstClass operations must be implemented by a version that takes one argument, most likely a struct bundling all the logical arguments together. These template structs provide convenient ways to specify these bundles (e.g. by means of appropriate typedefs). The ArgPack template is sufficient for bundling together all the args for a particular function. The function is assumed to be void-returning. If you want a space for a return value, use the WithReturnValue template as follows: WithReturnValue<bool, ArgPack<...> >

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Copyright 2005-2010 Google, Inc. Author: jpr@google.com (Jake Ratkiewicz) Classes to support "boxing" all existing types of FST arcs in a single FstClass which hides the arc types. This allows clients to load and work with FSTs without knowing the arc type. These classes are only recommended for use in high-level scripting applications. Most users should use the lower-level templated versions corresponding to these classes.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Copyright 2005-2010 Google, Inc. Author: jpr@google.com (Jake Ratkiewicz) Major classes Templates like Operation< >, Apply< > Operations REGISTER OPERATIONS This class is necessary because registering each of the operations separately overfills the stack, as there's so many of them.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Copyright 2005-2010 Google, Inc. Author: jpr@google.com (Jake Ratkiewicz) Holds methods and classes responsible for maintaining the register for FstClass arc types.

the following is necessary, or SWIG complains mightily about shortestdistanceoptions not being defined before being used as a base.

for ArcFilterType for QueueType

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Copyright 2005-2010 Google, Inc. Author: jpr@google.com (Jake Ratkiewicz) Represents a generic weight in an FST -- that is, represents a specific type of weight underneath while hiding that type from a client.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Copyright 2005-2010 Google, Inc. Author: jpr@google.com (Jake Ratkiewicz) These classes are only recommended for use in high-level scripting applications. Most users should use the lower-level templated versions corresponding to these classes.

---

Typedef Documentation

typedef CacheOptions fst::ArcSortFstOptions

Definition at line 71 of file arcsort.h.

typedef IntegerFilterState< signed char > fst::CharFilterState

Definition at line 80 of file compose-filter.h.

typedef RationalFstOptions fst::ConcatFstOptions

Definition at line 147 of file concat.h.

typedef ComposeOptions fst::DifferenceOptions

Definition at line 138 of file difference.h.

typedef FloatWeightTpl< float > fst::FloatWeight

Single precision FloatWeight.

Definition at line 102 of file float-weight.h.

typedef int fst::FstOnceType

Single initialization - single-thread implementation

Definition at line 33 of file lock.h.

typedef ComposeOptions fst::IntersectOptions

Definition at line 123 of file intersect.h.

typedef IntegerFilterState< int > fst::IntFilterState

Definition at line 82 of file compose-filter.h.

typedef ArcTpl< LogWeight > fst::LogArc

Definition at line 65 of file arc.h.

typedef MatcherFst<ConstFst<LogArc>, ArcLookAheadMatcher<SortedMatcher<ConstFst<LogArc> > >, arc_lookahead_fst_type> fst::LogArcLookAheadFst

Definition at line 306 of file matcher-fst.h.

typedef LogProbArcSelector<LogArc> fst::LogArcSelector

Definition at line 97 of file randgen.h.

typedef MatcherFst<ConstFst<LogArc>, LabelLookAheadMatcher<SortedMatcher<ConstFst<LogArc> >, ilabel_lookahead_flags, FastLogAccumulator<LogArc> >, ilabel_lookahead_fst_type, LabelLookAheadRelabeler<LogArc> > fst::LogILabelLookAheadFst

Definition at line 332 of file matcher-fst.h.

typedef MatcherFst<ConstFst<LogArc>, LabelLookAheadMatcher<SortedMatcher<ConstFst<LogArc> >, olabel_lookahead_flags, FastLogAccumulator<LogArc> >, olabel_lookahead_fst_type, LabelLookAheadRelabeler<LogArc> > fst::LogOLabelLookAheadFst

Definition at line 346 of file matcher-fst.h.

typedef WeightConvertMapper<LogArc, StdArc> fst::LogToStdMapper

Definition at line 707 of file map.h.

typedef LogWeightTpl< float > fst::LogWeight

Single precision LogWeight.

Definition at line 343 of file float-weight.h.

typedef LogWeightGenerator_<float> fst::LogWeightGenerator

Definition at line 104 of file random-weight.h.

typedef ArcTpl<MinMaxWeight> fst::MinMaxArc

Definition at line 67 of file arc.h.

typedef MinMaxWeightTpl< float > fst::MinMaxWeight

Single precision MinMaxWeight.

Definition at line 470 of file float-weight.h.

typedef MinMaxWeightGenerator_<float> fst::MinMaxWeightGenerator

Definition at line 139 of file random-weight.h.

typedef CacheOptions fst::RationalFstOptions

Definition at line 36 of file rational.h.

typedef CacheOptions fst::RelabelFstOptions

Definition at line 163 of file relabel.h.

typedef IntegerFilterState< short > fst::ShortFilterState

Definition at line 81 of file compose-filter.h.

typedef ArcTpl<SignedLogWeight> fst::SignedLogArc

Definition at line 66 of file arc.h.

typedef SignedLogWeightTpl<float> fst::SignedLogWeight

Definition at line 194 of file signed-log-weight.h.

typedef SignedLogWeightGenerator_<float> fst::SignedLogWeightGenerator

Definition at line 317 of file random-weight.h.

typedef ArcTpl< TropicalWeight > fst::StdArc

Definition at line 64 of file arc.h.

typedef MatcherFst<ConstFst<StdArc>, ArcLookAheadMatcher<SortedMatcher<ConstFst<StdArc> > >, arc_lookahead_fst_type> fst::StdArcLookAheadFst

Definition at line 302 of file matcher-fst.h.

typedef LogProbArcSelector<StdArc> fst::StdArcSelector

Convenience definitions.

Definition at line 96 of file randgen.h.

typedef ClosureFst< StdArc > fst::StdClosureFst

Useful alias when using StdArc.

Definition at line 149 of file closure.h.

typedef CompactFst< StdArc, AcceptorCompactor< StdArc > > fst::StdCompactAcceptorFst

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

typedef CompactFst< StdArc, StringCompactor< StdArc > > fst::StdCompactStringFst

Uselful aliases when using StdArc.

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

typedef CompactFst< StdArc, UnweightedAcceptorCompactor< StdArc > > fst::StdCompactUnweightedAcceptorFst

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

typedef CompactFst< StdArc, UnweightedCompactor< StdArc > > fst::StdCompactUnweightedFst

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

typedef CompactFst< StdArc, WeightedStringCompactor< StdArc > > fst::StdCompactWeightedStringFst

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

typedef ComplementFst<StdArc> fst::StdComplementFst

Useful alias when using StdArc.

Definition at line 315 of file complement.h.

typedef ComposeFst< StdArc > fst::StdComposeFst

Useful alias when using StdArc.

Definition at line 578 of file compose.h.

typedef ConcatFst< StdArc > fst::StdConcatFst

Useful alias when using StdArc.

Definition at line 211 of file concat.h.

typedef ConstFst< StdArc > fst::StdConstFst

A useful alias when using StdArc.

Definition at line 385 of file const-fst.h.

typedef DecodeFst<StdArc> fst::StdDecodeFst

Definition at line 573 of file encode.h.

typedef DeterminizeFst< StdArc > fst::StdDeterminizeFst

Useful aliases when using StdArc.

Definition at line 776 of file determinize.h.

typedef DifferenceFst< StdArc > fst::StdDifferenceFst

Useful alias when using StdArc.

Definition at line 135 of file difference.h.

typedef EncodeFst<StdArc> fst::StdEncodeFst

Useful aliases when using StdArc.

Definition at line 571 of file encode.h.

typedef ExpandedFst< StdArc > fst::StdExpandedFst

A useful alias when using StdArc.

Definition at line 111 of file expanded-fst.h.

typedef Fst< StdArc > fst::StdFst

namespace internal

A useful alias when using StdArc.

Definition at line 92 of file fst-decl.h.

typedef ILabelCompare<StdArc> fst::StdILabelCompare

Definition at line 291 of file arcsort.h.

typedef MatcherFst<ConstFst<StdArc>, LabelLookAheadMatcher<SortedMatcher<ConstFst<StdArc> >, ilabel_lookahead_flags, FastLogAccumulator<StdArc> >, ilabel_lookahead_fst_type, LabelLookAheadRelabeler<StdArc> > fst::StdILabelLookAheadFst

Definition at line 325 of file matcher-fst.h.

typedef IntersectFst< StdArc > fst::StdIntersectFst

Useful alias when using StdArc.

Definition at line 103 of file fst-decl.h.

typedef InvertFst< StdArc > fst::StdInvertFst

Useful alias when using StdArc.

Definition at line 104 of file fst-decl.h.

typedef MutableFst< StdArc > fst::StdMutableFst

A useful alias when using StdArc.

Definition at line 93 of file fst-decl.h.

typedef OLabelCompare<StdArc> fst::StdOLabelCompare

Definition at line 293 of file arcsort.h.

typedef MatcherFst<ConstFst<StdArc>, LabelLookAheadMatcher<SortedMatcher<ConstFst<StdArc> >, olabel_lookahead_flags, FastLogAccumulator<StdArc> >, olabel_lookahead_fst_type, LabelLookAheadRelabeler<StdArc> > fst::StdOLabelLookAheadFst

Definition at line 339 of file matcher-fst.h.

typedef ProjectFst< StdArc > fst::StdProjectFst

Useful alias when using StdArc.

Definition at line 105 of file fst-decl.h.

typedef RelabelFst< StdArc > fst::StdRelabelFst

Useful alias when using StdArc.

Definition at line 106 of file fst-decl.h.

typedef ReplaceFst< StdArc > fst::StdReplaceFst

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

typedef RmEpsilonFst< StdArc > fst::StdRmEpsilonFst

Useful alias when using StdArc.

Definition at line 109 of file fst-decl.h.

typedef WeightConvertMapper<StdArc, LogArc> fst::StdToLogMapper

Consider using more efficient Cast (fst.h) instead.

Definition at line 706 of file map.h.

typedef UnionFst< StdArc > fst::StdUnionFst

Useful alias when using StdArc.

Definition at line 110 of file fst-decl.h.

typedef VectorFst< StdArc > fst::StdVectorFst

A useful alias when using StdArc.

Definition at line 94 of file fst-decl.h.

typedef CacheOptions fst::SynchronizeFstOptions

Definition at line 42 of file synchronize.h.

typedef TropicalWeightTpl< float > fst::TropicalWeight

Single precision TropicalWeight.

Definition at line 228 of file float-weight.h.

typedef TropicalWeightGenerator_<float> fst::TropicalWeightGenerator

Definition at line 72 of file random-weight.h.

typedef RationalFstOptions fst::UnionFstOptions

Definition at line 97 of file union.h.

---

Enumeration Type Documentation

enum fst::ClosureType

This specifies whether to add the empty string.

Enumerator:

CLOSURE_STAR
CLOSURE_PLUS	T* -> add the empty string.

Definition at line 39 of file rational.h.

enum fst::ComposeFilter

Enumerator:

AUTO_FILTER
SEQUENCE_FILTER
ALT_SEQUENCE_FILTER
MATCH_FILTER

Definition at line 580 of file compose.h.

enum fst::DivideType

Determines direction of division.

Enumerator:

DIVIDE_LEFT
DIVIDE_RIGHT	left division
DIVIDE_ANY	right division

Definition at line 109 of file weight.h.

enum fst::EncodeType

Enumerator:

ENCODE
DECODE

Definition at line 43 of file encode.h.

enum fst::EpsNormalizeType

Enumerator:

EPS_NORM_INPUT
EPS_NORM_OUTPUT

Definition at line 36 of file epsnormalize.h.

enum fst::FarEntryType

Enumerator:

FET_LINE
FET_FILE

Definition at line 30 of file far.h.

enum fst::FarTokenType

Enumerator:

FTT_SYMBOL
FTT_BYTE
FTT_UTF8

Definition at line 31 of file far.h.

enum fst::FarType

Enumerator:

FAR_DEFAULT
FAR_STTABLE
FAR_SSTABLE

Definition at line 55 of file far.h.

enum fst::MapFinalAction

This determines how final weights are mapped.

Enumerator:

MAP_NO_SUPERFINAL	A final weight is mapped into a final weight. An error is raised if this is not possible.
MAP_ALLOW_SUPERFINAL	A final weight is mapped to an arc to the superfinal state when the result cannot be represented as a final weight. The superfinal state will be added only if it is needed.
MAP_REQUIRE_SUPERFINAL	A final weight is mapped to an arc to the superfinal state unless the result can be represented as a final weight of weight Zero(). The superfinal state is always added (if the input is not the empty Fst).

Definition at line 37 of file map.h.

enum fst::MapSymbolsAction

This determines how symbol tables are mapped.

Enumerator:

MAP_CLEAR_SYMBOLS	Symbols should be cleared in the result by the map.
MAP_COPY_SYMBOLS	Symbols should be copied from the input FST by the map.
MAP_NOOP_SYMBOLS	Symbols should not be modified in the result by the map itself. (They may set by the mapper).

Definition at line 55 of file map.h.

enum fst::MapType

Convenience function for mapping with one of several predefined map types.

Enumerator:

IDENTITY_MAPPER
INVERT_MAPPER
PLUS_MAPPER
QUANTIZE_MAPPER
RMWEIGHT_MAPPER
SUPERFINAL_MAPPER
TIMES_MAPPER

Definition at line 1073 of file map.h.

enum fst::MatcherRewriteMode

Specifies whether during matching we rewrite both the input and output sides.

Enumerator:

MATCHER_REWRITE_AUTO
MATCHER_REWRITE_ALWAYS	Rewrites both sides iff acceptor.
MATCHER_REWRITE_NEVER

Definition at line 313 of file matcher.h.

enum fst::MatchType

Specifies matcher action.

Enumerator:

MATCH_INPUT
MATCH_OUTPUT	Match input label.
MATCH_BOTH	Match output label.
MATCH_NONE	Match input or output label.
MATCH_UNKNOWN	Match nothing.

Definition at line 132 of file fst.h.

enum fst::ProjectType

This specifies whether to project on input or output.

Enumerator:

PROJECT_INPUT
PROJECT_OUTPUT

Definition at line 30 of file project.h.

enum fst::QueueType

State queue types.

template <class s>=""> class Queue { public: typedef typename S StateId;

Ctr: may need args (e.g., Fst, comparator) for some queues Queue(...); Returns the head of the queue StateId Head() const; Inserts a state void Enqueue(StateId s); Removes the head of the queue void Dequeue(); Updates ordering of state s when weight changes, if necessary void Update(StateId s); Does the queue contain no elements? bool Empty() const; Remove all states from queue void Clear(); };

Enumerator:

TRIVIAL_QUEUE
FIFO_QUEUE	Single state queue.
LIFO_QUEUE	First-in, first-out queue.
SHORTEST_FIRST_QUEUE	Last-in, first-out queue.
TOP_ORDER_QUEUE	Shortest-first queue.
STATE_ORDER_QUEUE	Topologically-ordered queue.
SCC_QUEUE	State-ID ordered queue.
AUTO_QUEUE	Component graph top-ordered meta-queue.
OTHER_QUEUE	Auto-selected queue.

Definition at line 58 of file queue.h.

enum fst::ReweightType

Enumerator:

REWEIGHT_TO_INITIAL
REWEIGHT_TO_FINAL

Definition at line 30 of file reweight.h.

enum fst::StringType

Determines whether to use left or right string semiring. Includes restricted versions that signal an error if proper prefixes (suffixes) would otherwise be returned by Plus, useful with various algorithms that require functional transducer input with the string semirings.

Enumerator:

STRING_LEFT
STRING_RIGHT
STRING_LEFT_RESTRICT
STRING_RIGHT_RESTRICT

Definition at line 41 of file string-weight.h.

---

Function Documentation

template<class A >

void fst::AcceptorMinimize

(

MutableFst< A > *

fst

)

Definition at line 486 of file minimize.h.

template<typename A >

uint64 fst::AddArcProperties	(	uint64	inprops,
		typename A::StateId	s,
		const A &	arc,
		const A *	prev_arc
	)

Gets the properties for the MutableFst::AddArc method.

Parameters:

	inprops	the current properties of the fst
	s	the id of the state to which an arc is being added
	arc	the arc being added to the state with the specified id
	prev_arc	the previously-added (or "last") arc of state s, or NULL if s currently has no arcs

Definition at line 389 of file properties.h.

uint64 fst::AddStateProperties

(

uint64

inprops

)

[inline]

Definition at line 347 of file properties.h.

template<class T >

bool fst::ApproxEqual	(	const FloatWeightTpl< T > &	w1,
		const FloatWeightTpl< T > &	w2,
		float	delta = kDelta
	)			[inline]

Definition at line 141 of file float-weight.h.

template<class T >

bool fst::ApproxEqual	(	const SignedLogWeightTpl< T > &	w1,
		const SignedLogWeightTpl< T > &	w2,
		float	delta = kDelta
	)			[inline]

Definition at line 170 of file signed-log-weight.h.

template<class W , class K >

bool fst::ApproxEqual	(	const SparsePowerWeight< W, K > &	w1,
		const SparsePowerWeight< W, K > &	w2,
		float	delta = kDelta
	)			[inline]

Definition at line 184 of file sparse-power-weight.h.

template<typename L , StringType S>

bool fst::ApproxEqual	(	const StringWeight< L, S > &	w1,
		const StringWeight< L, S > &	w2,
		float	delta = kDelta
	)			[inline]

Definition at line 313 of file string-weight.h.

template<class W1 , class W2 >

bool fst::ApproxEqual	(	const PairWeight< W1, W2 > &	w1,
		const PairWeight< W1, W2 > &	w2,
		float	delta = kDelta
	)			[inline]

Definition at line 207 of file pair-weight.h.

template<class W , unsigned int n>

bool fst::ApproxEqual	(	const TupleWeight< W, n > &	w1,
		const TupleWeight< W, n > &	w2,
		float	delta = kDelta
	)			[inline]

Definition at line 254 of file tuple-weight.h.

template<class A >

void fst::ArcMerge

(

MutableFst< A > *

fst

)

Combines identically labeled arcs with the same weights. For each state we combine arcs with the same input, output label and weight, keeping only one.

Definition at line 61 of file arcmerge.h.

template<class Arc , class Compare >

void fst::ArcSort	(	MutableFst< Arc > *	fst,
		Compare	comp
	)

Sorts the arcs in an FST according to function object 'comp' of type Compare. This version modifies its input. Comparison function objects IlabelCompare and OlabelCompare are provived by the library. In general, Compare must meet the requirements for an STL sort comparision function object. It must also have a member Properties(uint64) that specifies the known properties of the sorted FST; it takes as argument the input FST's known properties before the sort.

Complexity:

• Time: O(V D log D)
• Space: O(D) where V = # of states and D = maximum out-degree.

Definition at line 47 of file arcsort.h.

template<class A >

void fst::ArcSum

(

MutableFst< A > *

fst

)

Combines identically labeled arcs, summing weights. For each state we combine arcs with the same input and output label, summing their weights using Weight:Plus().

Definition at line 63 of file arcsum.h.

template<class Dest , class Source >

Dest fst::bit_cast

(

const Source &

source

)

[inline]

Bitcasting.

Definition at line 70 of file compat.h.

template<class F , class G >

void fst::Cast	(	const F &	,
		G *
	)

Converts FSTs by casting their implementations, where this makes sense (which excludes implementations with virtual methods). Must be a friend of the Fst classes involved (currently the concrete Fsts: VectorFst, ConstFst, CompactFst).

Definition at line 810 of file fst.h.

template<class A >

void fst::Closure	(	RationalFst< A > *	fst,
		ClosureType	closure_type
	)

template<class Arc >

void fst::Closure	(	RationalFst< Arc > *	fst,
		ClosureType	closure_type
	)

Computes the concatenative closure. This version modifies its RationalFst input.

Definition at line 74 of file closure.h.

template<class Arc >

void fst::Closure	(	MutableFst< Arc > *	fst,
		ClosureType	closure_type
	)

Computes the concatenative closure. This version modifies its MutableFst input. If FST transduces string x to y with weight a, then the closure transduces x to y with weight a, xx to yy with weight Times(a, a), xxx to yyy with with Times(Times(a, a), a), etc. If closure_type == CLOSURE_STAR, then the empty string is transduced to itself with weight Weight::One() as well.

Complexity:

• Time: O(V)
• Space: O(V) where V = # of states.

Definition at line 45 of file closure.h.

uint64 fst::ClosureProperties	(	uint64	inprops,
		bool	star,
		bool	delayed
	)

Properties for a concatenatively-closed FST.

These functions determine the properties associated with the FST result of various finite-state operations. The property arguments correspond to the operation's FST arguments. The properties returned assume the operation modifies its first argument. Bitwise-and this result with kCopyProperties for the case when a new (possibly delayed) FST is instead constructed.

Definition at line 38 of file properties.cc.

bool fst::CompatProperties	(	uint64	props1,
		uint64	props2
	)			[inline]

Tests compatibility between two sets of properties.

Definition at line 44 of file test-properties.h.

bool fst::CompatSymbols	(	const SymbolTable *	syms1,
		const SymbolTable *	syms2,
		bool	warning = true
	)			[inline]

Tests compatibilty between two sets of symbol tables.

Definition at line 458 of file symbol-table.h.

uint64 fst::ComplementProperties

(

uint64

inprops

)

Properties for a complemented FST.

Definition at line 51 of file properties.cc.

template<class Arc >

void fst::Compose	(	const Fst< Arc > &	ifst1,
		const Fst< Arc > &	ifst2,
		MutableFst< Arc > *	ofst,
		const ComposeOptions &	opts = ComposeOptions()
	)

Computes the composition of two transducers. This version writes the composed FST into a MurableFst. If FST1 transduces string x to y with weight a and FST2 transduces y to z with weight b, then their composition transduces string x to z with weight Times(x, z).

The output labels of the first transducer or the input labels of the second transducer must be sorted. The weights need to form a commutative semiring (valid for TropicalWeight and LogWeight).

Complexity: Assuming the first FST is unsorted and the second is sorted:

• Time: O(V1 V2 D1 (log D2 + M2)),
• Space: O(V1 V2 D1 M2) where Vi = # of states, Di = maximum out-degree, and Mi is the maximum multiplicity for the ith FST.

Caveats:

• Compose trims its output.
• The efficiency of composition can be strongly affected by several factors:
  • the choice of which tnansducer is sorted - prefer sorting the FST that has the greater average out-degree.
  • the amount of non-determinism
  • the presence and location of epsilon transitions - avoid epsilon transitions on the output side of the first transducer or the input side of the second transducer or prefer placing them later in a path since they delay matching and can introduce non-coaccessible states and transitions.

Definition at line 621 of file compose.h.

template<class Arc >

void fst::Compose	(	const Fst< Arc > &	ifst1,
		const vector< pair< typename Arc::Label, typename Arc::Label > > &	parens,
		const Fst< Arc > &	ifst2,
		MutableFst< Arc > *	ofst,
		const ComposeOptions &	opts = ComposeOptions()
	)

Composes pushdown transducer (PDT) encoded as an FST (1st arg) and an FST (2nd arg) with the result also a PDT encoded as an Fst. (3rd arg). In the PDTs, some transitions are labeled with open or close parentheses. To be interpreted as a PDT, the parens must balance on a path (see PdtExpand()). The open-close parenthesis label pairs are passed in 'parens'.

Definition at line 108 of file compose.h.

template<class Arc >

void fst::Compose	(	const Fst< Arc > &	ifst1,
		const Fst< Arc > &	ifst2,
		const vector< pair< typename Arc::Label, typename Arc::Label > > &	parens,
		MutableFst< Arc > *	ofst,
		const ComposeOptions &	opts = ComposeOptions()
	)

Composes an FST (1st arg) and pushdown transducer (PDT) encoded as an FST (2nd arg) with the result also a PDT encoded as an Fst (3rd arg). In the PDTs, some transitions are labeled with open or close parentheses. To be interpreted as a PDT, the parens must balance on a path (see ExpandFst()). The open-close parenthesis label pairs are passed in 'parens'.

Definition at line 130 of file compose.h.

uint64 fst::ComposeProperties	(	uint64	inprops1,
		uint64	inprops2
	)

Properties for a composed FST.

Definition at line 62 of file properties.cc.

template<class Arc >

uint64 fst::ComputeProperties	(	const Fst< Arc > &	fst,
		uint64	mask,
		uint64 *	known,
		bool	use_stored
	)

Computes FST property values defined in properties.h. The value of each property indicated in the mask will be determined and returned (these will never be unknown here). In the course of determining the properties specifically requested in the mask, certain other properties may be determined (those with little additional expense) and their values will be returned as well. The complete set of known properties (whether true or false) determined by this operation will be assigned to the the value pointed to by KNOWN. If 'use_stored' is true, pre-computed FST properties may be used when possible. This routine is seldom called directly; instead it is used to implement fst.Properties(mask, true).

Definition at line 74 of file test-properties.h.

template<class Arc >

void fst::Concat	(	MutableFst< Arc > *	fst1,
		const Fst< Arc > &	fst2
	)

Computes the concatenation (product) of two FSTs. If FST1 transduces string x to y with weight a and FST2 transduces string w to v with weight b, then their concatenation transduces string xw to yv with Times(a, b).

This version modifies its MutableFst argument (in first position).

Complexity:

• Time: O(V1 + V2 + E2)
• Space: O(V1 + V2 + E2) where Vi = # of states and Ei = # of arcs of the ith FST.

Definition at line 45 of file concat.h.

template<class A >

void fst::Concat	(	RationalFst< A > *	fst1,
		const Fst< A > &	fst2
	)

template<class A >

void fst::Concat	(	const Fst< A > &	fst1,
		RationalFst< A > *	fst2
	)

template<class Arc >

void fst::Concat	(	const Fst< Arc > &	fst1,
		MutableFst< Arc > *	fst2
	)

Computes the concatentation of two FSTs. This version modifies its MutableFst argument (in second position).

Complexity:

• Time: O(V1 + E1)
• Space: O(V1 + E1) where Vi = # of states and Ei = # of arcs of the ith FST.

Definition at line 96 of file concat.h.

template<class Arc >

void fst::Concat	(	RationalFst< Arc > *	fst1,
		const Fst< Arc > &	fst2
	)

Computes the concatentation of two FSTs. This version modifies its RationalFst input (in first position).

Definition at line 136 of file concat.h.

template<class Arc >

void fst::Concat	(	const Fst< Arc > &	fst1,
		RationalFst< Arc > *	fst2
	)

Computes the concatentation of two FSTs. This version modifies its RationalFst input (in second position).

Definition at line 143 of file concat.h.

uint64 fst::ConcatProperties	(	uint64	inprops1,
		uint64	inprops2,
		bool	delayed = false
	)

Properties for a concatenated FST.

Definition at line 81 of file properties.cc.

template<class Arc >

void fst::Connect

(

MutableFst< Arc > *

fst

)

Trims an FST, removing states and arcs that are not on successful paths. This version modifies its input.

Complexity:

• Time: O(V + E)
• Space: O(V + E) where V = # of states and E = # of arcs.

Definition at line 300 of file connect.h.

template<class A >

Fst<A>* fst::Convert	(	const Fst< A > &	fst,
		const string &	ftype
	)

Converts an fst to type 'type'.

Definition at line 115 of file register.h.

void fst::ConvertToLegalCSymbol

(

string *

s

)

Utilities for converting a type name to a legal C symbol.

Definition at line 46 of file util.cc.

template<class Arc >

Arc::StateId fst::CountStates

(

const Fst< Arc > &

fst

)

Function to return the number of states in an FST, counting them if necessary.

Definition at line 189 of file expanded-fst.h.

template<class Arc >

void fst::CountStatesAndArcs	(	const Fst< Arc > &	fst,
		size_t *	nstate,
		size_t *	narc
	)

Definition at line 33 of file info.h.

template<class A >

void fst::Decode	(	MutableFst< A > *	fst,
		const EncodeMapper< A > &	mapper
	)			[inline]

Definition at line 455 of file encode.h.

uint64 fst::DeleteAllStatesProperties	(	uint64	inprops,
		uint64	staticProps
	)			[inline]

Definition at line 355 of file properties.h.

uint64 fst::DeleteArcsProperties

(

uint64

inprops

)

[inline]

Definition at line 359 of file properties.h.

uint64 fst::DeleteStatesProperties

(

uint64

inprops

)

[inline]

Definition at line 351 of file properties.h.

template<class Arc >

void fst::Determinize	(	const Fst< Arc > &	ifst,
		MutableFst< Arc > *	ofst,
		const DeterminizeOptions< Arc > &	opts = DeterminizeOptions<Arc>()
	)

Determinizes a weighted transducer. This version writes the determinized Fst to an output MutableFst. The result will be an equivalent FSt that has the property that no state has two transitions with the same input label. For this algorithm, epsilon transitions are treated as regular symbols (cf. RmEpsilon).

The transducer must be functional. The weights must be (weakly) left divisible (valid for TropicalWeight and LogWeight).

Complexity:

• Determinizable: exponential (polynomial in the size of the output)
• Non-determinizable: does not terminate

The determinizable automata include all unweighted and all acyclic input.

References:

• Mehryar Mohri, "Finite-State Transducers in Language and Speech Processing". Computational Linguistics, 23:2, 1997.

Definition at line 817 of file determinize.h.

uint64 fst::DeterminizeProperties	(	uint64	inprops,
		bool	has_subsequential_label
	)

Properties for a determinized FST.

Definition at line 114 of file properties.cc.

template<class Arc , class V , class ArcFilter >

void fst::DfsVisit	(	const Fst< Arc > &	fst,
		V *	visitor,
		ArcFilter	filter
	)

Performs depth-first visitation. Visitor class argument determines actions and contains any return data. ArcFilter determines arcs that are considered.

Note this is similar to Visit() in visit.h called with a LIFO queue except this version has a Visitor class specialized and augmented for a DFS.

Definition at line 90 of file dfs-visit.h.

template<class Arc , class V >

void fst::DfsVisit	(	const Fst< Arc > &	fst,
		V *	visitor
	)

Definition at line 196 of file dfs-visit.h.

template<class Arc >

void fst::Difference	(	const Fst< Arc > &	ifst1,
		const Fst< Arc > &	ifst2,
		MutableFst< Arc > *	ofst,
		const DifferenceOptions &	opts = DifferenceOptions()
	)

Computes the difference between two FSAs. This version is writes the difference to an output MutableFst. Only strings that are in the first automaton but not in second are retained in the result.

The first argument must be an acceptor; the second argument must be an unweighted, epsilon-free, deterministic acceptor. One of the arguments must be label-sorted.

Complexity: same as Compose.

Caveats: same as Compose.

Definition at line 153 of file difference.h.

template<class W , unsigned int n>

PowerWeight<W, n> fst::Divide	(	const PowerWeight< W, n > &	w1,
		const PowerWeight< W, n > &	w2,
		DivideType	type = DIVIDE_ANY
	)			[inline]

Semiring divide operation.

Definition at line 112 of file power-weight.h.

template<class W1 , class W2 >

ProductWeight<W1, W2> fst::Divide	(	const ProductWeight< W1, W2 > &	w,
		const ProductWeight< W1, W2 > &	v,
		DivideType	typ = DIVIDE_ANY
	)			[inline]

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

template<class T >

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

Definition at line 269 of file float-weight.h.

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

Definition at line 281 of file float-weight.h.

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

Definition at line 287 of file float-weight.h.

template<class X1 , class X2 >

ExpectationWeight<X1, X2> fst::Divide	(	const ExpectationWeight< X1, X2 > &	w,
		const ExpectationWeight< X1, X2 > &	v,
		DivideType	typ = DIVIDE_ANY
	)			[inline]

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

template<class T >

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

Definition at line 395 of file float-weight.h.

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

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

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

Definition at line 413 of file float-weight.h.

template<class T >

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

Defined only for special cases.

Definition at line 508 of file float-weight.h.

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

Definition at line 515 of file float-weight.h.

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

Definition at line 521 of file float-weight.h.

template<class T >

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

Definition at line 150 of file signed-log-weight.h.

template<class W , class K >

SparsePowerWeight<W, K> fst::Divide	(	const SparsePowerWeight< W, K > &	w1,
		const SparsePowerWeight< W, K > &	w2,
		DivideType	type = DIVIDE_ANY
	)			[inline]

Semimodule divide operation.

Definition at line 162 of file sparse-power-weight.h.

template<class W1 , class W2 >

LexicographicWeight<W1, W2> fst::Divide	(	const LexicographicWeight< W1, W2 > &	w,
		const LexicographicWeight< W1, W2 > &	v,
		DivideType	typ = DIVIDE_ANY
	)			[inline]

Definition at line 127 of file lexicographic-weight.h.

template<typename L , StringType S>

StringWeight<L, S> fst::Divide	(	const StringWeight< L, S > &	w1,
		const StringWeight< L, S > &	w2,
		DivideType	typ
	)			[inline]

Default is for left division in the left string and the left restricted string semirings.

Definition at line 435 of file string-weight.h.

template<typename L >

StringWeight<L, STRING_RIGHT> fst::Divide	(	const StringWeight< L, STRING_RIGHT > &	w1,
		const StringWeight< L, STRING_RIGHT > &	w2,
		DivideType	typ
	)			[inline]

Right division in the right string semiring.

Definition at line 460 of file string-weight.h.

template<typename L >

StringWeight<L, STRING_RIGHT_RESTRICT> fst::Divide	(	const StringWeight< L, STRING_RIGHT_RESTRICT > &	w1,
		const StringWeight< L, STRING_RIGHT_RESTRICT > &	w2,
		DivideType	typ
	)			[inline]

Right division in the right restricted string semiring.

Definition at line 485 of file string-weight.h.

template<class W , unsigned int n>

W fst::DotProduct	(	const PowerWeight< W, n > &	w1,
		const PowerWeight< W, n > &	w2
	)			[inline]

Semimodule dot product.

Definition at line 141 of file power-weight.h.

template<class W , class K >

const W& fst::DotProduct	(	const SparsePowerWeight< W, K > &	w1,
		const SparsePowerWeight< W, K > &	w2
	)			[inline]

Semimodule dot product.

Definition at line 173 of file sparse-power-weight.h.

template<typename To , typename From >

To fst::down_cast

(

From *

f

)

[inline]

Downcasting.

Definition at line 64 of file compat.h.

template<class A >

void fst::Encode	(	MutableFst< A > *	fst,
		EncodeMapper< A > *	mapper
	)			[inline]

Complexity: O(nstates + narcs).

Definition at line 448 of file encode.h.

template<class Arc >

void fst::EpsNormalize	(	const Fst< Arc > &	ifst,
		MutableFst< Arc > *	ofst,
		EpsNormalizeType	type = EPS_NORM_INPUT
	)

Returns an equivalent FST that is epsilon-normalized. An acceptor is epsilon-normalized if it is epsilon-removed. A transducer is input epsilon-normalized if additionally if on each path any epsilon input label follows all non-epsilon input labels. Output epsilon-normalized is defined similarly.

The input FST needs to be functional.

References:

• Mehryar Mohri. "Generic epsilon-removal and input epsilon-normalization algorithms for weighted transducers", International Journal of Computer Science, 13(1): 129-143, 2002.

Definition at line 51 of file epsnormalize.h.

template<class Arc >

bool fst::Equal	(	const Fst< Arc > &	fst1,
		const Fst< Arc > &	fst2,
		float	delta = kDelta
	)

Tests if two Fsts have the same states and arcs in the same order.

Definition at line 30 of file equal.h.

template<class Arc >

bool fst::Equivalent	(	const Fst< Arc > &	fst1,
		const Fst< Arc > &	fst2,
		double	delta = kDelta
	)

Equivalence checking algorithm: determines if the two FSTs fst1 and fst2 are equivalent. The input FSTs must be deterministic input-side epsilon-free acceptors, unweighted or with weights over a left semiring. Two acceptors are considered equivalent if they accept exactly the same set of strings (with the same weights).

The algorithm (cf. Aho, Hopcroft and Ullman, "The Design and Analysis of Computer Programs") successively constructs sets of states that can be reached by the same prefixes, starting with a set containing the start states of both acceptors. A disjoint tree forest (the union-find algorithm) is used to represent the sets of states. The algorithm returns 'false' if one of the constructed sets contains both final and non-final states.

Complexity: quasi-linear, i.e. O(n G(n)), where n = |S1| + |S2| is the number of states in both acceptors G(n) is a very slowly growing function that can be approximated by 4 by all practical purposes.

Definition at line 126 of file equivalent.h.

template<class Arc >

void fst::Expand	(	const Fst< Arc > &	ifst,
		const vector< pair< typename Arc::Label, typename Arc::Label > > &	parens,
		MutableFst< Arc > *	ofst,
		bool	connect = true,
		bool	keep_parentheses = false
	)

Expands a pushdown transducer (PDT) encoded as an FST into an FST. This version writes the expanded PDT result to a MutableFst. In the PDT, some transitions are labeled with open or close parentheses. To be interpreted as a PDT, the parens must balance on a path. The open-close parenthesis label pairs are passed in 'parens'. The expansion enforces the parenthesis constraints. The PDT must be expandable as an FST.

Definition at line 319 of file expand.h.

uint64 fst::ExpandProperties

(

uint64

inprops

)

[inline]

Properties for an expanded PDT.

Definition at line 50 of file expand.h.

uint64 fst::FactorWeightProperties

(

uint64

inprops

)

Properties for factored weight FST.

Definition at line 131 of file properties.cc.

template<class Arc >

void fst::FarCompileStrings	(	const vector< string > &	in_fnames,
		const string &	out_fname,
		const string &	fst_type,
		const FarType &	far_type,
		int32	generate_keys,
		FarEntryType	fet,
		FarTokenType	tt,
		const string &	symbols_fname,
		bool	allow_negative_labels,
		bool	file_list_input,
		const string &	key_prefix,
		const string &	key_suffix
	)

Definition at line 128 of file compile-strings.h.

template<class Arc >

void fst::FarCreate	(	const vector< string > &	in_fnames,
		const string &	out_fname,
		const int32	generate_keys,
		const bool	file_list_input,
		const FarType &	far_type,
		const string &	key_prefix,
		const string &	key_suffix
	)

Definition at line 38 of file create.h.

template<class Arc >

void fst::FarExtract	(	const vector< string > &	ifilenames,
		const int32 &	generate_filenames,
		const string &	begin_key,
		const string &	end_key,
		const string &	filename_prefix,
		const string &	filename_suffix
	)

Definition at line 35 of file extract.h.

template<class Arc >

void fst::FarInfo	(	const vector< string > &	filenames,
		const string &	begin_key,
		const string &	end_key,
		const bool	list_fsts
	)

Definition at line 52 of file info.h.

template<class Arc >

void fst::FarPrintStrings	(	const vector< string > &	ifilenames,
		const FarEntryType	entry_type,
		const FarTokenType	far_token_type,
		const string &	begin_key,
		const string &	end_key,
		const bool	print_key,
		const string &	symbols_fname,
		const int32	generate_filenames,
		const string &	filename_prefix,
		const string &	filename_suffix
	)

Definition at line 35 of file print-strings.h.

FarType fst::FarTypeFromString

(

const string &

str

)

Return the 'FarType' value corresponding to a far type name.

string fst::FarTypeToString

(

FarType

type

)

Return the textual name corresponding to a 'FarType;.

template<class A >

A::Weight fst::Final	(	const ExpandedFst< A > &	fst,
		typename A::StateId	s
	)			[inline]

ExpandedFst case - abstract methods.

Definition at line 90 of file expanded-fst.h.

template<class A >

A::Weight fst::Final	(	const MutableFst< A > &	fst,
		typename A::StateId	s
	)			[inline]

MutableFst case - abstract methods.

Definition at line 192 of file mutable-fst.h.

int fst::FstOnceInit	(	FstOnceType *	once,
		void(*)(void)	init
	)			[inline]

Definition at line 37 of file lock.h.

template<class A >

void fst::FstToString	(	const Fst< A > &	fst,
		string *	result
	)

Fst Serialization.

Definition at line 816 of file fst.h.

void fst::Int64ToStr	(	int64	n,
		string *	s
	)

Definition at line 39 of file util.cc.

template<class Arc >

void fst::Intersect	(	const Fst< Arc > &	ifst1,
		const Fst< Arc > &	ifst2,
		MutableFst< Arc > *	ofst,
		const IntersectOptions &	opts = IntersectOptions()
	)

Computes the intersection (Hadamard product) of two FSAs. This version writes the intersection to an output MurableFst. Only strings that are in both automata are retained in the result.

The two arguments must be acceptors. One of the arguments must be label-sorted.

Complexity: same as Compose.

Caveats: same as Compose.

Definition at line 137 of file intersect.h.

template<class Arc >

void fst::Invert

(

MutableFst< Arc > *

fst

)

[inline]

Inverts the transduction corresponding to an FST by exchanging the FST's input and output labels. This version modifies its input.

Complexity:

• Time: O(V + E)
• Space: O(1) where V = # of states and E = # of arcs.

Definition at line 55 of file invert.h.

uint64 fst::InvertProperties

(

uint64

inprops

)

Properties for an inverted FST.

Definition at line 143 of file properties.cc.

bool fst::IsFstHeader	(	istream &	strm,
		const string &	source
	)

Check for Fst magic number in stream, to indicate caller function that the stream content is an Fst header;

Definition at line 105 of file fst.cc.

bool fst::IsSTTable

(

const string &

filename

)

int fst::KeySize

(

const char *

filename

)

Compute the minimal length required to encode each line number as a decimal number

Compute the minimal length required to encode each line number as a decimal number.

uint64 fst::KnownProperties

(

uint64

props

)

[inline]

For a binary property, the bit is always returned set. For a trinary (i.e. two-bit) property, both bits are returned set iff either corresponding input bit is set.

Definition at line 37 of file test-properties.h.

template<class Label >

bool fst::LabelsToUTF8String	(	const std::vector< Label > &	,
		string *
	)

Definition at line 127 of file compat.h.

template<class Label >

bool fst::LabelsToUTF8String	(	const vector< Label > &	labels,
		string *	str
	)

Definition at line 84 of file icu.h.

string fst::LoadArcTypeFromFar

(

const string &

far_fname

)

string fst::LoadArcTypeFromFst

(

const string &

fst_fname

)

template<class T >

T fst::LogExp

(

T

x

)

[inline]

Definition at line 346 of file float-weight.h.

template<class M1 , class M2 >

MatchType fst::LookAheadMatchType	(	const M1 &	m1,
		const M2 &	m2
	)

Identifies and verifies the capabilities of the matcher to be used for lookahead with the composition filters below. This version is passed the matchers.

Definition at line 37 of file lookahead-filter.h.

template<class Arc >

MatchType fst::LookAheadMatchType	(	const Fst< Arc > &	fst1,
		const Fst< Arc > &	fst2
	)

Identifies and verifies the capabilities of the matcher to be used for lookahead with the composition filters below. This version uses the Fst's default matchers.

Definition at line 60 of file lookahead-filter.h.

template<class A , class C >

void fst::Map	(	MutableFst< A > *	fst,
		C *	mapper
	)

Mapper Interface - class determinies how arcs and final weights are mapped.

class Mapper { public: Maps an arc type A to arc type B. B operator()(const A &arc); Specifies final action the mapper requires (see above). The mapper will be passed final weights as arcs of the form A(0, 0, weight, kNoStateId). MapFinalAction FinalAction() const; Specifies input symbol table action the mapper requires (see above). MapSymbolsAction InputSymbolsAction() const; Specifies output symbol table action the mapper requires (see above). MapSymbolsAction OutputSymbolsAction() const; This specifies the known properties of an Fst mapped by this mapper. It takes as argument the input Fst's known properties. uint64 Properties(uint64 props) const; }

The Map functions and classes below will use the FinalAction() method of the mapper to determine how to treat final weights, e.g. whether to add a superfinal state. They will use the Properties() method to set the result Fst properties.

We include a various map versions below. One dimension of variation is whether the mapping mutates its input, writes to a new result Fst, or is an on-the-fly Fst. Another dimension is how we pass the mapper. We allow passing the mapper by pointer for cases that we need to change the state of the user's mapper. This is the case with the encode mapper, which is reused during decoding. We also include map versions that pass the mapper by value or const reference when this suffices. Maps an arc type A using a mapper function object C, passed by pointer. This version modifies its Fst input.

Definition at line 106 of file map.h.

template<class A , class C >

void fst::Map	(	MutableFst< A > *	fst,
		C	mapper
	)

Maps an arc type A using a mapper function object C, passed by value. This version modifies its Fst input.

Definition at line 175 of file map.h.

template<class A , class B , class C >

void fst::Map	(	const Fst< A > &	ifst,
		MutableFst< B > *	ofst,
		C	mapper
	)

Maps an arc type A to an arc type B using mapper function object C, passed by value. This version writes the mapped input Fst to an output MutableFst.

Definition at line 265 of file map.h.

template<class A , class B , class C >

void fst::Map	(	const Fst< A > &	ifst,
		MutableFst< B > *	ofst,
		C *	mapper
	)

Maps an arc type A to an arc type B using mapper function object C, passed by pointer. This version writes the mapped input Fst to an output MutableFst.

Definition at line 184 of file map.h.

template<class Arc >

void fst::Map	(	MutableFst< Arc > *	ofst,
		MapType	map_type,
		float	delta = kDelta,
		typename Arc::Weight	weight_thresh = Arc::Weight::Zero()
	)

Definition at line 1077 of file map.h.

template<class A >

void fst::MergeStates	(	const Partition< typename A::StateId > &	partition,
		MutableFst< A > *	fst
	)

Given a partition and a mutable fst, merge states of Fst inplace (i.e. destructively). Merging works by taking the first state in a class of the partition to be the representative state for the class. Each arc is then reconnected to this state. All states in the class are merged by adding there arcs to the representative state.

Definition at line 453 of file minimize.h.

template<class A >

void fst::Minimize	(	MutableFst< A > *	fst,
		MutableFst< A > *	sfst = 0,
		float	delta = kDelta
	)

In place minimization of deterministic weighted automata and transducers. For transducers, then the 'sfst' argument is not null, the algorithm produces a compact factorization of the minimal transducer.

In the acyclic case, we use an algorithm from Dominique Revuz that is linear in the number of arcs (edges) in the machine. Complexity = O(E)

In the cyclic case, we use the classical hopcroft minimization. Complexity = O(|E|log(|N|)

Definition at line 528 of file minimize.h.

template<class Arc , class RevArc >

void fst::NShortestPath	(	const Fst< RevArc > &	ifst,
		MutableFst< Arc > *	ofst,
		const vector< typename Arc::Weight > &	distance,
		size_t	n,
		float	delta = kDelta,
		typename Arc::Weight	weight_threshold = Arc::Weight::Zero(),
		typename Arc::StateId	state_threshold = kNoStateId
	)

N-Shortest-path algorithm: implements the core n-shortest path algorithm. The output is built REVERSED. See below for versions with more options and not reversed.

'ofst' contains the REVERSE of 'n'-shortest paths in 'ifst'. 'distance' must contain the shortest distance from each state to a final state in 'ifst'. 'delta' is the convergence delta.

The n-shortest paths are the n-lowest weight paths w.r.t. the natural semiring order. The single path that can be read from the ith of at most n transitions leaving the initial state of 'ofst' is the ith shortest path. Disregarding the initial state and initial transitions, The n-shortest paths, in fact, form a tree rooted at the single final state.

The weights need to be left and right distributive (kSemiring) and have the path (kPath) property.

The algorithm is from Mohri and Riley, "An Efficient Algorithm for the n-best-strings problem", ICSLP 2002. The algorithm relies on the shortest-distance algorithm. There are some issues with the pseudo-code as written in the paper (viz., line 11).

IMPLEMENTATION NOTE: The input fst 'ifst' can be a delayed fst and and at any state in its expansion the values of distance vector need only be defined at that time for the states that are known to exist.

Definition at line 256 of file shortest-path.h.

template<class A >

ssize_t fst::NumArcs	(	const ExpandedFst< A > &	fst,
		typename A::StateId	s
	)			[inline]

Definition at line 95 of file expanded-fst.h.

template<class A >

ssize_t fst::NumArcs	(	const MutableFst< A > &	fst,
		typename A::StateId	s
	)			[inline]

Definition at line 197 of file mutable-fst.h.

template<class A >

ssize_t fst::NumInputEpsilons	(	const ExpandedFst< A > &	fst,
		typename A::StateId	s
	)			[inline]

Definition at line 100 of file expanded-fst.h.

template<class A >

ssize_t fst::NumInputEpsilons	(	const MutableFst< A > &	fst,
		typename A::StateId	s
	)			[inline]

Definition at line 202 of file mutable-fst.h.

template<class A >

ssize_t fst::NumOutputEpsilons	(	const ExpandedFst< A > &	fst,
		typename A::StateId	s
	)			[inline]

Definition at line 105 of file expanded-fst.h.

template<class A >

ssize_t fst::NumOutputEpsilons	(	const MutableFst< A > &	fst,
		typename A::StateId	s
	)			[inline]

Definition at line 207 of file mutable-fst.h.

bool fst::operator!=	(	const FloatWeightTpl< double > &	w1,
		const FloatWeightTpl< double > &	w2
	)			[inline]

Definition at line 130 of file float-weight.h.

bool fst::operator!=	(	const FloatWeightTpl< float > &	w1,
		const FloatWeightTpl< float > &	w2
	)			[inline]

Definition at line 135 of file float-weight.h.

template<class W , class K >

bool fst::operator!=	(	const SparseTupleWeight< W, K > &	w1,
		const SparseTupleWeight< W, K > &	w2
	)			[inline]

Definition at line 326 of file sparse-tuple-weight.h.

template<typename L , StringType S>

bool fst::operator!=	(	const StringWeight< L, S > &	w1,
		const StringWeight< L, S > &	w2
	)			[inline]

Definition at line 307 of file string-weight.h.

template<class W , unsigned int n>

bool fst::operator!=	(	const TupleWeight< W, n > &	w1,
		const TupleWeight< W, n > &	w2
	)			[inline]

Definition at line 245 of file tuple-weight.h.

template<class W1 , class W2 >

bool fst::operator!=	(	const PairWeight< W1, W2 > &	w1,
		const PairWeight< W1, W2 > &	w2
	)			[inline]

Definition at line 200 of file pair-weight.h.

template<class T >

bool fst::operator!=	(	const FloatWeightTpl< T > &	w1,
		const FloatWeightTpl< T > &	w2
	)			[inline]

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

template<class W1 , class W2 >

ostream& fst::operator<<	(	ostream &	strm,
		const PairWeight< W1, W2 > &	w
	)			[inline]

Definition at line 215 of file pair-weight.h.

template<class T >

ostream& fst::operator<<	(	ostream &	strm,
		const FloatWeightTpl< T > &	w
	)			[inline]

Definition at line 148 of file float-weight.h.

template<typename T >

ostream& fst::operator<<	(	ostream &	strm,
		const IntervalSet< T > &	s
	)

Definition at line 362 of file interval-set.h.

template<class W , class K >

ostream& fst::operator<<	(	ostream &	strm,
		const SparseTupleWeight< W, K > &	w
	)			[inline]

Definition at line 332 of file sparse-tuple-weight.h.

template<typename L , StringType S>

ostream& fst::operator<<	(	ostream &	strm,
		const StringWeight< L, S > &	w
	)			[inline]

Definition at line 320 of file string-weight.h.

template<class W , unsigned int n>

ostream& fst::operator<<	(	ostream &	strm,
		const TupleWeight< W, n > &	w
	)			[inline]

Definition at line 265 of file tuple-weight.h.

template<class S , class P >

bool fst::operator==	(	const ReplaceStateTuple< S, P > &	x,
		const ReplaceStateTuple< S, P > &	y
	)			[inline]

Equality of replace state tuples.

Definition at line 95 of file replace.h.

template<class T >

bool fst::operator==	(	const SignedLogWeightTpl< T > &	w1,
		const SignedLogWeightTpl< T > &	w2
	)			[inline]

Definition at line 183 of file signed-log-weight.h.

template<class W , class K >

bool fst::operator==	(	const SparseTupleWeight< W, K > &	w1,
		const SparseTupleWeight< W, K > &	w2
	)			[inline]

Definition at line 297 of file sparse-tuple-weight.h.

template<typename S , typename F >

bool fst::operator==	(	const ComposeStateTuple< S, F > &	x,
		const ComposeStateTuple< S, F > &	y
	)			[inline]

Equality of composition state tuples.

Definition at line 479 of file state-table.h.

template<typename L , StringType S>

bool fst::operator==	(	const StringWeight< L, S > &	w1,
		const StringWeight< L, S > &	w2
	)			[inline]

NB: This needs to be uncommented only if default fails for this the impl.

template <typename L, StringType S> inline StringWeight<L, S> &StringWeight<L, S>::operator=(const StringWeight<L, S> &w) { if (this != &w) { Clear(); for (StringWeightIterator<L, S> iter(w); !iter.Done(); iter.Next()) PushBack(iter.Value()); } return *this; }

Definition at line 291 of file string-weight.h.

template<typename S , typename K >

bool fst::operator==	(	const PdtStateTuple< S, K > &	x,
		const PdtStateTuple< S, K > &	y
	)			[inline]

Equality of PDT state tuples.

Definition at line 150 of file pdt.h.

template<class W , unsigned int n>

bool fst::operator==	(	const TupleWeight< W, n > &	w1,
		const TupleWeight< W, n > &	w2
	)			[inline]

Definition at line 236 of file tuple-weight.h.

template<class T >

bool fst::operator==	(	const FloatWeightTpl< T > &	w1,
		const FloatWeightTpl< T > &	w2
	)			[inline]

Definition at line 105 of file float-weight.h.

bool fst::operator==	(	const FloatWeightTpl< double > &	w1,
		const FloatWeightTpl< double > &	w2
	)			[inline]

Definition at line 114 of file float-weight.h.

bool fst::operator==	(	const FloatWeightTpl< float > &	w1,
		const FloatWeightTpl< float > &	w2
	)			[inline]

Definition at line 119 of file float-weight.h.

template<class W1 , class W2 >

bool fst::operator==	(	const PairWeight< W1, W2 > &	w,
		const PairWeight< W1, W2 > &	v
	)			[inline]

Definition at line 194 of file pair-weight.h.

template<class T >

istream& fst::operator>>	(	istream &	strm,
		FloatWeightTpl< T > &	w
	)			[inline]

Definition at line 160 of file float-weight.h.

template<class W , class K >

istream & fst::operator>>	(	istream &	strm,
		SparseTupleWeight< W, K > &	w
	)			[inline]

Definition at line 365 of file sparse-tuple-weight.h.

template<typename L , StringType S>

istream& fst::operator>>	(	istream &	strm,
		StringWeight< L, S > &	w
	)			[inline]

Definition at line 338 of file string-weight.h.

template<class W , unsigned int n>

istream & fst::operator>>	(	istream &	strm,
		TupleWeight< W, n > &	w
	)			[inline]

Definition at line 288 of file tuple-weight.h.

template<class W1 , class W2 >

istream & fst::operator>>	(	istream &	strm,
		PairWeight< W1, W2 > &	w
	)			[inline]

Definition at line 229 of file pair-weight.h.

template<class W , unsigned int n>

PowerWeight<W, n> fst::Plus	(	const PowerWeight< W, n > &	w1,
		const PowerWeight< W, n > &	w2
	)			[inline]

Semiring plus operation.

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

template<class W1 , class W2 >

ProductWeight<W1, W2> fst::Plus	(	const ProductWeight< W1, W2 > &	w,
		const ProductWeight< W1, W2 > &	v
	)			[inline]

Definition at line 83 of file product-weight.h.

template<typename L , StringType S>

StringWeight<L, S> fst::Plus	(	const StringWeight< L, S > &	w1,
		const StringWeight< L, S > &	w2
	)			[inline]

Default is for the restricted left and right semirings. String equality is required (for non-Zero() input. This restriction is used in e.g. Determinize to ensure functional input.

Definition at line 365 of file string-weight.h.

template<class T >

TropicalWeightTpl<T> fst::Plus	(	const TropicalWeightTpl< T > &	w1,
		const TropicalWeightTpl< T > &	w2
	)			[inline]

Definition at line 231 of file float-weight.h.

TropicalWeightTpl<float> fst::Plus	(	const TropicalWeightTpl< float > &	w1,
		const TropicalWeightTpl< float > &	w2
	)			[inline]

Definition at line 236 of file float-weight.h.

TropicalWeightTpl<double> fst::Plus	(	const TropicalWeightTpl< double > &	w1,
		const TropicalWeightTpl< double > &	w2
	)			[inline]

Definition at line 241 of file float-weight.h.

template<typename L >

StringWeight<L, STRING_LEFT> fst::Plus	(	const StringWeight< L, STRING_LEFT > &	w1,
		const StringWeight< L, STRING_LEFT > &	w2
	)			[inline]

Longest common prefix for left string semiring.

Definition at line 382 of file string-weight.h.

template<class T >

LogWeightTpl<T> fst::Plus	(	const LogWeightTpl< T > &	w1,
		const LogWeightTpl< T > &	w2
	)			[inline]

Definition at line 349 of file float-weight.h.

template<class X1 , class X2 >

ExpectationWeight<X1, X2> fst::Plus	(	const ExpectationWeight< X1, X2 > &	w,
		const ExpectationWeight< X1, X2 > &	v
	)			[inline]

Definition at line 109 of file expectation-weight.h.

LogWeightTpl<float> fst::Plus	(	const LogWeightTpl< float > &	w1,
		const LogWeightTpl< float > &	w2
	)			[inline]

Definition at line 362 of file float-weight.h.

LogWeightTpl<double> fst::Plus	(	const LogWeightTpl< double > &	w1,
		const LogWeightTpl< double > &	w2
	)			[inline]

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

template<class T >

MinMaxWeightTpl<T> fst::Plus	(	const MinMaxWeightTpl< T > &	w1,
		const MinMaxWeightTpl< T > &	w2
	)			[inline]

Min.

Definition at line 474 of file float-weight.h.

MinMaxWeightTpl<float> fst::Plus	(	const MinMaxWeightTpl< float > &	w1,
		const MinMaxWeightTpl< float > &	w2
	)			[inline]

Definition at line 479 of file float-weight.h.

MinMaxWeightTpl<double> fst::Plus	(	const MinMaxWeightTpl< double > &	w1,
		const MinMaxWeightTpl< double > &	w2
	)			[inline]

Definition at line 484 of file float-weight.h.

template<class W1 , class W2 >

LexicographicWeight<W1, W2> fst::Plus	(	const LexicographicWeight< W1, W2 > &	w,
		const LexicographicWeight< W1, W2 > &	v
	)			[inline]

Definition at line 108 of file lexicographic-weight.h.

template<class T >

SignedLogWeightTpl<T> fst::Plus	(	const SignedLogWeightTpl< T > &	w1,
		const SignedLogWeightTpl< T > &	w2
	)			[inline]

Definition at line 102 of file signed-log-weight.h.

template<class W , class K >

SparsePowerWeight<W, K> fst::Plus	(	const SparsePowerWeight< W, K > &	w1,
		const SparsePowerWeight< W, K > &	w2
	)			[inline]

Semimodule plus operation.

Definition at line 142 of file sparse-power-weight.h.

template<typename L >

StringWeight<L, STRING_RIGHT> fst::Plus	(	const StringWeight< L, STRING_RIGHT > &	w1,
		const StringWeight< L, STRING_RIGHT > &	w2
	)			[inline]

Longest common suffix for right string semiring.

Definition at line 401 of file string-weight.h.

template<class W >

W fst::Power	(	W	w,
		size_t	n
	)

Power is the iterated product for arbitrary semirings such that Power(w, 0) is One() for the semiring, and Power(w, n) = Times(Power(w, n-1), w)

Definition at line 147 of file weight.h.

template<class A >

void fst::PrintFstInfo	(	const FstInfo< A > &	fstinfo,
		bool	pipe = false
	)

Definition at line 218 of file info-impl.h.

template<class A >

void fst::PrintPdtInfo

(

const PdtInfo< A > &

pdtinfo

)

Definition at line 144 of file info.h.

template<class Arc >

void fst::Project	(	MutableFst< Arc > *	fst,
		ProjectType	project_type
	)			[inline]

Projects an FST onto its domain or range by either copying each arcs' input label to the output label or vice versa. This version modifies its input.

Complexity:

• Time: O(V + E)
• Space: O(1) where V = # of states and E = # of arcs.

Definition at line 76 of file project.h.

uint64 fst::ProjectProperties	(	uint64	inprops,
		bool	project_input
	)

Properties for a projected FST.

Definition at line 181 of file properties.cc.

template<class Arc , class ArcFilter >

void fst::Prune	(	MutableFst< Arc > *	fst,
		const PruneOptions< Arc, ArcFilter > &	opts
	)

Pruning algorithm: this version modifies its input and it takes an options class as an argment. Delete states and arcs in 'fst' that do not belong to a successful path whose weight is no more than the weight of the shortest path Times() 'opts.weight_threshold'. When 'opts.state_threshold != kNoStateId', the resulting transducer will restricted further to have at most 'opts.state_threshold' states. Weights need to be commutative and have the path property. The weight 'w' of any cycle needs to be bounded, i.e., 'Plus(w, W::One()) = One()'.

Definition at line 99 of file prune.h.

template<class Arc >

void fst::Prune	(	MutableFst< Arc > *	fst,
		typename Arc::Weight	weight_threshold,
		typename Arc::StateId	state_threshold = kNoStateId,
		double	delta = kDelta
	)

Pruning algorithm: this version modifies its input and simply takes the pruning threshold as an argument. Delete states and arcs in 'fst' that do not belong to a successful path whose weight is no more than the weight of the shortest path Times() 'weight_threshold'. When 'state_threshold != kNoStateId', the resulting transducer will be restricted further to have at most 'opts.state_threshold' states. Weights need to be commutative and have the path property. The weight 'w' of any cycle needs to be bounded, i.e., 'Plus(w, W::One()) = One()'.

Definition at line 193 of file prune.h.

template<class Arc , class ArcFilter >

void fst::Prune	(	const Fst< Arc > &	ifst,
		MutableFst< Arc > *	ofst,
		const PruneOptions< Arc, ArcFilter > &	opts
	)

Pruning algorithm: this version writes the pruned input Fst to an output MutableFst and it takes an options class as an argument. 'ofst' contains states and arcs that belong to a successful path in 'ifst' whose weight is no more than the weight of the shortest path Times() 'opts.weight_threshold'. When 'opts.state_threshold != kNoStateId', 'ofst' will be restricted further to have at most 'opts.state_threshold' states. Weights need to be commutative and have the path property. The weight 'w' of any cycle needs to be bounded, i.e., 'Plus(w, W::One()) = One()'.

Definition at line 213 of file prune.h.

template<class Arc >

void fst::Prune	(	const Fst< Arc > &	ifst,
		MutableFst< Arc > *	ofst,
		typename Arc::Weight	weight_threshold,
		typename Arc::StateId	state_threshold = kNoStateId,
		float	delta = kDelta
	)

Pruning algorithm: this version writes the pruned input Fst to an output MutableFst and simply takes the pruning threshold as an argument. 'ofst' contains states and arcs that belong to a successful path in 'ifst' whose weight is no more than the weight of the shortest path Times() 'weight_threshold'. When 'state_threshold != kNoStateId', 'ofst' will be restricted further to have at most 'opts.state_threshold' states. Weights need to be commutative and have the path property. The weight 'w' of any cycle needs to be bounded, i.e., 'Plus(w, W::One()) = W::One()'.

Definition at line 320 of file prune.h.

template<class Arc >

void fst::Push	(	MutableFst< Arc > *	fst,
		ReweightType	type,
		float	delta = kDelta,
		bool	remove_total_weight = false
	)

namespace internal

Pushes the weights in FST in the direction defined by TYPE. If pushing towards the initial state, the sum of the weight of the outgoing transitions and final weight at a non-initial state is equal to One() in the resulting machine. If pushing towards the final state, the same property holds on the reverse machine.

Weight needs to be left distributive when pushing towards the initial state and right distributive when pushing towards the final states.

Definition at line 95 of file push.h.

template<class Arc , ReweightType rtype>

void fst::Push	(	const Fst< Arc > &	ifst,
		MutableFst< Arc > *	ofst,
		uint32	ptype,
		float	delta = kDelta
	)

OFST obtained from IFST by pushing weights and/or labels according to PTYPE in the direction defined by RTYPE. Weight needs to be left distributive when pushing weights towards the initial state and right distributive when pushing weights towards the final states.

Definition at line 121 of file push.h.

template<class Arc , class ArcSelector >

bool fst::RandEquivalent	(	const Fst< Arc > &	fst1,
		const Fst< Arc > &	fst2,
		ssize_t	num_paths,
		float	delta,
		const RandGenOptions< ArcSelector > &	opts
	)

Test if two FSTs are equivalent by randomly generating 'num_paths' paths (as specified by the RandGenOptions 'opts') in these FSTs.

For each randomly generated path, the algorithm computes for each of the two FSTs the sum of the weights of all the successful paths sharing the same input and output labels as the considered randomly generated path and checks that these two values are within 'delta'.

Definition at line 43 of file randequivalent.h.

template<class Arc >

bool fst::RandEquivalent	(	const Fst< Arc > &	fst1,
		const Fst< Arc > &	fst2,
		ssize_t	num_paths,
		float	delta = kDelta,
		int	seed = time(0),
		int	path_length = INT_MAX
	)

Test if two FSTs are equivalent by randomly generating 'num_paths' paths of length no more than 'path_length' using the seed 'seed' in these FSTs.

Definition at line 107 of file randequivalent.h.

template<class Arc >

void fst::RandGen	(	const Fst< Arc > &	ifst,
		MutableFst< Arc > *	ofst
	)

Randomly generate a path through an FST with the uniform distribution over the transitions.

Definition at line 208 of file randgen.h.

template<class Arc , class ArcSelector >

void fst::RandGen	(	const Fst< Arc > &	ifst,
		MutableFst< Arc > *	ofst,
		const RandGenOptions< ArcSelector > &	opts
	)

Randomly generate paths through an FST; details controlled by RandGenOptions.

Definition at line 164 of file randgen.h.

fst::READ_POD_TYPE

(

float

)

fst::READ_POD_TYPE

(

char

)

fst::READ_POD_TYPE

(

double

)

fst::READ_POD_TYPE

(

int

)

fst::READ_POD_TYPE

(

long

)

fst::READ_POD_TYPE

(

unsigned long

long

)

fst::READ_POD_TYPE

(

unsigned

char

)

fst::READ_POD_TYPE

(

short

)

fst::READ_POD_TYPE

(

bool

)

fst::READ_POD_TYPE

(

signed

char

)

fst::READ_STL_ASSOC_TYPE

(

unordered_set

)

fst::READ_STL_ASSOC_TYPE

(

map

)

fst::READ_STL_ASSOC_TYPE

(

set

)

fst::READ_STL_ASSOC_TYPE

(

unordered_map

)

fst::READ_STL_SEQ_TYPE

(

vector

)

fst::READ_STL_SEQ_TYPE

(

list

)

template<typename Label >

void fst::ReadLabelPairs	(	const string &	filename,
		vector< pair< Label, Label > > *	pairs,
		bool	allow_negative = false
	)

Utilities for reading/writing label pairs.

Definition at line 262 of file util.h.

template<class H >

bool fst::ReadSTTableHeader	(	const string &	filename,
		H *	header
	)

String-to-type table header reading function template on the entry header type 'H' having a member function: Read(istream &strm, const string &filename); Checks that 'filename' is an STTable and call the H::Read() on the last entry in the STTable.

Definition at line 289 of file sttable.h.

template<typename S , typename T >

istream& fst::ReadType	(	istream &	strm,
		pair< S, T > *	p
	)			[inline]

Pair case.

Definition at line 94 of file util.h.

template<typename T >

istream& fst::ReadType	(	istream &	strm,
		T *	t
	)			[inline]

Read some types from an input stream.

UTILITIES FOR TYPE I/O Generic case.

Definition at line 54 of file util.h.

istream& fst::ReadType	(	istream &	strm,
		string *	s
	)			[inline]

String case.

Definition at line 80 of file util.h.

template<typename S , typename T >

istream& fst::ReadType	(	istream &	strm,
		pair< const S, T > *	p
	)			[inline]

Definition at line 101 of file util.h.

fst::REGISTER_FST	(	ConstFst	,
		CustomArc
	)

fst::REGISTER_FST	(	EditFst	,
		StdArc
	)

fst::REGISTER_FST	(	ConstFst	,
		StdArc
	)

fst::REGISTER_FST	(	VectorFst	,
		CustomArc
	)

fst::REGISTER_FST	(	VectorFst	,
		StdArc
	)

Register VectorFst, ConstFst and EditFst for common arcs types.

template<class A >

void fst::Relabel	(	MutableFst< A > *	fst,
		const vector< pair< typename A::Label, typename A::Label > > &	ipairs,
		const vector< pair< typename A::Label, typename A::Label > > &	opairs
	)

Relabels either the input labels or output labels. The old to new labels are specified using a vector of pair<Label,Label>. Any label associations not specified are assumed to be identity mapping.

Parameters:

	fst	input fst, must be mutable
	ipairs	vector of input label pairs indicating old to new mapping
	opairs	vector of output label pairs indicating old to new mapping

Definition at line 49 of file relabel.h.

template<class A >

void fst::Relabel	(	MutableFst< A > *	fst,
		const SymbolTable *	new_isymbols,
		const SymbolTable *	new_osymbols
	)

Relabels either the input labels or output labels. The old to new labels mappings are specified using an input Symbol set. Any label associations not specified are assumed to be identity mapping.

Parameters:

	fst	input fst, must be mutable
	new_isymbols	symbol set indicating new mapping of input symbols
	new_osymbols	symbol set indicating new mapping of output symbols

Definition at line 105 of file relabel.h.

template<class A >

void fst::Relabel	(	MutableFst< A > *	fst,
		const SymbolTable *	old_isymbols,
		const SymbolTable *	new_isymbols,
		bool	attach_new_isymbols,
		const SymbolTable *	old_osymbols,
		const SymbolTable *	new_osymbols,
		bool	attach_new_osymbols
	)

Definition at line 114 of file relabel.h.

uint64 fst::RelabelProperties

(

uint64

inprops

)

Properties for a relabeled FST.

Definition at line 293 of file properties.cc.

template<class Label >

SymbolTable* fst::RelabelSymbolTable	(	const SymbolTable *	table,
		const vector< pair< Label, Label > > &	pairs
	)

Relabels a symbol table as specified by the input vector of pairs (old label, new label). The new symbol table only retains symbols for which a relabeling is *explicitely* specified. TODO(allauzen): consider adding options to allow for some form of implicit identity relabeling.

Definition at line 490 of file symbol-table.h.

template<class Arc >

void fst::Replace	(	const vector< pair< typename Arc::Label, const Fst< Arc > * > > &	ifst_array,
		MutableFst< Arc > *	ofst,
		typename Arc::Label	root
	)

Definition at line 1234 of file replace.h.

template<class Arc >

void fst::Replace	(	const vector< pair< typename Arc::Label, const Fst< Arc > * > > &	ifst_array,
		MutableFst< Arc > *	ofst,
		vector< pair< typename Arc::Label, typename Arc::Label > > *	parens,
		typename Arc::Label	root
	)

Builds a pushdown transducer (PDT) from an RTN specification identical to that in fst/lib/replace.h. The result is a PDT encoded as the FST 'ofst' where some transitions are labeled with open or close parentheses. To be interpreted as a PDT, the parens must balance on a path (see PdtExpand()). The open/close parenthesis label pairs are returned in 'parens'.

Definition at line 47 of file replace.h.

template<class Arc >

void fst::Replace	(	const vector< pair< typename Arc::Label, const Fst< Arc > * > > &	ifst_array,
		MutableFst< Arc > *	ofst,
		typename Arc::Label	root,
		bool	epsilon_on_replace
	)

// Recursivively replaces arcs in the root Fst with other Fsts. This version writes the result of replacement to an output MutableFst.

Replace supports replacement of arcs in one Fst with another Fst. This replacement is recursive. Replace takes an array of Fst(s). One Fst represents the root (or topology) machine. The root Fst refers to other Fsts by recursively replacing arcs labeled as non-terminals with the matching non-terminal Fst. Currently Replace uses the output symbols of the arcs to determine whether the arc is a non-terminal arc or not. A non-terminal can be any label that is not a non-zero terminal label in the output alphabet. Note that input argument is a vector of pair<>. These correspond to the tuple of non-terminal Label and corresponding Fst.

Definition at line 1224 of file replace.h.

uint64 fst::ReplaceProperties	(	const vector< uint64 > &	inprops,
		ssize_t	root,
		bool	epsilon_on_replace,
		bool	no_empty_fst
	)

Properties for a replace FST.

Definition at line 231 of file properties.cc.

template<class Arc , class RevArc >

void fst::Reverse	(	const Fst< Arc > &	ifst,
		MutableFst< RevArc > *	ofst
	)

Reverses an FST. The reversed result is written to an output MutableFst. If A transduces string x to y with weight a, then the reverse of A transduces the reverse of x to the reverse of y with weight a.Reverse().

Typically, a = a.Reverse() and Arc = RevArc (e.g. for TropicalWeight or LogWeight). In general, e.g. when the weights only form a left or right semiring, the output arc type must match the input arc type except having the reversed Weight type.

Definition at line 42 of file reverse.h.

template<class Arc , class RevArc >

void fst::Reverse	(	const Fst< Arc > &	ifst,
		const vector< pair< typename Arc::Label, typename Arc::Label > > &	parens,
		MutableFst< RevArc > *	ofst
	)

Reverses a pushdown transducer (PDT) encoded as an FST.

Definition at line 38 of file reverse.h.

uint64 fst::ReverseProperties

(

uint64

inprops

)

Properties for a reversed FST. (the superinitial state limits this set).

Definition at line 306 of file properties.cc.

template<class Arc >

void fst::Reweight	(	MutableFst< Arc > *	fst,
		const vector< typename Arc::Weight > &	potential,
		ReweightType	type
	)

Reweight FST according to the potentials defined by the POTENTIAL vector in the direction defined by TYPE. Weight needs to be left distributive when reweighting towards the initial state and right distributive when reweighting towards the final states.

An arc of weight w, with an origin state of potential p and destination state of potential q, is reweighted by p when reweighting towards the initial state and by pw/q when reweighting towards the final states.

Definition at line 42 of file reweight.h.

uint64 fst::ReweightProperties

(

uint64

inprops

)

Properties for re-weighted FST.

Definition at line 315 of file properties.cc.

template<class Arc , class Queue >

void fst::RmEpsilon	(	MutableFst< Arc > *	fst,
		vector< typename Arc::Weight > *	distance,
		const RmEpsilonOptions< Arc, Queue > &	opts
	)

Removes epsilon-transitions (when both the input and output label are an epsilon) from a transducer. The result will be an equivalent FST that has no such epsilon transitions. This version modifies its input. It allows fine control via the options argument; see below for a simpler interface.

The vector 'distance' will be used to hold the shortest distances during the epsilon-closure computation. The state queue discipline and convergence delta are taken in the options argument.

Definition at line 224 of file rmepsilon.h.

template<class Arc >

void fst::RmEpsilon	(	MutableFst< Arc > *	fst,
		bool	connect = true,
		typename Arc::Weight	weight_threshold = Arc::Weight::Zero(),
		typename Arc::StateId	state_threshold = kNoStateId,
		float	delta = kDelta
	)

Removes epsilon-transitions (when both the input and output label are an epsilon) from a transducer. The result will be an equivalent FST that has no such epsilon transitions. This version modifies its input. It has a simplified interface; see above for a version that allows finer control.

Complexity:

• Time:
  • Unweighted: O(V2 + V E)
  • Acyclic: O(V2 + V E)
  • Tropical semiring: O(V2 log V + V E)
  • General: exponential
• Space: O(V E) where V = # of states visited, E = # of arcs.

References:

• Mehryar Mohri. Generic Epsilon-Removal and Input Epsilon-Normalization Algorithms for Weighted Transducers, "International Journal of Computer Science", 13(1):129-143 (2002).

Definition at line 313 of file rmepsilon.h.

uint64 fst::RmEpsilonProperties	(	uint64	inprops,
		bool	delayed = false
	)

Properties for an epsilon-removed FST.

Definition at line 322 of file properties.cc.

template<class A >

void fst::RmFinalEpsilon

(

MutableFst< A > *

fst

)

Definition at line 36 of file rmfinalepsilon.h.

template<typename Weight >

uint64 fst::SetFinalProperties	(	uint64	inprops,
		Weight	old_weight,
		Weight	new_weight
	)

Definitions of template functions.

Definition at line 367 of file properties.h.

uint64 fst::SetStartProperties

(

uint64

inprops

)

[inline]

Definitions of inlined functions.

PROPERTY FUNCTIONS and STRING NAMES (defined in properties.cc) Below are functions for getting property bit vectors when executing mutating fst operations.

Definition at line 339 of file properties.h.

template<class Arc , class Queue , class ArcFilter >

void fst::ShortestDistance	(	const Fst< Arc > &	fst,
		vector< typename Arc::Weight > *	distance,
		const ShortestDistanceOptions< Arc, Queue, ArcFilter > &	opts
	)

Shortest-distance algorithm: this version allows fine control via the options argument. See below for a simpler interface.

This computes the shortest distance from the 'opts.source' state to each visited state S and stores the value in the 'distance' vector. An unvisited state S has distance Zero(), which will be stored in the 'distance' vector if S is less than the maximum visited state. The state queue discipline, arc filter, and convergence delta are taken in the options argument. The weights must must be right distributive and k-closed (i.e., 1 + x + x^2 + ... + x^(k +1) = 1 + x + x^2 + ... + x^k).

The algorithm is from Mohri, "Semiring Framweork and Algorithms for Shortest-Distance Problems", Journal of Automata, Languages and Combinatorics 7(3):321-350, 2002. The complexity of algorithm depends on the properties of the semiring and the queue discipline used. Refer to the paper for more details.

Definition at line 221 of file shortest-distance.h.

template<class Arc >

void fst::ShortestDistance	(	const Fst< Arc > &	fst,
		vector< typename Arc::Weight > *	distance,
		bool	reverse = false,
		float	delta = kDelta
	)

Shortest-distance algorithm: simplified interface. See above for a version that allows finer control.

If 'reverse' is false, this computes the shortest distance from the initial state to each state S and stores the value in the 'distance' vector. If 'reverse' is true, this computes the shortest distance from each state to the final states. An unvisited state S has distance Zero(), which will be stored in the 'distance' vector if S is less than the maximum visited state. The state queue discipline is automatically-selected.

The weights must must be right (left) distributive if reverse is false (true) and k-closed (i.e., 1 + x + x^2 + ... + x^(k +1) = 1 + x + x^2 + ... + x^k).

The algorithm is from Mohri, "Semiring Framweork and Algorithms for Shortest-Distance Problems", Journal of Automata, Languages and Combinatorics 7(3):321-350, 2002. The complexity of algorithm depends on the properties of the semiring and the queue discipline used. Refer to the paper for more details.

Definition at line 252 of file shortest-distance.h.

template<class Arc >

Arc::Weight fst::ShortestDistance

(

const Fst< Arc > &

fst

)

Return the sum of the weight of all successful paths in an FST, i.e., the shortest-distance from the initial state to the final states.

Definition at line 289 of file shortest-distance.h.

template<class Arc >

void fst::ShortestPath	(	const Fst< Arc > &	ifst,
		MutableFst< Arc > *	ofst,
		size_t	n = 1,
		bool	unique = false,
		bool	first_path = false,
		typename Arc::Weight	weight_threshold = Arc::Weight::Zero(),
		typename Arc::StateId	state_threshold = kNoStateId
	)

Shortest-path algorithm: simplified interface. See above for a version that allows finer control.

'ofst' contains the 'n'-shortest paths in 'ifst'. The queue discipline is automatically selected. When 'unique' == true, only paths with distinct input labels are returned.

The n-shortest paths are the n-lowest weight paths w.r.t. the natural semiring order. The single path that can be read from the ith of at most n transitions leaving the initial state of 'ofst' is the ith best path.

The weights need to be right distributive and have the path (kPath) property.

Definition at line 451 of file shortest-path.h.

template<class Arc >

void fst::ShortestPath	(	const Fst< Arc > &	ifst,
		const vector< pair< typename Arc::Label, typename Arc::Label > > &	parens,
		MutableFst< Arc > *	ofst
	)

Definition at line 757 of file shortest-path.h.

template<class Arc , class Queue >

void fst::ShortestPath	(	const Fst< Arc > &	ifst,
		const vector< pair< typename Arc::Label, typename Arc::Label > > &	parens,
		MutableFst< Arc > *	ofst,
		const PdtShortestPathOptions< Arc, Queue > &	opts
	)

Definition at line 747 of file shortest-path.h.

template<class Arc , class Queue , class ArcFilter >

void fst::ShortestPath	(	const Fst< Arc > &	ifst,
		MutableFst< Arc > *	ofst,
		vector< typename Arc::Weight > *	distance,
		ShortestPathOptions< Arc, Queue, ArcFilter > &	opts
	)

N-Shortest-path algorithm: this version allow fine control via the otpions argument. See below for a simpler interface.

'ofst' contains the n-shortest paths in 'ifst'. 'distance' returns the shortest distances from the source state to each state in 'ifst'. 'opts' is used to specify options such as the number of paths to return, whether they need to have distinct input strings, the queue discipline, the arc filter and the convergence delta.

The n-shortest paths are the n-lowest weight paths w.r.t. the natural semiring order. The single path that can be read from the ith of at most n transitions leaving the initial state of 'ofst' is the ith shortest path. Disregarding the initial state and initial transitions, The n-shortest paths, in fact, form a tree rooted at the single final state. The weights need to be right distributive and have the path (kPath) property. They need to be left distributive as well for nshortest > 1.

The algorithm is from Mohri and Riley, "An Efficient Algorithm for the n-best-strings problem", ICSLP 2002. The algorithm relies on the shortest-distance algorithm. There are some issues with the pseudo-code as written in the paper (viz., line 11).

Definition at line 387 of file shortest-path.h.

uint64 fst::ShortestPathProperties

(

uint64

props

)

Properties for shortest path. This function computes how the properties of the output of shortest path need to be updated, given that 'props' is already known.

Definition at line 339 of file properties.cc.

template<class Arc , class Queue , class ArcFilter >

void fst::SingleShortestPath	(	const Fst< Arc > &	ifst,
		MutableFst< Arc > *	ofst,
		vector< typename Arc::Weight > *	distance,
		ShortestPathOptions< Arc, Queue, ArcFilter > &	opts
	)

Shortest-path algorithm: normally not called directly; prefer 'ShortestPath' below with n=1. 'ofst' contains the shortest path in 'ifst'. 'distance' returns the shortest distances from the source state to each state in 'ifst'. 'opts' is used to specify options such as the queue discipline, the arc filter and delta.

The shortest path is the lowest weight path w.r.t. the natural semiring order.

The weights need to be right distributive and have the path (kPath) property.

Definition at line 77 of file shortest-path.h.

template<class W , class K , class M >

void fst::SparseTupleWeightMap	(	SparseTupleWeight< W, K > *	ret,
		const SparseTupleWeight< W, K > &	w1,
		const SparseTupleWeight< W, K > &	w2,
		const M &	operator_mapper
	)			[inline]

Definition at line 267 of file sparse-tuple-weight.h.

void fst::SplitToVector	(	char *	full,
		const char *	delim,
		vector< char * > *	vec,
		bool	omit_empty_strings
	)

Definition at line 32 of file compat.cc.

void fst::SplitToVector	(	char *	line,
		const char *	delim,
		std::vector< char * > *	vec,
		bool	omit_empty_strings
	)

template<class Arc >

void fst::StateSort	(	MutableFst< Arc > *	fst,
		const vector< typename Arc::StateId > &	order
	)

Sorts the input states of an FST, modifying it. ORDER[i] gives the the state Id after sorting that corresponds to state Id i before sorting. ORDER must be a permutation of FST's states ID sequence: (0, 1, 2, ..., fst->NumStates() - 1).

Definition at line 37 of file statesort.h.

template<typename S , typename T >

void fst::StlReserve	(	vector< S, T > *	c,
		int64	n
	)

Specialization for vectors.

Definition at line 113 of file util.h.

template<typename C >

void fst::StlReserve	(	C *	c,
		int64	n
	)

General case - no-op.

Definition at line 109 of file util.h.

FarEntryType fst::StringToFarEntryType

(

const string &

s

)

FarTokenType fst::StringToFarTokenType

(

const string &

s

)

template<class A >

Fst<A>* fst::StringToFst

(

const string &

s

)

Definition at line 823 of file fst.h.

int64 fst::StrToInt64	(	const string &	s,
		const string &	src,
		size_t	nline,
		bool	allow_negative = false
	)

Utilities for converting between int64 or Weight and string.

Definition at line 27 of file util.cc.

template<typename Weight >

Weight fst::StrToWeight	(	const string &	s,
		const string &	src,
		size_t	nline
	)

Definition at line 239 of file util.h.

template<class Arc >

void fst::Synchronize	(	const Fst< Arc > &	ifst,
		MutableFst< Arc > *	ofst
	)

Synchronizes a transducer. This version writes the synchronized result to a MutableFst. The result will be an equivalent FST that has the property that during the traversal of a path, the delay is either zero or strictly increasing, where the delay is the difference between the number of non-epsilon output labels and input labels along the path.

For the algorithm to terminate, the input transducer must have bounded delay, i.e., the delay of every cycle must be zero.

Complexity:

• A has bounded delay: exponential
• A does not have bounded delay: does not terminate

References:

• Mehryar Mohri. Edit-Distance of Weighted Automata: General Definitions and Algorithms, International Journal of Computer Science, 14(6): 957-982 (2003).

Definition at line 440 of file synchronize.h.

uint64 fst::SynchronizeProperties

(

uint64

inprops

)

Properties for a synchronized FST.

Definition at line 344 of file properties.cc.

template<class Arc >

uint64 fst::TestProperties	(	const Fst< Arc > &	fst,
		uint64	mask,
		uint64 *	known
	)

This is a wrapper around ComputeProperties that will cause a fatal error if the stored properties and the computed properties are incompatible when 'FLAGS_fst_verify_properties' is true. This routine is seldom called directly; instead it is used to implement fst.Properties(mask, true).

Definition at line 229 of file test-properties.h.

LogWeightTpl<float> fst::Times	(	const LogWeightTpl< float > &	w1,
		const LogWeightTpl< float > &	w2
	)			[inline]

Definition at line 384 of file float-weight.h.

template<class W , unsigned int n>

PowerWeight<W, n> fst::Times	(	const W &	s,
		const PowerWeight< W, n > &	w
	)			[inline]

Semimodule left scalar product.

Definition at line 123 of file power-weight.h.

template<typename L , StringType S>

StringWeight<L, S> fst::Times	(	const StringWeight< L, S > &	w1,
		const StringWeight< L, S > &	w2
	)			[inline]

Definition at line 419 of file string-weight.h.

template<class W , unsigned int n>

PowerWeight<W, n> fst::Times	(	const PowerWeight< W, n > &	w,
		const W &	s
	)			[inline]

Semimodule right scalar product.

Definition at line 132 of file power-weight.h.

TropicalWeightTpl<double> fst::Times	(	const TropicalWeightTpl< double > &	w1,
		const TropicalWeightTpl< double > &	w2
	)			[inline]

Definition at line 263 of file float-weight.h.

template<class W1 , class W2 >

ProductWeight<W1, W2> fst::Times	(	const ProductWeight< W1, W2 > &	w,
		const ProductWeight< W1, W2 > &	v
	)			[inline]

Definition at line 90 of file product-weight.h.

template<class X1 , class X2 >

ExpectationWeight<X1, X2> fst::Times	(	const ExpectationWeight< X1, X2 > &	w,
		const ExpectationWeight< X1, X2 > &	v
	)			[inline]

Definition at line 117 of file expectation-weight.h.

template<class W , unsigned int n>

PowerWeight<W, n> fst::Times	(	const PowerWeight< W, n > &	w1,
		const PowerWeight< W, n > &	w2
	)			[inline]

Semiring times operation.

Definition at line 102 of file power-weight.h.

MinMaxWeightTpl<float> fst::Times	(	const MinMaxWeightTpl< float > &	w1,
		const MinMaxWeightTpl< float > &	w2
	)			[inline]

Definition at line 496 of file float-weight.h.

TropicalWeightTpl<float> fst::Times	(	const TropicalWeightTpl< float > &	w1,
		const TropicalWeightTpl< float > &	w2
	)			[inline]

Definition at line 258 of file float-weight.h.

template<class T >

TropicalWeightTpl<T> fst::Times	(	const TropicalWeightTpl< T > &	w1,
		const TropicalWeightTpl< T > &	w2
	)			[inline]

Definition at line 247 of file float-weight.h.

MinMaxWeightTpl<double> fst::Times	(	const MinMaxWeightTpl< double > &	w1,
		const MinMaxWeightTpl< double > &	w2
	)			[inline]

Definition at line 501 of file float-weight.h.

LogWeightTpl<double> fst::Times	(	const LogWeightTpl< double > &	w1,
		const LogWeightTpl< double > &	w2
	)			[inline]

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

template<class T >

MinMaxWeightTpl<T> fst::Times	(	const MinMaxWeightTpl< T > &	w1,
		const MinMaxWeightTpl< T > &	w2
	)			[inline]

Max.

Definition at line 491 of file float-weight.h.

template<class W , class K >

SparsePowerWeight<W, K> fst::Times	(	const SparsePowerWeight< W, K > &	w1,
		const W &	k
	)			[inline]

Definition at line 201 of file sparse-power-weight.h.

template<class T >

SignedLogWeightTpl<T> fst::Times	(	const SignedLogWeightTpl< T > &	w1,
		const SignedLogWeightTpl< T > &	w2
	)			[inline]

Definition at line 137 of file signed-log-weight.h.

template<class W1 , class W2 >

LexicographicWeight<W1, W2> fst::Times	(	const LexicographicWeight< W1, W2 > &	w,
		const LexicographicWeight< W1, W2 > &	v
	)			[inline]

Definition at line 120 of file lexicographic-weight.h.

template<class W , class K >

SparsePowerWeight<W, K> fst::Times	(	const SparsePowerWeight< W, K > &	w1,
		const SparsePowerWeight< W, K > &	w2
	)			[inline]

Semimodule times operation.

Definition at line 152 of file sparse-power-weight.h.

template<class W , class K >

SparsePowerWeight<W, K> fst::Times	(	const W &	k,
		const SparsePowerWeight< W, K > &	w2
	)			[inline]

Definition at line 194 of file sparse-power-weight.h.

template<class T >

LogWeightTpl<T> fst::Times	(	const LogWeightTpl< T > &	w1,
		const LogWeightTpl< T > &	w2
	)			[inline]

Definition at line 373 of file float-weight.h.

template<class Arc >

bool fst::TopSort

(

MutableFst< Arc > *

fst

)

Topologically sorts its input if acyclic, modifying it. Otherwise, the input is unchanged. When sorted, all transitions are from lower to higher state IDs.

Complexity:

• Time: O(V + E)
• Space: O(V + E) where V = # of states and E = # of arcs.

Definition at line 89 of file topsort.h.

template<class Arc >

void fst::Union	(	RationalFst< Arc > *	fst1,
		const Fst< Arc > &	fst2
	)

Computes the union of two FSTs; this version modifies its RationalFst argument.

Definition at line 92 of file union.h.

template<class Arc >

void fst::Union	(	MutableFst< Arc > *	fst1,
		const Fst< Arc > &	fst2
	)

Computes the union (sum) of two FSTs. This version writes the union to an output MurableFst. If A transduces string x to y with weight a and B transduces string w to v with weight b, then their union transduces x to y with weight a and w to v with weight b.

Complexity:

• Time: (V2 + E2)
• Space: O(V2 + E2) where Vi = # of states and Ei = # of arcs of the ith FST.

Definition at line 42 of file union.h.

template<class A >

void fst::Union	(	RationalFst< A > *	fst1,
		const Fst< A > &	fst2
	)

uint64 fst::UnionProperties	(	uint64	inprops1,
		uint64	inprops2,
		bool	delayed = false
	)

Properties for a unioned FST.

Definition at line 353 of file properties.cc.

template<class Label >

bool fst::UTF8StringToLabels	(	const string &	,
		std::vector< Label > *
	)

Define the UTF8 string conversion function to throw an error when the ICU Library is missing or disabled.

Definition at line 121 of file compat.h.

template<class Label >

bool fst::UTF8StringToLabels	(	const string &	str,
		vector< Label > *	labels
	)

Definition at line 68 of file icu.h.

template<class Arc >

bool fst::Verify	(	const Fst< Arc > &	fst,
		bool	allow_negative_labels = false
	)

Verifies that an Fst's contents are sane.

Definition at line 31 of file verify.h.

template<class Arc , class V , class Q , class ArcFilter >

void fst::Visit	(	const Fst< Arc > &	fst,
		V *	visitor,
		Q *	queue,
		ArcFilter	filter
	)

Visitor Interface - class determines actions taken during a visit. If any of the boolean member functions return false, the visit is aborted by first calling FinishState() on all unfinished (grey) states and then calling FinishVisit().

Note this is more general than the visitor interface in dfs-visit.h but lacks some DFS-specific behavior.

template <class arc>=""> class Visitor { public: typedef typename Arc::StateId StateId;

Visitor(T *return_data); Invoked before visit void InitVisit(const Fst<Arc> &fst); Invoked when state discovered (2nd arg is visitation root) bool InitState(StateId s, StateId root); Invoked when arc to white/undiscovered state examined bool WhiteArc(StateId s, const Arc &a); Invoked when arc to grey/unfinished state examined bool GreyArc(StateId s, const Arc &a); Invoked when arc to black/finished state examined bool BlackArc(StateId s, const Arc &a); Invoked when state finished. void FinishState(StateId s); Invoked after visit void FinishVisit(); }; Performs queue-dependent visitation. Visitor class argument determines actions and contains any return data. ArcFilter determines arcs that are considered.

Note this is more general than DfsVisit() in dfs-visit.h but lacks some DFS-specific Visitor behavior.

Definition at line 67 of file visit.h.

template<class Arc , class V , class Q >

void fst::Visit	(	const Fst< Arc > &	fst,
		V *	visitor,
		Q *	queue
	)			[inline]

Definition at line 186 of file visit.h.

template<typename Weight >

void fst::WeightToStr	(	Weight	w,
		string *	s
	)

Definition at line 252 of file util.h.

fst::WRITE_POD_TYPE

(

int

)

fst::WRITE_POD_TYPE

(

signed

char

)

fst::WRITE_POD_TYPE

(

float

)

fst::WRITE_POD_TYPE

(

short

)

fst::WRITE_POD_TYPE

(

double

)

fst::WRITE_POD_TYPE

(

unsigned

char

)

fst::WRITE_POD_TYPE

(

char

)

fst::WRITE_POD_TYPE

(

bool

)

fst::WRITE_POD_TYPE

(

unsigned long

long

)

fst::WRITE_POD_TYPE

(

long

)

fst::WRITE_STL_ASSOC_TYPE

(

map

)

fst::WRITE_STL_ASSOC_TYPE

(

unordered_map

)

fst::WRITE_STL_ASSOC_TYPE

(

set

)

fst::WRITE_STL_ASSOC_TYPE

(

unordered_set

)

fst::WRITE_STL_SEQ_TYPE

(

vector

)

fst::WRITE_STL_SEQ_TYPE

(

list

)

template<typename Label >

void fst::WriteLabelPairs	(	const string &	filename,
		const vector< pair< Label, Label > > &	pairs
	)

Definition at line 291 of file util.h.

ostream& fst::WriteType	(	ostream &	strm,
		const string &	s
	)			[inline]

String case.

Definition at line 187 of file util.h.

template<typename S , typename T >

ostream& fst::WriteType	(	ostream &	strm,
		const pair< S, T > &	p
	)			[inline]

Pair case.

Definition at line 195 of file util.h.

template<typename T >

ostream& fst::WriteType	(	ostream &	strm,
		const T	t
	)			[inline]

Write some types to an output stream.

Generic case.

Definition at line 160 of file util.h.

---

Variable Documentation

const char fst::arc_lookahead_fst_type = "arc_lookahead"

Arc look-ahead matchers.

Fst type definitions for lookahead Fsts.

Useful aliases when using StdArc and LogArc.

Definition at line 96 of file fst.cc.

const char fst::ilabel_lookahead_fst_type = "ilabel_lookahead"

Label look-ahead matchers.

Definition at line 97 of file fst.cc.

const uint64 fst::kAcceptor = 0x0000000000010000ULL

ilabel == olabel for each arc

TRINARY PROPERTIES

For each of these properties below there is a pair of property bits

• one positive and one negative. If the positive bit is set, the property is true. If the negative bit is set, the property is false. If neither is set, the property has unknown value. Both should never be simultaneously set. The individual positive and negative bit pairs should be adjacent with the positive bit at an odd and lower position.

Definition at line 61 of file properties.h.

const uint64 fst::kAccessible = 0x0000010000000000ULL

All states reachable from the initial state.

Definition at line 121 of file properties.h.

const uint64 fst::kAcyclic = 0x0000000800000000ULL

FST has no cycles.

Definition at line 108 of file properties.h.

const uint64 fst::kAddArcProperties

Initial value:

 kExpanded | kMutable | kNotAcceptor |
    kNonIDeterministic | kNonODeterministic | kEpsilons | kIEpsilons |
    kOEpsilons | kNotILabelSorted | kNotOLabelSorted | kWeighted |
    kCyclic | kInitialCyclic | kNotTopSorted | kAccessible | kCoAccessible

Properties that are preserved when an FST arc is added.

Definition at line 191 of file properties.h.

const uint64 fst::kAddStateProperties

Initial value:

 kExpanded | kMutable | kAcceptor | kNotAcceptor | kIDeterministic |
    kNonIDeterministic | kODeterministic | kNonODeterministic |
    kEpsilons | kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons |
    kNoOEpsilons | kILabelSorted | kNotILabelSorted | kOLabelSorted |
    kNotOLabelSorted | kWeighted | kUnweighted | kCyclic | kAcyclic |
    kInitialCyclic | kInitialAcyclic | kTopSorted | kNotTopSorted |
    kNotAccessible | kNotCoAccessible | kNotString

Properties that are preserved when an FST state is added.

Definition at line 182 of file properties.h.

const uint64 fst::kAddSuperFinalProperties

Initial value:

 kExpanded | kMutable | kAcceptor |
  kNotAcceptor | kNonIDeterministic | kNonODeterministic | kEpsilons |
  kIEpsilons | kOEpsilons | kNotILabelSorted | kNotOLabelSorted |
  kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic |
  kInitialAcyclic | kNotTopSorted | kNotAccessible | kCoAccessible |
  kNotCoAccessible | kNotString

Properties that are preserved when a superfinal state is added and an FSTs final weights are directed to it via new transitions.

Definition at line 262 of file properties.h.

const uint64 fst::kArcSortProperties

Initial value:

  kExpanded | kMutable | kAcceptor | kNotAcceptor | kIDeterministic |
  kNonIDeterministic | kODeterministic | kNonODeterministic |
  kEpsilons | kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons |
  kNoOEpsilons | kWeighted | kUnweighted | kCyclic | kAcyclic |
  kInitialCyclic | kInitialAcyclic | kTopSorted | kNotTopSorted |
  kAccessible | kNotAccessible | kCoAccessible | kNotCoAccessible |
  kString | kNotString

Properties that are preserved when an FST's arcs are reordered.

Definition at line 224 of file properties.h.

const uint64 fst::kBinaryProperties = 0x0000000000000003ULL

All binary properties.

Definition at line 279 of file properties.h.

const uint64 fst::kCoAccessible = 0x0000040000000000ULL

All states can reach a final state.

Definition at line 126 of file properties.h.

const uint64 fst::kCommutative = 0x0000000000000004ULL

For all a,b: Times(a,b) = Times(b,a).

Definition at line 99 of file weight.h.

const uint64 fst::kCopyProperties

Initial value:

 kAcceptor | kNotAcceptor | kIDeterministic | kNonIDeterministic |
    kODeterministic | kNonODeterministic | kEpsilons | kNoEpsilons |
    kIEpsilons | kNoIEpsilons | kOEpsilons | kNoOEpsilons |
    kILabelSorted | kNotILabelSorted | kOLabelSorted |
    kNotOLabelSorted | kWeighted | kUnweighted | kCyclic | kAcyclic |
    kInitialCyclic | kInitialAcyclic | kTopSorted | kNotTopSorted |
    kAccessible | kNotAccessible | kCoAccessible | kNotCoAccessible |
    kString | kNotString

Properties that are preserved when an FST is copied.

Definition at line 152 of file properties.h.

const uint64 fst::kCyclic = 0x0000000400000000ULL

FST has cycles.

Definition at line 106 of file properties.h.

const uint64 fst::kDeleteArcsProperties

Initial value:

 kExpanded | kMutable | kAcceptor | kIDeterministic |
    kODeterministic | kNoEpsilons | kNoIEpsilons | kNoOEpsilons |
    kILabelSorted | kOLabelSorted | kUnweighted | kAcyclic |
    kInitialAcyclic | kTopSorted |  kNotAccessible | kNotCoAccessible

Properties that are preserved when FST arcs are deleted.

Definition at line 208 of file properties.h.

const uint64 fst::kDeleteStatesProperties

Initial value:

 kExpanded | kMutable | kAcceptor | kIDeterministic |
    kODeterministic | kNoEpsilons | kNoIEpsilons | kNoOEpsilons |
    kILabelSorted | kOLabelSorted | kUnweighted | kAcyclic |
    kInitialAcyclic | kTopSorted

Properties that are preserved when FST states are deleted.

Definition at line 201 of file properties.h.

const float fst::kDelta = 1.0F/1024.0F

A representable float near .001.

CONSTANT DEFINITIONS

Definition at line 88 of file weight.h.

const int fst::kDfsBlack = 2

Finished.

Definition at line 68 of file dfs-visit.h.

const int fst::kDfsGrey = 1

Discovered & unfinished.

Definition at line 67 of file dfs-visit.h.

const int fst::kDfsWhite = 0

An Fst state's DFS status.

Visitor Interface - class determines actions taken during a Dfs. If any of the boolean member functions return false, the DFS is aborted by first calling FinishState() on all currently grey states and then calling FinishVisit().

Note this is similar to the more general visitor interface in visit.h except that FinishState returns additional information appropriate only for a DFS and some methods names here are better suited to a DFS.

template <class arc>=""> class Visitor { public: typedef typename Arc::StateId StateId;

Visitor(T *return_data); Invoked before DFS visit void InitVisit(const Fst<Arc> &fst); Invoked when state discovered (2nd arg is DFS tree root) bool InitState(StateId s, StateId root); Invoked when tree arc examined (to white/undiscovered state) bool TreeArc(StateId s, const Arc &a); Invoked when back arc examined (to grey/unfinished state) bool BackArc(StateId s, const Arc &a); Invoked when forward or cross arc examined (to black/finished state) bool ForwardOrCrossArc(StateId s, const Arc &a); Invoked when state finished (PARENT is kNoStateID and ARC == NULL when S is tree root) void FinishState(StateId s, StateId parent, const Arc *parent_arc); Invoked after DFS visit void FinishVisit(); }; Undiscovered

Definition at line 66 of file dfs-visit.h.

const uint64 fst::kEpsilons = 0x0000000000400000ULL

FST has input/output epsilons.

Definition at line 76 of file properties.h.

const uint64 fst::kExpanded = 0x0000000000000001ULL

The Fst is an ExpandedFst.

The property bits here assert facts about an FST. If individual bits are added, then the composite properties below, the property functions and property names in properties.cc, and TestProperties() in test-properties.h should be updated. BINARY PROPERTIES

For each property below, there is a single bit. If it is set, the property is true. If it is not set, the property is false.

Definition at line 44 of file properties.h.

const uint32 fst::kFactorArcWeights = 0x00000002

Definition at line 41 of file factor-weight.h.

const uint32 fst::kFactorFinalWeights = 0x00000001

Definition at line 40 of file factor-weight.h.

const uint64 fst::kFstProperties = kBinaryProperties | kTrinaryProperties

All properties.

Definition at line 297 of file properties.h.

const uint64 fst::kIdempotent = 0x0000000000000008ULL

For all a: Plus(a, a) = a.

Definition at line 102 of file weight.h.

const uint64 fst::kIDeterministic = 0x0000000000040000ULL

ilabels unique leaving each state

Definition at line 66 of file properties.h.

const uint64 fst::kIEpsilons = 0x0000000001000000ULL

FST has input epsilons.

Definition at line 81 of file properties.h.

const uint64 fst::kILabelInvariantProperties

Initial value:

  kExpanded | kMutable | kODeterministic | kNonODeterministic |
  kOEpsilons | kNoOEpsilons | kOLabelSorted | kNotOLabelSorted |
  kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic |
  kInitialAcyclic | kTopSorted | kNotTopSorted | kAccessible |
  kNotAccessible | kCoAccessible | kNotCoAccessible | kString | kNotString

Properties that are preserved when an FST's input labels are changed.

Definition at line 234 of file properties.h.

const uint64 fst::kILabelSorted = 0x0000000010000000ULL

ilabels sorted wrt < for each state

Definition at line 91 of file properties.h.

const uint64 fst::kInitialAcyclic = 0x0000002000000000ULL

FST has no cycles containing the initial state.

Definition at line 113 of file properties.h.

const uint64 fst::kInitialCyclic = 0x0000001000000000ULL

FST has cycles containing the initial state.

Definition at line 111 of file properties.h.

const uint32 fst::kInputLookAheadMatcher = 0x00000001

LOOKAHEAD MATCHERS - these have the interface of Matchers (see matcher.h) and these additional methods:

template <class f>=""> class LookAheadMatcher { public: typedef F FST; typedef F::Arc Arc; typedef typename Arc::StateId StateId; typedef typename Arc::Label Label; typedef typename Arc::Weight Weight;

Required constructors. LookAheadMatcher(const F &fst, MatchType match_type); If safe=true, the copy is thread-safe (except the lookahead Fst is preserved). See Fst<>::Cop() for further doc. LookAheadMatcher(const LookAheadMatcher &matcher, bool safe = false);

Below are methods for looking ahead for a match to a label and more generally, to a rational set. Each returns false if there is definitely not a match and returns true if there possibly is a match. // LABEL LOOKAHEAD: Can 'label' be read from the current matcher state after possibly following epsilon transitions? bool LookAheadLabel(Label label) const;

RATIONAL LOOKAHEAD: The next methods allow looking ahead for an arbitrary rational set of strings, specified by an FST and a state from which to begin the matching. If the lookahead FST is a transducer, this looks on the side different from the matcher 'match_type' (cf. composition).

Are there paths P from 's' in the lookahead FST that can be read from the cur. matcher state? bool LookAheadFst(const Fst<Arc>& fst, StateId s);

Gives an estimate of the combined weight of the paths P in the lookahead and matcher FSTs for the last call to LookAheadFst. A trivial implementation returns Weight::One(). Non-trivial implementations are useful for weight-pushing in composition. Weight LookAheadWeight() const;

Is there is a single non-epsilon arc found in the lookahead FST that begins P (after possibly following any epsilons) in the last call LookAheadFst? If so, return true and copy it to '*arc', o.w. return false. A trivial implementation returns false. Non-trivial implementations are useful for label-pushing in composition. bool LookAheadPrefix(Arc *arc);

Optionally pre-specifies the lookahead FST that will be passed to LookAheadFst() for possible precomputation. If copy is true, then 'fst' is a copy of the FST used in the previous call to this method (useful to avoid unnecessary updates). void InitLookAheadFst(const Fst<Arc>& fst, bool copy = false);

}; LOOK-AHEAD FLAGS (see also kMatcherFlags in matcher.h):

Matcher is a lookahead matcher when 'match_type' is MATCH_INPUT.

Definition at line 98 of file lookahead-matcher.h.

const uint64 fst::kLeftSemiring = 0x0000000000000001ULL

For all a,b,c: Times(c, Plus(a,b)) = Plus(Times(c,a), Times(c, b)).

Definition at line 91 of file weight.h.

const int fst::kLineLen = 8096

Maximum line length in textual symbols file.

Definition at line 33 of file symbol-table.cc.

const uint32 fst::kLookAheadEpsilons = 0x00000020

Look-ahead of matcher FST epsilon arcs?

Definition at line 115 of file lookahead-matcher.h.

const uint32 fst::kLookAheadFlags = 0x000000ff

Flags used for lookahead matchers.

Definition at line 126 of file lookahead-matcher.h.

const uint32 fst::kLookAheadKeepRelabelData = 0x00000080

For LabelLookAheadMatcher, save relabeling data to file.

Definition at line 123 of file lookahead-matcher.h.

const uint32 fst::kLookAheadNonEpsilonPrefix = 0x00000040

Ignore epsilon paths for the lookahead prefix? Note this gives correct results in composition only with an appropriate composition filter since it depends on the filter blocking the ignored paths.

Definition at line 120 of file lookahead-matcher.h.

const uint32 fst::kLookAheadNonEpsilons = 0x00000010

Look-ahead of matcher FST non-epsilon arcs?

Definition at line 112 of file lookahead-matcher.h.

const uint32 fst::kLookAheadPrefix = 0x00000008

A non-trivial implementation of LookAheadPrefix() method defined and should be used?

Definition at line 109 of file lookahead-matcher.h.

const uint32 fst::kLookAheadWeight = 0x00000004

A non-trivial implementation of LookAheadWeight() method defined and should be used?

Definition at line 105 of file lookahead-matcher.h.

const uint32 fst::kMatcherFlags = 0x00000000

Flags used for basic matchers (see also lookahead.h).

MATCHERS - these can find and iterate through requested labels at FST states. In the simplest form, these are just some associative map or search keyed on labels. More generally, they may implement matching special labels that represent sets of labels such as 'sigma' (all), 'rho' (rest), or 'phi' (fail). The Matcher interface is:

template <class f>=""> class Matcher { public: typedef F FST; typedef F::Arc Arc; typedef typename Arc::StateId StateId; typedef typename Arc::Label Label; typedef typename Arc::Weight Weight;

Required constructors. Matcher(const F &fst, MatchType type); If safe=true, the copy is thread-safe. See Fst<>::Copy() for further doc. Matcher(const Matcher &matcher, bool safe = false);

If safe=true, the copy is thread-safe. See Fst<>::Copy() for further doc. Matcher<F> *Copy(bool safe = false) const;

Returns the match type that can be provided (depending on compatibility of the input FST). It is either the requested match type, MATCH_NONE, or MATCH_UNKNOWN. If 'test' is false, a constant time test is performed, but MATCH_UNKNOWN may be returned. If 'test' is true, a definite answer is returned, but may involve more costly computation (e.g., visiting the Fst). MatchType Type(bool test) const; Specifies the current state. void SetState(StateId s);

This finds matches to a label at the current state. Returns true if a match found. kNoLabel matches any 'non-consuming' transitions, e.g., epsilon transitions, which do not require a matching symbol. bool Find(Label label); These iterate through any matches found: bool Done() const; ///< No more matches. const A& Value() const; ///< Current arc (when !Done) void Next(); ///< Advance to next arc (when !Done)

Return matcher FST. const F& GetFst() const; This specifies the known Fst properties as viewed from this matcher. It takes as argument the input Fst's known properties. uint64 Properties(uint64 props) const; };

Definition at line 86 of file matcher.h.

const uint32 fst::kMultiEpsList = 0x00000001

Return multi-epsilon arcs for Find(kNoLabel).

MULTI-EPS MATCHER FLAGS

Definition at line 827 of file matcher.h.

const uint32 fst::kMultiEpsLoop = 0x00000002

Return a kNolabel loop for Find(multi_eps).

Definition at line 830 of file matcher.h.

const uint64 fst::kMutable = 0x0000000000000002ULL

The Fst is a MutableFst.

Definition at line 47 of file properties.h.

const uint64 fst::kNegTrinaryProperties

Initial value:

  kTrinaryProperties & 0xaaaaaaaaaaaaaaaaULL

2nd bit of trinary properties

Definition at line 293 of file properties.h.

const uint64 fst::kNoEpsilons = 0x0000000000800000ULL

FST has no input/output epsilons.

Definition at line 78 of file properties.h.

const uint64 fst::kNoIEpsilons = 0x0000000002000000ULL

FST has no input epsilons.

Definition at line 83 of file properties.h.

const int fst::kNoLabel = -1

Not a valid label.

Definition at line 557 of file fst.h.

const uint64 fst::kNonIDeterministic = 0x0000000000080000ULL

ilabels not unique leaving some state

Definition at line 68 of file properties.h.

const uint64 fst::kNonODeterministic = 0x0000000000200000ULL

olabels not unique leaving some state

Definition at line 73 of file properties.h.

const uint64 fst::kNoOEpsilons = 0x0000000008000000ULL

FST has no output epsilons.

Definition at line 88 of file properties.h.

const int fst::kNoStateId = -1

Not a valid state ID.

CONSTANT DEFINITIONS

Definition at line 556 of file fst.h.

const uint64 fst::kNotAcceptor = 0x0000000000020000ULL

ilabel != olabel for some arc

Definition at line 63 of file properties.h.

const uint64 fst::kNotAccessible = 0x0000020000000000ULL

Not all states reachable from the initial state.

Definition at line 123 of file properties.h.

const uint64 fst::kNotCoAccessible = 0x0000080000000000ULL

Not all states can reach a final state.

Definition at line 128 of file properties.h.

const uint64 fst::kNotILabelSorted = 0x0000000020000000ULL

ilabels not sorted wrt < for some state

Definition at line 93 of file properties.h.

const uint64 fst::kNotOLabelSorted = 0x0000000080000000ULL

olabels not sorted wrt < for some state

Definition at line 98 of file properties.h.

const uint64 fst::kNotString = 0x0000200000000000ULL

Not a string FST.

Definition at line 136 of file properties.h.

const uint64 fst::kNotTopSorted = 0x0000008000000000ULL

FST is not topologically sorted.

Definition at line 118 of file properties.h.

const uint64 fst::kNullProperties

Initial value:

 kAcceptor | kIDeterministic | kODeterministic | kNoEpsilons |
    kNoIEpsilons | kNoOEpsilons | kILabelSorted | kOLabelSorted |
    kUnweighted | kAcyclic | kInitialAcyclic | kTopSorted |
    kAccessible | kCoAccessible | kString

Properties of an empty machine.

COMPOSITE PROPERTIES

Definition at line 145 of file properties.h.

const uint64 fst::kODeterministic = 0x0000000000100000ULL

olabels unique leaving each state

Definition at line 71 of file properties.h.

const uint64 fst::kOEpsilons = 0x0000000004000000ULL

FST has output epsilons.

Definition at line 86 of file properties.h.

const uint64 fst::kOLabelInvariantProperties

Initial value:

  kExpanded | kMutable | kIDeterministic | kNonIDeterministic |
  kIEpsilons | kNoIEpsilons | kILabelSorted | kNotILabelSorted |
  kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic |
  kInitialAcyclic | kTopSorted | kNotTopSorted | kAccessible |
  kNotAccessible | kCoAccessible | kNotCoAccessible | kString | kNotString

Properties that are preserved when an FST's output labels are changed.

Definition at line 242 of file properties.h.

const uint64 fst::kOLabelSorted = 0x0000000040000000ULL

olabels sorted wrt < for each state

Definition at line 96 of file properties.h.

const uint32 fst::kOutputLookAheadMatcher = 0x00000002

Matcher is a lookahead matcher when 'match_type' is MATCH_OUTPUT.

Definition at line 101 of file lookahead-matcher.h.

const uint64 fst::kPath = 0x0000000000000010ULL

For all a,b: Plus(a,b) = a or Plus(a,b) = b.

Definition at line 105 of file weight.h.

const uint64 fst::kPosTrinaryProperties

Initial value:

  kTrinaryProperties & 0x5555555555555555ULL

1st bit of trinary properties

COMPUTED PROPERTIES

Definition at line 289 of file properties.h.

const uint32 fst::kPushLabels = 0x0002

Definition at line 111 of file push.h.

const uint32 fst::kPushRemoveCommonAffix = 0x0008

Definition at line 113 of file push.h.

const uint32 fst::kPushRemoveTotalWeight = 0x0004

Definition at line 112 of file push.h.

const uint32 fst::kPushWeights = 0x0001

Definition at line 110 of file push.h.

const uint64 fst::kRightSemiring = 0x0000000000000002ULL

For all a,b,c: Times(Plus(a,b), c) = Plus(Times(a,c), Times(b, c)).

Definition at line 94 of file weight.h.

const uint64 fst::kRmSuperFinalProperties

Initial value:

 kExpanded | kMutable | kAcceptor |
  kNotAcceptor | kIDeterministic | kODeterministic | kNoEpsilons |
  kNoIEpsilons | kNoOEpsilons | kILabelSorted | kOLabelSorted |
  kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic |
  kInitialAcyclic | kTopSorted | kAccessible | kCoAccessible |
  kNotCoAccessible | kString

Properties that are preserved when a superfinal state is removed and the epsilon transitions directed to it are made final weights.

Definition at line 271 of file properties.h.

const uint64 fst::kSemiring = kLeftSemiring | kRightSemiring

Definition at line 96 of file weight.h.

const uint64 fst::kSetArcProperties = kExpanded | kMutable

Properties that are preserved when an FST arc is set.

Definition at line 197 of file properties.h.

const uint64 fst::kSetFinalProperties

Initial value:

 kExpanded | kMutable | kAcceptor | kNotAcceptor | kIDeterministic |
    kNonIDeterministic | kODeterministic | kNonODeterministic |
    kEpsilons | kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons |
    kNoOEpsilons | kILabelSorted | kNotILabelSorted | kOLabelSorted |
    kNotOLabelSorted | kCyclic | kAcyclic | kInitialCyclic |
    kInitialAcyclic | kTopSorted | kNotTopSorted | kAccessible |
    kNotAccessible

Properties that are preserved when an FST final weight is set.

Definition at line 172 of file properties.h.

const uint64 fst::kSetStartProperties

Initial value:

 kExpanded | kMutable | kAcceptor | kNotAcceptor | kIDeterministic |
    kNonIDeterministic | kODeterministic | kNonODeterministic |
    kEpsilons | kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons |
    kNoOEpsilons | kILabelSorted | kNotILabelSorted | kOLabelSorted |
    kNotOLabelSorted | kWeighted | kUnweighted | kCyclic | kAcyclic |
    kTopSorted | kNotTopSorted | kCoAccessible | kNotCoAccessible

Properties that are preserved when an FST start state is set.

Definition at line 163 of file properties.h.

const uint64 fst::kStateSortProperties

Initial value:

 kExpanded | kMutable | kAcceptor |
  kNotAcceptor | kIDeterministic | kNonIDeterministic |
  kODeterministic | kNonODeterministic | kEpsilons | kNoEpsilons |
  kIEpsilons | kNoIEpsilons | kOEpsilons | kNoOEpsilons |
  kILabelSorted | kNotILabelSorted | kOLabelSorted | kNotOLabelSorted
  | kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic |
  kInitialAcyclic | kAccessible | kNotAccessible | kCoAccessible |
  kNotCoAccessible

Properties that are preserved when an FST's states are reordered.

Definition at line 214 of file properties.h.

const uint64 fst::kString = 0x0000100000000000ULL

If NumStates() > 0, then state 0 is initial, state NumStates()-1 is final, there is a transition from each non-final state i to state i+1, and there are no other transitions.

Definition at line 133 of file properties.h.

const int fst::kStringBad = -2

Label for a non-string.

Definition at line 33 of file string-weight.h.

const int fst::kStringInfinity = -1

Label for the infinite string.

Definition at line 32 of file string-weight.h.

const char fst::kStringSeparator = '_'

Label separator in strings.

Definition at line 34 of file string-weight.h.

const uint64 fst::kTopSorted = 0x0000004000000000ULL

FST is topologically sorted.

Definition at line 116 of file properties.h.

const uint64 fst::kTrinaryProperties = 0x00003fffffff0000ULL

All trinary properties.

Definition at line 282 of file properties.h.

const uint64 fst::kUnweighted = 0x0000000200000000ULL

Only trivial arc and final weights.

Definition at line 103 of file properties.h.

const uint64 fst::kWeighted = 0x0000000100000000ULL

Non-trivial arc or final weights.

Definition at line 101 of file properties.h.

const uint64 fst::kWeightInvariantProperties

Initial value:

  kExpanded | kMutable | kAcceptor | kNotAcceptor | kIDeterministic |
  kNonIDeterministic | kODeterministic | kNonODeterministic |
  kEpsilons | kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons |
  kNoOEpsilons | kILabelSorted | kNotILabelSorted | kOLabelSorted |
  kNotOLabelSorted | kCyclic | kAcyclic | kInitialCyclic | kInitialAcyclic |
  kTopSorted | kNotTopSorted | kAccessible | kNotAccessible | kCoAccessible |
  kNotCoAccessible | kString | kNotString

Properties that are preserved when an FST's weights are changed. This assumes that the set of states that are non-final is not changed.

Definition at line 251 of file properties.h.

const char fst::olabel_lookahead_fst_type = "olabel_lookahead"

Definition at line 98 of file fst.cc.

const char * fst::PropertyNames

Initial value:

 {
  
  "expanded", "mutable", "", "", "", "", "", "",
  "", "", "", "", "", "", "", "",
  
  "acceptor", "not acceptor",
  "input deterministic", "non input deterministic",
  "output deterministic", "non output deterministic",
  "input/output epsilons", "no input/output epsilons",
  "input epsilons", "no input epsilons",
  "output epsilons", "no output epsilons",
  "input label sorted", "not input label sorted",
  "output label sorted", "not output label sorted",
  "weighted", "unweighted",
  "cyclic", "acyclic",
  "cyclic at initial state", "acyclic at initial state",
  "top sorted", "not top sorted",
  "accessible", "not accessible",
  "coaccessible", "not coaccessible",
  "string", "not string",
}

Property string names (indexed by bit position).

Definition at line 382 of file properties.cc.