Skip to content

union.md

Latest commit

 

History

History
64 lines (42 loc) · 1.27 KB

union.md

File metadata and controls

64 lines (42 loc) · 1.27 KB

Union

Description

This operation computes the union (sum) of two FSTs. If A transduces string x to y with weight a and B transduces string w to v with weight b, then their union transduces x to y with weight a and w to v with weight b.

Usage

template <class Arc>
void Union(MutableFst<Arc> *fst1, const Fst<Arc> &fst2);
template <class Arc> UnionFst<Arc>::
UnionFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2);

UnionFst

fstunion a.fst b.fst out.fst

Examples

A:

Input FST A for Union operation.

B:

Input FST B for Union operation.

A ∪ B:

Result of Union(A, B).

Union(&A, B);
UnionFst<Arc>(A, B);
fstunion a.fst b.fst out.fst

Complexity

Union:

  • Time: $O(V_2 + E_2)$
  • Space: $O(V_2 + E_2)$

where $V_i$ = # of states and $E_i$ = # of arcs of the ith FST.

UnionFst:

  • Time: $O(v_1 + e_1 + v_2 + e_2)$
  • Space: $O(v_1 + v_2)$

where $v_i$ = # of states visited and $e_i$ = # of arcs visited of the ith FST. Constant time and space to visit an input state or arc is assumed and exclusive of caching.