Difference: UnionDoc (1 vs. 4)

Revision 42018-04-27 - MichaelRiley

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

Union

Line: 15 to 15
 |
template <class Arc> 
void Union(MutableFst<Arc> *fst1, const Fst<Arc> &fst2);
Changed:
<
<
| doc [bad link?] |
>
>
| |
 |
template <class Arc> UnionFst<Arc>::
UnionFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2);

Revision 32009-03-06 - CyrilAllauzen

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

Union

Line: 53 to 53
 
  • Time: O(v1 + e1 + v2 + e2)
  • Space: O(v1 + v2)
where vi = # of states visited and ei = # of arcs visited of the ith FST.
Changed:
<
<
Constant time and space to visit an input state or arc is assumed and exclusive of caching.
>
>
Constant time and space to visit an input state or arc is assumed and exclusive of caching.
  -- MichaelRiley - 1 Jul 2007

Revision 22007-07-02 - MichaelRiley

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

Union

Line: 44 to 44
 

Complexity

Changed:
<
<
Union: O(V2 + E2), where Vi = # of states and Ei = # of arcs of the ith FST.
>
>
Union:
  • Time: O(V2 + E2)
  • Space: O(V2 + E2)
where Vi = # of states and Ei = # of arcs of the ith FST.
  UnionFst:
Changed:
<
<
  • Constructor: O(1)
  • Traversal: O(v1 + e1 + v2 + e2),
    where vi = # of states visited and ei = # of arcs visited of the ith FST and constant time to visit an input state or arc is assumed.
>
>
  • 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

Revision 12007-07-01 - MichaelRiley

Line: 1 to 1
Added:
>
>
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);
doc [bad link?]
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: O(V2 + E2), where Vi = # of states and Ei = # of arcs of the ith FST.

UnionFst:

  • Constructor: O(1)
  • Traversal: O(v1 + e1 + v2 + e2),
    where vi = # of states visited and ei = # of arcs visited of the ith FST and constant time to visit an input state or arc is assumed.

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