[4/19/2014] After a recent upgrade, we have been having problems with runaway TWiki processes that cause this server to eventually freeze. We are working on it.

This operation computes the composition of two transducers. If `A`

transduces string `x`

to `y`

with weight `a`

and `B`

transduces `y`

to `z`

with weight `b`

, then their composition transduces
string `x`

to `z`

with weight `a ⊗ b`

.

The output labels of the first transducer or the input labels of the second transducer must be sorted (or the FSTs otherwise support appropriate
matchers).
The weights need to form a commutative semiring (valid for `TropicalWeight`

and `LogWeight`

for instance).

Versions of this operation (not all shown here) accept options that allow choosing the matcher, composition filter, state table and, when delayed, the caching behavior used by composition.

`A`

:

`B`

:

`A o B`

:

Compose(A, B, &C); ComposeFst<Arc>(A, B); fstcompose a.fst b.fst out.fst

Assuming the first FST is unsorted and the second is sorted:

`Compose`

:

- Time:
*O(V*_{1}V_{2}D_{1}(log D_{2}+ M_{2})) - Space:
*O(V*_{1}V_{2}D_{1}M_{2})

`ComposeFst`

:

- TIme:
*O(v*,_{1}v_{2}d_{1}(log d_{2}+ m_{2})) - Space:
*O(v*_{1}v_{2})

`Compose`

and `fstcompose`

trim their output, `ComposeFst`

does not (since it is a delayed operation).

The efficiency of composition can be strongly affected by several factors:

- the choice of which transducer is sorted
- prefer sorting the FST that has the greater average out-degree
- sorting both transducers allows composition to automatically select the best transducer to match against (per state pair)
- note stored sort properties of the FSTs are first checked in constant time followed by the minimum number of linear-time sort tests necessary to discover one sorted FST; thus composition may be unaware that both FSTs are sorted when those properties are not stored.

- the amount of non-determinism
- the presence and location of epsilon transitions - avoid epsilon transitions on the output side of the first transducer or the input side of the second transducer or prefer placing them later in a path since they delay matching and can introduce non-coaccessible states and transitions

See here for more discussion on efficient usage.

I | Attachment | History | Action | Size | Date | Who | Comment |
---|---|---|---|---|---|---|---|

jpg | compose1.jpg | r2 r1 | manage | 11.7 K | 2007-06-30 - 21:47 | MichaelRiley | |

jpg | compose2.jpg | r7 r6 r5 r4 r3 | manage | 11.2 K | 2007-06-30 - 21:47 | MichaelRiley | |

jpg | compose3.jpg | r6 r5 r4 r3 r2 | manage | 14.8 K | 2007-06-30 - 21:47 | MichaelRiley |

Topic revision: r23 - 2014-04-23 - MichaelRiley

Copyright © 2008-2014 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding TWiki? Send feedback

Ideas, requests, problems regarding TWiki? Send feedback