TWiki> FST Web>FstQuickTour>ReplaceDoc (revision 7)EditAttach

Replace

Description

This operation performs the dynamic replacement of arcs in one FST with another FST, allowing the definition of FSTs analogous to RTNs. It takes as input 1) a set of pairs formed by a non-terminal label and its corresponding FST, and 2) a label identifying the root FST in that set. The resulting FST is obtained by taking the root FST and recursively replacing each arc having a nonterminal as output label by its corresponding FST.

More precisely, an arc form state s to state d with output label the nonterminal n is replaced by redirecting this arc to the initial state of a copy F of the FST for nonterminal n, replacing its output label by epsilon (and its input label by epsilon when the option epsilon_on_replace is set to true), and adding epsilon arcs from each final state of F to d.

Usage

template <class Arc>
void Replace(const vector<pair<typename Arc::Label, const Fst<Arc>* > > &label_fst_pairs, 
             MutableFst<Arc> *ofst,
             typename Arc::Label root,
             bool epsilon_on_replace = false);
doc [bad link?]
template <class Arc> ReplaceFst<Arc>::
ReplaceFst(const vector<pair<typename Arc::Label, const Fst<Arc>* > > &label_fst_pairs,
           typename Arc::Label root);
doc
template <class Arc> ReplaceFst<Arc>::
ReplaceFst(const vector<pair<typename Arc::Label, const Fst<Arc>* > > &label_fst_pairs,
           const ReplaceFstOptions<Arc> &opts);
fstreplace [--epsilon_on_replace] root.fst rootlabel [subfst1.fst label1 ....] [out.fst]

Examples

Symbol table:

eps 0
$Root 1
$Name 2
$FirstName 3
$LastName 4
dial 5
please 6
johan 7
schalkwyk 8
google 9
michael 10
riley 11

A1:

root FST:

g1.png

A2:

FST for nonterminal $Name :

g2.png

A3:

FST for nonterminal $FirstName :

g3.png

A4:

Fst for nonterminal $LastName :

g4.png

B:

g_out.png

vector<pair<Label, const Fst<Arc>*> > > label_fst_pairs;
label_fst_pairs.push_back(make_pair(1, A1.Copy()));
label_fst_pairs.push_back(make_pair(2, A2.Copy()));
label_fst_pairs.push_back(make_pair(3, A3.Copy()));
label_fst_pairs.push_back(make_pair(4, A4.Copy()));
Replace(label_fst_pairs, &B, 1, true);

ReplaceFst<Arc> B(label_fst_pairs, ReplaceFstOptions<Arc>(1, true));

fstreplace --epsilon_on_replace a1.fst 1 a2.fst 2 a3.fst 3 a4.fst 4 b.fst

Complexity

Replace

  • Time: O(V + E + N)
  • Space: O(V + N)
where V = # of states, E = # of transitions in the resulting FST, and N = # of nonterminals.

ReplaceFst

  • Time: O(v + e + N)
  • Space: O(v + N)
where v = # of visited states, e = # of visited transitions in the resulting FST, and N = # of nonterminals. Constant time and space to visit an input state or arc is assumed and exclusive of caching.

Caveats

A cyclic dependency among a subset of nonterminals will lead to an infinite machine. The presence of such cyclic dependencies can be tested in time linear in the sum of the sizes of the input FSTs using the CyclicDependencies method of the ReplaceFst class.

-- CyrilAllauzen - 02 Mar 2009

Topic attachments
I Attachment History Action Size Date Who Comment
PNGpng g1.png r2 r1 manage 11.7 K 2009-03-02 - 20:09 CyrilAllauzen Replace example: root fst
PNGpng g2.png r2 r1 manage 12.7 K 2009-03-02 - 20:10 CyrilAllauzen Replace example: fst for nonterminal $Name
PNGpng g3.png r2 r1 manage 6.3 K 2009-03-02 - 20:10 CyrilAllauzen Replace example: fst for nonterminal $FirstName
PNGpng g4.png r2 r1 manage 6.9 K 2009-03-02 - 20:11 CyrilAllauzen Replace example: fst for nonterminal $LastName
PNGpng g_out.png r1 manage 22.1 K 2009-03-02 - 20:11 CyrilAllauzen Replace example: resulting fst
Edit | Attach | Watch | Print version | History: r10 < r9 < r8 < r7 < r6 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r7 - 2010-08-02 - CyrilAllauzen
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback