# 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` 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 StateMap(MutableFst *fst, StateMapper *mapper); ``` ```template StateMap(MutableFst *fst, StateMapper mapper); ``` ```template StateMap(const Fst &ifst, MutableFst *ofst, StateMapper *mapper); ``` ```template StateMap(const Fst &ifst, MutableFst *ofst, StateMapper mapper); ``` ```template StateMapFst:: StateMapFst(const Fst &fst, StateMapper *mapper); ``` ```template StateMapFst:: StateMapFst(const Fst &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

(TropicalWeight)

### `StateMap(&A, ArcSumMapper(A))`:

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

## See Also

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
Edit | Watch | Print version | History: r4 < r3 < r2 < r1 | Backlinks | Raw View | More topic actions
Topic revision: r4 - 2018-04-27 - MichaelRiley

Copyright © 2008-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback