StateMapDoc < FST

---+ !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[%H%]}%  combines arcs with the same input label, output label and destination state, &oplus;-summing their weights.

A list of available state mappers and instructions on how to create them are given [[FstAdvancedUsage#StateMappers][here]].

---++ Usage

| <verbatim>template <class Arc, class StateMapper>
StateMap(MutableFst<Arc> *fst, StateMapper *mapper); </verbatim> | %DOX{namespacefst.html#StateMap[%H%]}% |
| <verbatim>template <class Arc, class StateMapper>
StateMap(MutableFst<Arc> *fst, StateMapper mapper); </verbatim> |^|
| <verbatim>template <class Arc, class StateMapper>
StateMap(const Fst<Arc> &ifst, MutableFst<Arc> *ofst, StateMapper *mapper); </verbatim> |^|
| <verbatim>template <class Arc, class StateMapper>
StateMap(const Fst<Arc> &ifst, MutableFst<Arc> *ofst, StateMapper mapper); </verbatim> |^|
| <verbatim>template <class Arc, class StateMapper> StateMapFst<Arc>::
StateMapFst(const Fst<A> &fst, StateMapper *mapper); </verbatim> | %DOX{fst::StateMapFst[%H%]}% |
| <verbatim>template <class Arc, class StateMapper> StateMapFst<Arc>::
StateMapFst(const Fst<A> &fst, const StateMapper &mapper); </verbatim> |^|
| <verbatim>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: ""
</verbatim> ||

Note =fstmap= also includes [[ArcMapDoc][arc mappers]].

---++ Example 

---+++ =A=:

%ATTACHURL%/map1.png

 (!TropicalWeight)

---+++ =StateMap(&A, <nop>ArcSumMapper(A))=:

%ATTACHURL%/map2.png

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

---++ 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 [[FstAdvancedUsage#FstCaching][caching]].

For instance in the case of =ArcSumMap=, we have _c = O(D log(D))_ and _m = O(D)_, where _D_ = maximum out-degree.

---++ See Also

[[ArcMapDoc][ArcMap]], [[FstAdvancedUsage#StateMappers][State Mappers]]
Attachments
Topic attachments
I	Attachment	History	Action	Size	Date	Who	Comment
png	map1.png	r1	manage	24.0 K	2011-12-06 - 00:57	MichaelRiley
png	map2.png	r1	manage	16.9 K	2011-12-06 - 00:57	MichaelRiley
This topic: FST > WebHome > FstQuickTour > StateMapDoc
Topic revision: r3 - 2014-04-23 - MichaelRiley