(r1) RandGenDoc < FST

FST Web>FstQuickTour>RandGenDoc (revision 1) (raw view)~~EditAttach~~

---+ !RandGen

---++ Description

This operation randomly generates a set of successful paths in the input FST. The operation relies on an =ArcSelector= object for randomly selecting an outgoing transition at a given state in the input FST. The default arc selector, =UniformArcSelector=, randomly selects a transition using the uniform distribution. =LogProbArcSelector= randomly selects a transition w.r.t. the weights treated as negative log probabilities after normalizing for the total weight leaving the state. In all cases, finality is treated as a transition to a super-final state.

---++ Usage

| <verbatim>
template <class Arc>
void RandGen(const Fst<Arc> &ifst, MutableFst<Arc> *ofst);
</verbatim> | %DOX{namespacefst.html#RandGen[%H%]}% |
| <verbatim>
template <class Arc, class ArcSelector>
void RandGen(const Fst<Arc> &ifst, MutableFst<Arc> *ofst, const RandGenOptions<ArcSelector> &opts);
</verbatim> | ^ |
| <verbatim>
fstrandgen [--max_length=$l] [--npath=$n] [--seed=$s] [--select=$sel] in.fst out.fst 
</verbatim> ||


---++ Example

---+++ =A=:

%ATTACHURL%/randgen1.png

---+++ =Relabel(A, &B) using !UniformArcSelector=:

%ATTACHURL%/randgen2.png

<verbatim>
RandGen(A, &B);
RandGen(A, &B, RandGenOptions<UniformArcSelector<Arc> >(UniformArcSelector<Arc>()));

fstrandgen a.fst b.fst
</verbatim>

---+++ =Relabel(A, &B) using !LogProbArcSelector=:

%ATTACHURL%/randgen3.png

<verbatim>
RandGen(A, &B, RandGenOptions<LogProbArcSelector<Arc> >(LogProbArcSelector<Arc>()));

fstrandgen --select=log_prob a.fst b.fst
</verbatim>

---++ Complexity:

=RandGen=
   * Time: _O(N * L * c<sub>T</sub>)_
   * Space: _O(N * L + c<sub>S</sub>)_
where _N_ = number of paths to be generated, _L_ = expected length of a successful path according to the considered arc selector, _c<sub>T</sub>_ = time required for randomly selecting an arc, and _c<sub>S</sub>_ = space required for randomly selecting an arc.

-- Main.CyrilAllauzen - 27 Mar 2009

Attachments

Topic attachments
I	Attachment	History	Action	Size	Date	Who	Comment
png	randgen1.png	r1	manage	19.4 K	2009-03-27 - 19:04	CyrilAllauzen	RandGen example: input FST
png	randgen2.png	r1	manage	7.7 K	2009-03-27 - 19:05	CyrilAllauzen	RandGen example: randomly generated path using `UniformArcSelector`
png	randgen3.png	r1	manage	7.8 K	2009-03-27 - 19:06	CyrilAllauzen	RandGen example: randomly generated path using `LogProbArcSelector`

Topic revision: r1 - 2009-03-27 - CyrilAllauzen