Difference: ReplaceDoc (1 vs. 10)

Revision 102018-04-27 - MichaelRiley

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

Replace

Line: 16 to 16
  MutableFst *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,

Revision 92017-02-23 - KyleGorman

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

Replace

Line: 78 to 78
 
vector<pair<Label, const Fst<Arc>*> > > label_fst_pairs;
Changed:
<
<
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()));
>
>
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);

Revision 82015-05-04 - KyleGorman

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

Replace

Line: 6 to 6
  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.
Changed:
<
<
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.
>
>
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

Revision 72010-08-02 - CyrilAllauzen

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

Replace

Line: 15 to 15
 void Replace(const vector<pair* > > &label_fst_pairs, MutableFst *ofst, typename Arc::Label root,
Changed:
<
<
bool epsilon_on_replace);
>
>
bool epsilon_on_replace = false);
  | %DOX{namespacefst.html#Replace[doc]}% | |
template <class Arc> ReplaceFst<Arc>::

Revision 62010-07-21 - CyrilAllauzen

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

Replace

Line: 12 to 12
  |
template <class Arc>
Changed:
<
<
void Replace(const vector<pair* > > >&label_fst_pairs,
>
>
void Replace(const vector<pair* > > &label_fst_pairs,
  MutableFst *ofst, typename Arc::Label root, bool epsilon_on_replace); | %DOX{namespacefst.html#Replace[doc]}% | |
template <class Arc> ReplaceFst<Arc>::
Changed:
<
<
ReplaceFst(const vector<pair* > > > &label_fst_pairs,
>
>
ReplaceFst(const vector<pair* > > &label_fst_pairs,
  typename Arc::Label root); |%DOX{fst::ReplaceFst[doc]}% | |
template <class Arc> ReplaceFst<Arc>::
Changed:
<
<
ReplaceFst(const vector<pair* > > > &label_fst_pairs,
>
>
ReplaceFst(const vector<pair* > > &label_fst_pairs,
  const ReplaceFstOptions &opts); |^| |

Revision 52009-03-12 - CyrilAllauzen

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

Replace

Description

Changed:
<
<
Work in progress, under construction TBA
>
>
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

Line: 93 to 95
 

Complexity

Changed:
<
<
Work in progress, under construction TBA
>
>
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

Changed:
<
<
Work in progress, under construction TBA
>
>
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

Revision 42009-03-06 - CyrilAllauzen

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

Replace

Line: 31 to 31
 

Examples

Changed:
<
<

Symbol table

>
>

Symbol table:

 
eps 0
$Root 1
Line: 46 to 46
 
michael 10
riley 11
Changed:
<
<

A1

>
>

A1:

  root FST:

g1.png

Changed:
<
<

A2

>
>

A2:

  FST for nonterminal $Name :

g2.png

Changed:
<
<

A3

>
>

A3:

  FST for nonterminal $FirstName :

g3.png

Changed:
<
<

A4

>
>

A4:

  Fst for nonterminal $LastName :

g4.png

Changed:
<
<

B

>
>

B:

  g_out.png
Line: 91 to 91
 fstreplace --epsilon_on_replace a1.fst 1 a2.fst 2 a3.fst 3 a4.fst 4 b.fst
Added:
>
>

Complexity

 
Added:
>
>
Work in progress, under construction TBA

Caveats

Work in progress, under construction TBA

 

-- CyrilAllauzen - 02 Mar 2009

Revision 32009-03-03 - CyrilAllauzen

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

Replace Work in progress, under construction

>
>

Replace

 

Description

Changed:
<
<

Usage

>
>
Work in progress, under construction TBA
 
Added:
>
>

Usage

  |
template <class Arc>
Changed:
<
<
Replace(const vector<pair* > > >&label_fst_pairs,
>
>
void Replace(const vector<pair* > > >&label_fst_pairs,
  MutableFst *ofst, typename Arc::Label root, bool epsilon_on_replace);
Line: 17 to 18
 |
template <class Arc> ReplaceFst<Arc>::
ReplaceFst(const vector<pair<typename Arc::Label, const Fst<Arc>* > > > &label_fst_pairs,
Changed:
<
<
typename Arc::Label root, bool epsilon_on_replace);
>
>
typename Arc::Label root);
  |%DOX{fst::ReplaceFst[doc]}% | |
Added:
>
>
template ReplaceFst:: ReplaceFst(const vector<pair* > > > &label_fst_pairs, const ReplaceFstOptions &opts); |^| |
 fstreplace [--epsilon_on_replace] root.fst rootlabel [subfst1.fst label1 ....] [out.fst] ||
Line: 79 to 84
 
Changed:
<
<
ReplaceFst B(label_fst_pairs, 1, true);
>
>
ReplaceFst B(label_fst_pairs, ReplaceFstOptions(1, true));
 

Revision 22009-03-02 - CyrilAllauzen

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

Replace

>
>

Replace Work in progress, under construction

 

Description

Revision 12009-03-02 - CyrilAllauzen

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

Replace

Description

Usage

template <class Arc>
Replace(const vector<pair<typename Arc::Label, const Fst<Arc>* > > >&label_fst_pairs, 
        MutableFst<Arc> *ofst,
        typename Arc::Label root,
        bool epsilon_on_replace);
%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,
           bool epsilon_on_replace);
%DOX{fst::ReplaceFst[doc]}%
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, 1, true);

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

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