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);
doc
template <class Arc> UnionFst<Arc>::
UnionFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2);
doc
fstunion a.fst b.fst out.fst
 

Examples

A:

union1.jpg

B:

union2.jpg

A ∪ B:

union3.jpg

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

Complexity

Union:

  • Time: O(V2 + E2)
  • Space: O(V2 + E2)
where Vi = # of states and Ei = # of arcs of the ith FST.

UnionFst:

  • Time: O(v1 + e1 + v2 + e2)
  • Space: O(v1 + v2)
where vi = # of states visited and ei = # 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

Topic attachments
I Attachment History Action Size Date Who Comment
JPEGjpg union1.jpg r1 manage 3.4 K 2007-07-01 - 19:04 MichaelRiley  
JPEGjpg union2.jpg r1 manage 6.3 K 2007-07-01 - 19:05 MichaelRiley  
JPEGjpg union3.jpg r1 manage 12.6 K 2007-07-01 - 19:06 MichaelRiley  
Topic revision: r3 - 2009-03-06 - CyrilAllauzen
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback