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);
fstunion a.fst b.fst out.fst

Examples

A:

B:

A ∪ B:

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

Complexity

Union:

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

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

UnionFst:

• Time: O(v₁ + e₁ + v₂ + e₂)
• Space: O(v₁ + v₂)
  

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.

-- MichaelRiley - 1 Jul 2007