FST Web>FstQuickTour>ReverseDoc (2018-04-27, MichaelRiley)

Reverse

Description

This operation reverses an FST. If A transduces string x to y with weight a, then the reverse of A transduces the reverse of x to the reverse of y with weight a.Reverse().

Typically, a = a.Reverse() and Arc = RevArc (e.g. for TropicalWeight or LogWeight). In general, e.g., when the weights only form a left or right semiring, the output arc type must match the input arc type except having the reversed Weight type.

Usage

template<class Arc, class RevArc> void Reverse(const Fst<Arc> &ifst, MutableFst<RevArc> *ofst);
fstreverse a.fst out.fst

template<class Arc, class RevArc>
void Reverse(const Fst<Arc> &ifst, MutableFst<RevArc> *ofst);

fstreverse a.fst out.fst

Examples

`A`:

`Reverse of A`:

Reverse(&A);
fstreverse a.fst out.fst

Complexity

Reverse:

Time: O(V + E)
Space: O(V + E)

where V = # of states and E = # of arcs.

-- MichaelRiley - 03 Jul 2007

Attachments

Topic attachments
I	Attachment	History	Action	Size	Date	Who	Comment
jpg	reverse1.jpg	r3 r2 r1	manage	14.3 K	2007-07-03 - 01:19	MichaelRiley
jpg	reverse2.jpg	r3 r2 r1	manage	18.5 K	2007-07-03 - 01:19	MichaelRiley

Topic revision: r3 - 2018-04-27 - MichaelRiley