Invert

Description

This operation inverts the transduction corresponding to an FST by exchanging the FST's input and output labels.

Usage

template<class Arc> void Invert(MutableFst<Arc> *fst);
template <class Arc> InvertFst<Arc>:: InvertFst(const Fst<Arc> &fst);
fstinvert a.fst out.fst

Examples

A:

A-1:

Invert(&A);
InvertFst<Arc>(A);
fstinvert a.fst out.fst

Complexity

Invert:

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

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

InvertFst:

• Time:: O(v + e)
• Space: O(1)
  

where v = # of states visited, e = # of arcs visited. Constant time and space to visit an input state or arc is assumed and exclusive of caching.

-- MichaelRiley - 1 Jul 2007