TWiki> FST Web>FstQuickTour>ConcatDoc (revision 13)EditAttach



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.


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








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


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.


  • 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 - 15 Jun 2007

Topic attachments
I Attachment HistorySorted ascending 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  
Edit | Attach | Watch | Print version | History: r17 | r15 < r14 < r13 < r12 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r13 - 2009-03-02 - CyrilAllauzen
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2022 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback