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.


template <class Arc>
void RandGen(const Fst<Arc> &ifst, MutableFst<Arc> *ofst);
template <class Arc, class ArcSelector>
void RandGen(const Fst<Arc> &ifst, MutableFst<Arc> *ofst, const RandGenOptions<ArcSelector> &opts);
fstrandgen [--max_length=$l] [--npath=$n] [--seed=$s] [--select=$sel] in.fst out.fst 




Relabel(A, &B) using UniformArcSelector:


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

fstrandgen a.fst b.fst

Relabel(A, &B) using LogProbArcSelector:


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

fstrandgen --select=log_prob a.fst b.fst



  • Time: O(N * L * cT)
  • Space: O(N * L + cS)
where N = number of paths to be generated, L = expected length of a successful path according to the considered arc selector, cT = time required for randomly selecting an arc, and cS = space required for randomly selecting an arc.

-- CyrilAllauzen - 27 Mar 2009

Topic attachments
I Attachment History Action Size Date Who Comment
PNGpng randgen1.png r1 manage 19.4 K 2009-03-27 - 19:04 CyrilAllauzen RandGen example: input FST
PNGpng randgen2.png r1 manage 7.7 K 2009-03-27 - 19:05 CyrilAllauzen RandGen example: randomly generated path using UniformArcSelector
PNGpng 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
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback