---+ Determinize ---++ Description This operation determinizes a weighted transducer. The result will be an [[FstGlossary#EquivalentDef][equivalent]] FST that has the property that no state has two transitions with the same input label. For this algorithm, [[FstGlossary#EpsilonDef][epsilon]] transitions are treated as regular symbols (cf. [[RmEpsilonDoc][RmEpsilon]]). The transducer must be [[FstGlossary#FunctionalDef][functional]]. The weights must be (weakly) [[FstWeightRequirements][left divisible]] (valid for !TropicalWeight and !LogWeight for instance) and [[FstGlossary#ZeroSumFreeDef][zero-sum-free]]. ---++ Usage |<verbatim> template <class Arc> void Determinize(const Fst<Arc> &ifst, MutableFst<Arc> *ofst); </verbatim>| %DOX{namespacefst.html#Determinize[%H%]}% | |<verbatim> template <class Arc> DeterminizeFst<Arc>:: DeterminizeFst(const Fst<Arc> &fst); </verbatim>| %DOX{fst::DeterminizeFst[%H%]}% | |<verbatim>fstdeterminize a.fst out.fst</verbatim> | | ---++ Examples ---+++ =A=: %ATTACHURL%/determinize1.jpg (!TropicalWeight) ---+++ =Determinize of A=: %ATTACHURL%/determinize2.jpg <verbatim> Determinize(&A); DeterminizeFst<Arc>(A); fstdeterminize a.fst out.fst </verbatim> ---++ Complexity =Determinize=: * Determinizable: _exponential (polynomial in the size of the output)_ * Non-determinizable: _does not terminate_ =DeterminizeFst:= * Determinizable: _exponential (polynomial in the size of the output)_ * Non-determinizable: _does not terminate_ The determinizable automata include all unweighted and all acyclic input. ---++ Caveats Epsilons may be added as input labels at the ends of paths when determinizing transducers. If input transducer also contains epsilons, this may result in a non-deterministic result even when the epsilons are treated as regular symbols. The _subsequential label_ can be chosen as a non-zero value to avoid this issue by passing it as an option (in a variant call to this function/class). Non-functional transducers can be handled by passing the 'disambiguate_output' option when the semiring has the [[FstWeightRequirements][path property]] (in a variant call to this function/class). In this case, only the shortest path output for each input is retained. ---++ See Also [[DisambiguateDoc][Disambiguate]], [[RmEpsilonDoc][RmEpsilon]] ---++ References * Mehryar Mohri. [[http://www.cs.nyu.edu/~mohri/postscript/cl1.pdf][Finite-State Transducers in Language and Speech Processing.]] _Computational Linguistics_, 23:2, 1997. * Cyril Allauzen and Mehryar Mohri. [[http://cs.nyu.edu/~allauzen/pdf/twins.pdf][Efficient Algorithms for Testing the Twins Property.]] _Journal of Automata, Languages and Combinatorics_, 8(2):117-144, 2003. -- Main.MichaelRiley - 20 Jun 2007
Attachments
Attachments
Topic attachments
I
Attachment
History
Action
Size
Date
Who
Comment
jpg
determinize1.jpg
r2
r1
manage
12.5 K
2007-06-21 - 21:43
MichaelRiley
jpg
determinize2.jpg
r2
r1
manage
13.7 K
2007-06-21 - 21:43
MichaelRiley
This topic: FST
>
WebHome
>
FstQuickTour
>
DeterminizeDoc
Topic revision: r13 - 2014-05-06 - MichaelRiley
Copyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki?
Send feedback