Difference: ReplaceDoc (9 vs. 10)

Revision 102018-04-27 - MichaelRiley

Line: 1 to 1
 
META TOPICPARENT name="FstQuickTour"

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 from 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);
Changed:
<
<
| %DOX{namespacefst.html#Replace[doc]}% |
>
>
| |
 
template <class Arc> ReplaceFst<Arc>::
ReplaceFst(const vector<pair<typename Arc::Label, const Fst<Arc>* > > &label_fst_pairs,
           typename Arc::Label root);
%DOX{fst::ReplaceFst[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.emplace_back(1, A1.Copy());
label_fst_pairs.emplace_back(2, A2.Copy());
label_fst_pairs.emplace_back(3, A3.Copy());
label_fst_pairs.emplace_back(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

META FILEATTACHMENT attr="" autoattached="1" comment="Replace example: fst for nonterminal =$Name=" date="1236024617" name="g2.png" path="g2.png" size="13036" user="Main.CyrilAllauzen" version="2"
META FILEATTACHMENT attr="" autoattached="1" comment="Replace example: resulting fst" date="1236024718" name="g_out.png" path="g_out.png" size="22603" user="Main.CyrilAllauzen" version="1"
META FILEATTACHMENT attr="" autoattached="1" comment="Replace example: fst for nonterminal =$LastName=" date="1236024671" name="g4.png" path="g4.png" size="7068" user="Main.CyrilAllauzen" version="2"
META FILEATTACHMENT attr="" autoattached="1" comment="Replace example: fst for nonterminal =$FirstName=" date="1236024644" name="g3.png" path="g3.png" size="6460" user="Main.CyrilAllauzen" version="2"
META FILEATTACHMENT attr="" autoattached="1" comment="Replace example: root fst" date="1236024546" name="g1.png" path="g1.png" size="11966" user="Main.CyrilAllauzen" version="2"
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 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