Concat

Description

This operation computes the concatenation (product) 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 concatenation transduces string xw to yv with weight a ⊗ b.

Usage

template <class Arc> 
void Concat(MutableFst<Arc> *fst1, const Fst<Arc> &fst2);
doc
template <class Arc> 
void Concat(const Fst<Arc> &fst1, MutableFst<Arc> *fst2);
doc
template <class Arc> ConcatFst<Arc>::
ConcatFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2);
doc
fstconcat a.fst b.fst out.fst

Examples

A:

concat1.jpg

B:

concat2.jpg

AB:

concat3.jpg

Concat(&A, B);
Concat(A, &B);
ConcatFst<Arc>(A, B);
fstconcat a.fst b.fst out.fst

Complexity

Concat(&A, B):

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

Concat(A, &B):

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

ConcatFst:

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

Caveats

When concatenating a large number of FSTs, one should use the prepending Concat(A, &B) instead of the appending Concat(&A, B) since the total cost of the concatenation operations would be linear in the sum of the size of the input FSTs for the former instead of quadratic for the latter.

-- MichaelRiley - 15 Jun 2007

Topic attachments
I Attachment History Action Size Date Who Comment
JPEGjpg concat1.jpg r1 manage 6.3 K 2007-06-21 - 21:43 MichaelRiley  
JPEGjpg concat2.jpg r1 manage 3.4 K 2007-06-21 - 21:43 MichaelRiley  
JPEGjpg concat3.jpg r1 manage 10.6 K 2007-06-21 - 21:43 MichaelRiley  
Topic revision: r16 - 2015-09-20 - MichaelRiley
 
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