TWiki> FST Web>FstQuickTour>RandGenDoc (revision 1)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

 ```template void RandGen(const Fst &ifst, MutableFst *ofst); ``` [bad link?] ```template void RandGen(const Fst &ifst, MutableFst *ofst, const RandGenOptions &opts); ``` ```fstrandgen [--max_length=\$l] [--npath=\$n] [--seed=\$s] [--select=\$sel] in.fst out.fst ```

## Example

### `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
```

## Complexity:

`RandGen`

• 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
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`
Edit | Attach | Watch | Print version | History: r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r1 - 2009-03-27 - CyrilAllauzen

Copyright © 2008-2022 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback