#include <fst/compose.h>

Inherits ImplToFst< ComposeFstImplBase< A > >.

Inherited by fst::DifferenceFst< A >, and fst::IntersectFst< A >.

Collaboration diagram for fst::ComposeFst< A >:

Public Types
typedef A	Arc
typedef A::Weight	Weight
typedef A::StateId	StateId
typedef CacheState< A >	State
typedef ComposeFstImplBase< A >	Impl
Public Member Functions
	ComposeFst (const Fst< A > &fst1, const Fst< A > &fst2, const CacheOptions &opts=CacheOptions())
	Compose specifying only caching options.
template<class M , class F , class T >
	ComposeFst (const Fst< A > &fst1, const Fst< A > &fst2, const ComposeFstOptions< A, M, F, T > &opts)
template<class M1 , class M2 , class F , class T >
	ComposeFst (const typename M1::FST &fst1, const typename M2::FST &fst2, const ComposeFstImplOptions< M1, M2, F, T > &opts)
	ComposeFst (const ComposeFst< A > &fst, bool safe=false)
	See Fst<>::Copy() for doc.
virtual ComposeFst< A > *	Copy (bool safe=false) const
	Get a copy of this ComposeFst. See Fst<>::Copy() for further doc.
virtual void	InitStateIterator (StateIteratorData< A > *data) const
virtual void	InitArcIterator (StateId s, ArcIteratorData< A > *data) const
Protected Member Functions
	ComposeFst ()
Static Protected Member Functions
template<class M1 , class M2 , class F , class T >
static Impl *	CreateBase2 (const typename M1::FST &fst1, const typename M2::FST &fst2, const ComposeFstImplOptions< M1, M2, F, T > &opts)
	Create compose implementation specifying two matcher types.
template<class M , class F , class T >
static Impl *	CreateBase1 (const Fst< A > &fst1, const Fst< A > &fst2, const ComposeFstOptions< A, M, F, T > &opts)
static Impl *	CreateBase (const Fst< A > &fst1, const Fst< A > &fst2, const CacheOptions &opts)
	Create compose implementation specifying no matcher type.
Friends
class	ArcIterator< ComposeFst< A > >
class	StateIterator< ComposeFst< A > >

Detailed Description

template<class A>
class fst::ComposeFst< A >

Computes the composition of two transducers. This version is a delayed Fst. 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 (with the default matcher). 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) where vi = # of states visited, di = maximum out-degree, and mi the maximum multiplicity of the states visited for the ith FST. Constant time and space to visit an input state or arc is assumed and exclusive of caching.

Caveats:

ComposeFst does not trim its output (since it is a delayed operation).
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.

This class attaches interface to implementation and handles reference counting, delegating most methods to ImplToFst.

Definition at line 430 of file compose.h.

Member Typedef Documentation

template<class A>

typedef A fst::ComposeFst< A >::Arc

Reimplemented from fst::ImplToFst< ComposeFstImplBase< A > >.

Reimplemented in fst::DifferenceFst< A >, and fst::IntersectFst< A >.

Definition at line 435 of file compose.h.

template<class A>

typedef ComposeFstImplBase<A> fst::ComposeFst< A >::Impl

Definition at line 439 of file compose.h.

template<class A>

typedef CacheState<A> fst::ComposeFst< A >::State

Definition at line 438 of file compose.h.

template<class A>

typedef A::StateId fst::ComposeFst< A >::StateId

Reimplemented from fst::ImplToFst< ComposeFstImplBase< A > >.

Reimplemented in fst::DifferenceFst< A >, and fst::IntersectFst< A >.

Definition at line 437 of file compose.h.

template<class A>

typedef A::Weight fst::ComposeFst< A >::Weight

Reimplemented from fst::ImplToFst< ComposeFstImplBase< A > >.

Reimplemented in fst::DifferenceFst< A >, and fst::IntersectFst< A >.

Definition at line 436 of file compose.h.

Constructor & Destructor Documentation

template<class A>

fst::ComposeFst< A >::ComposeFst	(	const Fst< A > &	fst1,
		const Fst< A > &	fst2,
		const CacheOptions &	opts = `CacheOptions()`
	)			`[inline]`

Compose specifying only caching options.

Definition at line 444 of file compose.h.

template<class A>

template<class M , class F , class T >

fst::ComposeFst< A >::ComposeFst	(	const Fst< A > &	fst1,
		const Fst< A > &	fst2,
		const ComposeFstOptions< A, M, F, T > &	opts
	)			`[inline]`

Compose specifying one shared matcher type M. Requires input Fsts and matcher FST type (M::FST) be Fst. Recommended for best code-sharing and matcher compatiblity.

Definition at line 452 of file compose.h.

template<class A>

template<class M1 , class M2 , class F , class T >

fst::ComposeFst< A >::ComposeFst	(	const typename M1::FST &	fst1,
		const typename M2::FST &	fst2,
		const ComposeFstImplOptions< M1, M2, F, T > &	opts
	)			`[inline]`

Compose specifying two matcher types M1 and M2. Requires input Fsts (of the same Arc type but o.w. arbitrary) match the corresponding matcher FST types (M1::FST, M2::FST). Recommended only for advanced use in demanding or specialized applications due to potential code bloat and matcher incompatibilities.

Definition at line 462 of file compose.h.

template<class A>

fst::ComposeFst< A >::ComposeFst	(	const ComposeFst< A > &	fst,
		bool	safe = `false`
	)			`[inline]`

See Fst<>::Copy() for doc.

Definition at line 467 of file compose.h.

template<class A>

fst::ComposeFst< A >::ComposeFst ( ) [inline, protected]

Definition at line 486 of file compose.h.

Member Function Documentation

template<class A>

virtual ComposeFst<A>* fst::ComposeFst< A >::Copy ( bool safe = false ) const [inline, virtual]

Get a copy of this ComposeFst. See Fst<>::Copy() for further doc.

Implements fst::Fst< typename ComposeFstImplBase< A >::Arc >.

Reimplemented in fst::DifferenceFst< A >, and fst::IntersectFst< A >.

Definition at line 475 of file compose.h.

template<class A>

static Impl* fst::ComposeFst< A >::CreateBase	(	const Fst< A > &	fst1,
		const Fst< A > &	fst2,
		const CacheOptions &	opts
	)			`[inline, static, protected]`

Create compose implementation specifying no matcher type.

Definition at line 514 of file compose.h.

template<class A>

template<class M , class F , class T >

static Impl* fst::ComposeFst< A >::CreateBase1	(	const Fst< A > &	fst1,
		const Fst< A > &	fst2,
		const ComposeFstOptions< A, M, F, T > &	opts
	)			`[inline, static, protected]`

Create compose implementation specifying one matcher type. Requires input Fsts and matcher FST type (M::FST) be Fst

Definition at line 506 of file compose.h.

template<class A>

template<class M1 , class M2 , class F , class T >

static Impl* fst::ComposeFst< A >::CreateBase2	(	const typename M1::FST &	fst1,
		const typename M2::FST &	fst2,
		const ComposeFstImplOptions< M1, M2, F, T > &	opts
	)			`[inline, static, protected]`

Create compose implementation specifying two matcher types.

Definition at line 490 of file compose.h.

template<class A>

virtual void fst::ComposeFst< A >::InitArcIterator	(	StateId	s,
		ArcIteratorData< A > *	data
	)			const `[inline, virtual]`

Definition at line 481 of file compose.h.

template<class A >

void fst::ComposeFst< A >::InitStateIterator ( StateIteratorData< A > * data ) const [inline, virtual]

Definition at line 573 of file compose.h.

Friends And Related Function Documentation

template<class A>

friend class ArcIterator< ComposeFst< A > > [friend]

Definition at line 432 of file compose.h.

template<class A>

friend class StateIterator< ComposeFst< A > > [friend]

Definition at line 433 of file compose.h.

The documentation for this class was generated from the following file:

openfst-1.2.6/src/include/fst/compose.h

fst::ComposeFst< A > Class Template Reference

Public Types

Public Member Functions

Protected Member Functions

Static Protected Member Functions

Friends

Detailed Description

template<class A> class fst::ComposeFst< A >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

template<class A>
class fst::ComposeFst< A >