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[]}% |
>
>
| |

 ```template UnionFst:: UnionFst(const Fst &fst1, const Fst &fst2); ``` %DOX{fst::UnionFst[]}% `fstunion a.fst b.fst out.fst`

Examples

`A ∪ B`:

```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" attr="" autoattached="1" comment="" date="1183316725" name="union2.jpg" path="union2.jpg" size="6423" user="Main.MichaelRiley" version="1" attr="" autoattached="1" comment="" date="1183316762" name="union3.jpg" path="union3.jpg" size="12872" user="Main.MichaelRiley" version="1"

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