Difference: ClosureDoc (1 vs. 15)

Revision 152018-04-27 - MichaelRiley

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

Closure

Line: 17 to 17
 |
template<class Arc>
void Closure(MutableFst<Arc> *fst, ClosureType type);
Changed:
<
<
| doc [bad link?] |
>
>
| |
 |
template <class Arc> ClosureFst<Arc>::
ClosureFst(const Fst<Arc> &fst, ClosureType type);

Revision 142009-03-06 - CyrilAllauzen

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

Closure

Line: 64 to 64
 
  • Time: O(v)
  • Space: O(v)
where v = # of states visited, e = # of arcs visited.
Changed:
<
<
Constant time to visit an input state or arc is assumed and exclusive of caching.
>
>
Constant time to visit an input state or arc is assumed and exclusive of caching.
 

-- MichaelRiley - 13 Jun 2007

Revision 132007-07-11 - MichaelRiley

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

Closure

Description

This operation computes the concatenative closure. If A transduces string x to y with weight a, then the closure transduces x to y with weight a, xx to yy with weight
Changed:
<
<
Times(a, a), xxx to yyy with weight Times(Times(a, a), a),
>
>
a ⊗ a, xxx to yyy with weight a ⊗ a ⊗ a,
 etc. If closure_type is CLOSURE_STAR, then the empty string is
Changed:
<
<
transduced to itself with weight Weight::One() as well.
>
>
transduced to itself with weight 1 as well.
 

Usage

Revision 122007-07-02 - MichaelRiley

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

Closure

Line: 56 to 56
 

Complexity

Closure:

Changed:
<
<
  • Time: O(V + E)
>
>
  • Time: O(V)
 
  • Space: O(V)
where V = # of states and E = # of arcs.

ClosureFst:

Changed:
<
<
  • Time: O(v + e)
>
>
  • Time: O(v)
 
  • Space: O(v)
where v = # of states visited, e = # of arcs visited. Constant time to visit an input state or arc is assumed and exclusive of caching.

Revision 112007-07-02 - MichaelRiley

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

Closure

Line: 55 to 55
 

Complexity

Changed:
<
<
Closure: O(V + E), where V = # of states and E = # of arcs.
>
>
Closure:
  • Time: O(V + E)
  • Space: O(V)
where V = # of states and E = # of arcs.
  ClosureFst:
Changed:
<
<
  • Constructor: O(1)
  • Traversal: O(v + e),
    where v = # of states visited, e = # of arcs visited and constant time to visit an input state or arc is assumed.
>
>
  • Time: O(v + e)
  • Space: O(v)
where v = # of states visited, e = # of arcs visited. Constant time to visit an input state or arc is assumed and exclusive of caching.
 

-- MichaelRiley - 13 Jun 2007

Revision 102007-07-01 - MichaelRiley

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

Closure

Line: 60 to 60
 ClosureFst:
  • Constructor: O(1)
  • Traversal: O(v + e),
Changed:
<
<
where v = # of states visited and e = # of arcs visited and assuming constant time to visit an input state or arc.
>
>
where v = # of states visited, e = # of arcs visited and constant time to visit an input state or arc is assumed.
 

-- MichaelRiley - 13 Jun 2007

Revision 92007-06-30 - MichaelRiley

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

Closure

Line: 55 to 55
 

Complexity

Changed:
<
<
Closure: O(nstates + narcs)
>
>
Closure: O(V + E), where V = # of states and E = # of arcs.
 ClosureFst:
  • Constructor: O(1)
Changed:
<
<
  • Traversal: O(nstates_visited + narcs_visited),
>
>
  • Traversal: O(v + e),
    where v = # of states visited and e = # of arcs visited and
  assuming constant time to visit an input state or arc.

Revision 82007-06-30 - MichaelRiley

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

Closure

Revision 72007-06-30 - MichaelRiley

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

Closure

Line: 24 to 24
  | doc | |
fstclosure [--opts] a.fst  out.fst
Changed:
<
<
-closure_type: closure_star (def) | closure_plus
>
>
--closure_type: closure_star (def) | closure_plus
  | |

Examples

Line: 50 to 50
 
Closure(&A, CLOSURE_PLUS);
ClosureFst<Arc>(A, CLOSURE_PLUS);
Changed:
<
<
fstclosure -closure_plus a.fst out.fst
>
>
fstclosure --closure_plus a.fst out.fst
 

Complexity

Revision 62007-06-26 - MichaelRiley

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

Closure

Line: 12 to 12
 

Usage

enum ClosureType { CLOSURE_STAR, CLOSURE_PLUS }; 
Added:
>
>
 
Added:
>
>
|
 template void Closure(MutableFst *fst, ClosureType type);
Changed:
<
<
>
>
| doc [bad link?] | |
 template ClosureFst:: ClosureFst(const Fst &fst, ClosureType type);
Changed:
<
<
>
>
| doc | |
 fstclosure [--opts] a.fst out.fst -closure_type: closure_star (def) | closure_plus
Changed:
<
<
>
>
| |
 

Examples

Line: 64 to 68
 

Changed:
<
<
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1181704907" name="closure2.jpg" path="closure2.jpg" size="6423" user="Main.MichaelRiley" version="1"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1181704843" name="closure1.jpg" path="closure1.jpg" size="3497" user="Main.MichaelRiley" version="1"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1181704930" name="closure3.jpg" path="closure3.jpg" size="4175" user="Main.MichaelRiley" version="1"
>
>
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1182462219" name="closure2.jpg" path="closure2.jpg" size="6423" user="Main.MichaelRiley" version="1"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1182462219" name="closure1.jpg" path="closure1.jpg" size="3497" user="Main.MichaelRiley" version="1"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1182462219" name="closure3.jpg" path="closure3.jpg" size="4175" user="Main.MichaelRiley" version="1"

Revision 52007-06-17 - MichaelRiley

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

Closure

Line: 54 to 54
 Closure: O(nstates + narcs)
ClosureFst:
  • Constructor: O(1)
Changed:
<
<
  • Traversal: O(nstates_visited + narcs_visited), assuming constant time to visit an input state or arc.
>
>
  • Traversal: O(nstates_visited + narcs_visited),
    assuming constant time to visit an input state or arc.
 

Revision 42007-06-16 - MichaelRiley

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

Closure

Line: 9 to 9
 etc. If closure_type is CLOSURE_STAR, then the empty string is transduced to itself with weight Weight::One() as well.
Added:
>
>

Usage

enum ClosureType { CLOSURE_STAR, CLOSURE_PLUS }; 

template<class Arc>
void Closure(MutableFst<Arc> *fst, ClosureType type);

template <class Arc> ClosureFst<Arc>::
ClosureFst(const Fst<Arc> &fst, ClosureType type);

fstclosure [--opts] a.fst  out.fst
  -closure_type: closure_star (def) | closure_plus
 

Examples

A:

Revision 32007-06-15 - MichaelRiley

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

Closure

Line: 19 to 19
  closure2.jpg
Changed:
<
<
Closure(&A, CLOSURE_STAR);
ClosureFst(A, CLOSURE_STAR);
fstclosure a.fst out.fst
>
>
Closure(&A, CLOSURE_STAR);
ClosureFst<Arc>(A, CLOSURE_STAR);
fstclosure a.fst out.fst
 

A+:

closure3.jpg

Changed:
<
<
Closure(&A, CLOSURE_PLUS);
ClosureFst(A, CLOSURE_PLUS);
fstclosure -closure_plus a.fst out.fst
>
>
Closure(&A, CLOSURE_PLUS);
ClosureFst<Arc>(A, CLOSURE_PLUS);
fstclosure -closure_plus a.fst out.fst
 

Complexity

Changed:
<
<
Closure: O(nstates + narcs)
>
>
Closure: O(nstates + narcs)
 ClosureFst:
  • Constructor: O(1)
  • Traversal: O(nstates_visited + narcs_visited), assuming constant time to visit an input state or arc.

Revision 22007-06-14 - MichaelRiley

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

Closure

Description

Changed:
<
<
This operation computes the concatenative closure. If A transduces x to y with weight a, then the
>
>
This operation computes the concatenative closure. If A transduces string x to y with weight a, then the
 closure transduces x to y with weight a, xx to yy with weight Times(a, a), xxx to yyy with weight Times(Times(a, a), a), etc. If closure_type is CLOSURE_STAR, then the empty string is

Revision 12007-06-13 - MichaelRiley

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

Closure

Description

This operation computes the concatenative closure. If A transduces x to y with weight a, then the closure transduces x to y with weight a, xx to yy with weight Times(a, a), xxx to yyy with weight Times(Times(a, a), a), etc. If closure_type is CLOSURE_STAR, then the empty string is transduced to itself with weight Weight::One() as well.

Examples

A:

closure1.jpg

A*:

closure2.jpg

Closure(&A, CLOSURE_STAR);
ClosureFst(A, CLOSURE_STAR);
fstclosure a.fst out.fst

A+:

closure3.jpg

Closure(&A, CLOSURE_PLUS);
ClosureFst(A, CLOSURE_PLUS);
fstclosure -closure_plus a.fst out.fst

Complexity

Closure: O(nstates + narcs)
ClosureFst:

  • Constructor: O(1)
  • Traversal: O(nstates_visited + narcs_visited), assuming constant time to visit an input state or arc.

-- MichaelRiley - 13 Jun 2007

META FILEATTACHMENT attr="" autoattached="1" comment="" date="1181704907" name="closure2.jpg" path="closure2.jpg" size="6423" user="Main.MichaelRiley" version="1"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1181704843" name="closure1.jpg" path="closure1.jpg" size="3497" user="Main.MichaelRiley" version="1"
META FILEATTACHMENT attr="" autoattached="1" comment="" date="1181704930" name="closure3.jpg" path="closure3.jpg" size="4175" user="Main.MichaelRiley" version="1"
 
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