Skip to content

invert.md

Latest commit

 

History

History
57 lines (37 loc) · 952 Bytes

invert.md

File metadata and controls

57 lines (37 loc) · 952 Bytes

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);

InvertFst

fstinvert a.fst out.fst

Examples

A:

Input FST A.

A-1:

Result of Invert(A), swapping input and output labels.

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.