Difference: StateMapDoc (1 vs. 4)

Revision 42018-04-27 - MichaelRiley

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

StateMap

Line: 14 to 14
 

Usage

|

template <class Arc, class StateMapper>
Changed:
<
<
StateMap(MutableFst *fst, StateMapper *mapper); | %DOX{namespacefst.html#StateMap[doc]}% |
>
>
StateMap(MutableFst *fst, StateMapper *mapper); | |
 
template <class Arc, class StateMapper>
StateMap(MutableFst<Arc> *fst, StateMapper mapper); 
|
template <class Arc, class StateMapper>

Revision 32014-04-23 - MichaelRiley

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

StateMap

Line: 66 to 66
  For instance in the case of ArcSumMap, we have c = O(D log(D)) and m = O(D), where D = maximum out-degree.
Added:
>
>

See Also

ArcMap, State Mappers

 
Deleted:
<
<
-- MichaelRiley - 05 Dec 2011
 
META FILEATTACHMENT attachment="map1.png" attr="" comment="" date="1323133046" name="map1.png" path="map1.png" size="24540" stream="map1.png" tmpFilename="/var/tmp/CGItemp1973" user="MichaelRiley" version="1"
META FILEATTACHMENT attachment="map2.png" attr="" comment="" date="1323133075" name="map2.png" path="map2.png" size="17291" stream="map2.png" tmpFilename="/var/tmp/CGItemp2133" user="MichaelRiley" version="1"

Revision 22011-12-06 - MichaelRiley

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

StateMap

Line: 7 to 7
 This operation transforms each state in the input FST. The transformation is specified by a function object called a state mapper.
Changed:
<
<
For instance, ArcSumMapper %DOX{structfst_1_1_arc_sum_mapper.html[doc]}% combines arcs with the same input label, output label and destination state, summing their weights.
>
>
For instance, ArcSumMapper %DOX{structfst_1_1_arc_sum_mapper.html[doc]}% combines arcs with the same input label, output label and destination state, ⊕-summing their weights.
  A list of available state mappers and instructions on how to create them are given here.
Line: 34 to 34
 

Example

Deleted:
<
<
(Under construction).
 

A:

map1.png

Added:
>
>
(TropicalWeight)
 

StateMap(&A, ArcSumMapper(A)):

map2.png

Line: 68 to 68
 

-- MichaelRiley - 05 Dec 2011

Added:
>
>
META FILEATTACHMENT attachment="map1.png" attr="" comment="" date="1323133046" name="map1.png" path="map1.png" size="24540" stream="map1.png" tmpFilename="/var/tmp/CGItemp1973" user="MichaelRiley" version="1"
META FILEATTACHMENT attachment="map2.png" attr="" comment="" date="1323133075" name="map2.png" path="map2.png" size="17291" stream="map2.png" tmpFilename="/var/tmp/CGItemp2133" user="MichaelRiley" version="1"

Revision 12011-12-05 - MichaelRiley

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

StateMap

Description

This operation transforms each state in the input FST. The transformation is specified by a function object called a state mapper.

For instance, ArcSumMapper %DOX{structfst_1_1_arc_sum_mapper.html[doc]}% combines arcs with the same input label, output label and destination state, summing their weights.

A list of available state mappers and instructions on how to create them are given here.

Usage

template <class Arc, class StateMapper>
StateMap(MutableFst<Arc> *fst, StateMapper *mapper); 
%DOX{namespacefst.html#StateMap[doc]}%
template <class Arc, class StateMapper>
StateMap(MutableFst<Arc> *fst, StateMapper mapper); 
template <class Arc, class StateMapper>
StateMap(const Fst<Arc> &ifst, MutableFst<Arc> *ofst, StateMapper *mapper); 
template <class Arc, class StateMapper>
StateMap(const Fst<Arc> &ifst, MutableFst<Arc> *ofst, StateMapper mapper); 
template <class Arc, class StateMapper> StateMapFst<Arc>::
StateMapFst(const Fst<A> &fst, StateMapper *mapper); 
%DOX{fst::StateMapFst[doc]}%
template <class Arc, class StateMapper> StateMapFst<Arc>::
StateMapFst(const Fst<A> &fst, const StateMapper &mapper); 
fstmap [--opts] in.fst out.fst 
     -map_type (Map operation, one of: "identity", "arc_sum") type: string default: "identity"
    -weight (Weight parameter) type: string default: ""

Note fstmap also includes arc mappers.

Example

(Under construction).

A:

map1.png

StateMap(&A, ArcSumMapper(A)):

map2.png

StateMap(&A, ArcSumMapper<StdArc>(A));
StateMap(A, &B, ArcSumMapper<StdArc>(A));
StateMapFst B(A, ArcSumMapper<StdArc>(A));

fstmap --map_type=arc_sum a.fst b.fst

Complexity

StateMap:

  • Time: O(c*V)
  • Space: O(m)
where V = # of states, c = cost of processing one state by the mapper and m = total memory usage for the mapper.

StateMapFst:

  • Time: O(c*v)
  • Space: O(m)
where v = # of visited states, c = cost of processing one state by the mapper and m = total memory usage for the mapper. Constant time and space to visit an input state is assumed and exclusive of caching.

For instance in the case of ArcSumMap, we have c = O(D log(D)) and m = O(D), where D = maximum out-degree.

-- MichaelRiley - 05 Dec 2011

 
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