Difference: UnionDoc (3 vs. 4)

Revision 42018-04-27 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

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);
Changed:
<
<
| %DOX{namespacefst.html#Union[doc]}% |
>
>
| |
 
template <class Arc> UnionFst<Arc>::
UnionFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2);
%DOX{fst::UnionFst[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

META FILEATTACHMENT attr="" autoattached="1" comment="" date="1183316686" name="union1.jpg" path="union1.jpg" size="3497" user="Main.MichaelRiley" version="1"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1183316725" name="union2.jpg" path="union2.jpg" size="6423" user="Main.MichaelRiley" version="1"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1183316762" name="union3.jpg" path="union3.jpg" size="12872" user="Main.MichaelRiley" version="1"
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback