fst::DeterminizeFst< A > Class Template Reference

#include <fst/determinize.h>

Inherits ImplToFst< DeterminizeFstImplBase< A > >.

Collaboration diagram for fst::DeterminizeFst< A >:

List of all members.

Public Types
typedef A	Arc
typedef A::Weight	Weight
typedef A::StateId	StateId
typedef A::Label	Label
typedef CacheState< A >	State
typedef DeterminizeFstImplBase< A >	Impl
Public Member Functions
	DeterminizeFst (const Fst< A > &fst, const DeterminizeFstOptions< A > &opts=DeterminizeFstOptions< A >())
	DeterminizeFst (const Fst< A > &fst, const vector< Weight > &in_dist, vector< Weight > *out_dist, const DeterminizeFstOptions< A > &opts=DeterminizeFstOptions< A >())
	DeterminizeFst (const DeterminizeFst< A > &fst, bool safe=false)
	See Fst<>::Copy() for doc.
virtual DeterminizeFst< A > *	Copy (bool safe=false) const
	Get a copy of this DeterminizeFst. See Fst<>::Copy() for further doc.
virtual void	InitStateIterator (StateIteratorData< A > *data) const
virtual void	InitArcIterator (StateId s, ArcIteratorData< A > *data) const
Friends
class	ArcIterator< DeterminizeFst< A > >
class	StateIterator< DeterminizeFst< A > >
class	DeterminizeFstImpl

---

Detailed Description

template<class A>
class fst::DeterminizeFst< A >

Determinizes a weighted transducer. This version is a delayed Fst. 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 for instance) and be zero-sum-free if for all a,b: (Plus(a, b) = 0 => a = b = 0.

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.

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

Definition at line 639 of file determinize.h.

---

Member Typedef Documentation

template<class A>

typedef A fst::DeterminizeFst< A >::Arc

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

Definition at line 645 of file determinize.h.

template<class A>

typedef DeterminizeFstImplBase<A> fst::DeterminizeFst< A >::Impl

Definition at line 650 of file determinize.h.

template<class A>

typedef A::Label fst::DeterminizeFst< A >::Label

Definition at line 648 of file determinize.h.

template<class A>

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

Definition at line 649 of file determinize.h.

template<class A>

typedef A::StateId fst::DeterminizeFst< A >::StateId

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

Definition at line 647 of file determinize.h.

template<class A>

typedef A::Weight fst::DeterminizeFst< A >::Weight

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

Definition at line 646 of file determinize.h.

---

Constructor & Destructor Documentation

template<class A>

fst::DeterminizeFst< A >::DeterminizeFst	(	const Fst< A > &	fst,
		const DeterminizeFstOptions< A > &	opts = DeterminizeFstOptions<A>()
	)			[inline, explicit]

Definition at line 654 of file determinize.h.

template<class A>

fst::DeterminizeFst< A >::DeterminizeFst	(	const Fst< A > &	fst,
		const vector< Weight > &	in_dist,
		vector< Weight > *	out_dist,
		const DeterminizeFstOptions< A > &	opts = DeterminizeFstOptions<A>()
	)			[inline]

This acceptor-only version additionally computes the distance to final states in the output if provided with those distances for the input. Useful for e.g. unique N-shortest paths.

Definition at line 670 of file determinize.h.

template<class A>

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

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

Definition at line 682 of file determinize.h.

---

Member Function Documentation

template<class A>

virtual DeterminizeFst<A>* fst::DeterminizeFst< A >::Copy

(

bool

safe = false

)

const [inline, virtual]

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

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

Definition at line 690 of file determinize.h.

template<class A>

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

Definition at line 696 of file determinize.h.

template<class A >

void fst::DeterminizeFst< A >::InitStateIterator

(

StateIteratorData< A > *

data

)

const [inline, virtual]

Definition at line 769 of file determinize.h.

---

Friends And Related Function Documentation

template<class A>

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

Definition at line 641 of file determinize.h.

template<class A>

friend class DeterminizeFstImpl [friend]

Definition at line 643 of file determinize.h.

template<class A>

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

Definition at line 642 of file determinize.h.

---

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

• openfst-1.2.6/src/include/fst/determinize.h