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);
template <class Arc> void Concat(const Fst<Arc> &fst1, MutableFst<Arc> *fst2);
template <class Arc> ConcatFst<Arc>:: ConcatFst(const Fst<Arc> &fst1, const Fst<Arc> &fst2);
fstconcat a.fst b.fst out.fst

Examples

A:

B:

AB:

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

Complexity

Concat(&A, B):

• Time: O(V₁ + V₂ + E₂)
• Space: O(V₁ + V₂ + E₂)
  

where V_i = # of states and E_i = # of arcs of the ith FST.

Concat(A, &B):

• Time: O(V₁ + E₁)
• Space: O(V₁ + E₁)
  

where V_i = # of states and E_i = # of arcs of the ith FST.

ConcatFst:

• Time: O(v₁ + e₁ + v₂ + e₂)
• Space: O(v₁ + v₂)
  

where v_i = # of states visited and e_i = # 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