TWiki> FST Web>FstQuickTour>ComposeDoc (revision 20)EditAttach

# Compose

## Description

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.

## Usage

 ```template void Compose(const Fst &ifst1, const Fst &ifst2, MutableFst *ofst); ``` [bad link?] ```template ComposeFst:: ComposeFst(const Fst &fst1, const Fst &fst2); ``` ```fstcompose [--opts] a.fst b.fst out.fst --connect: Trim output (def: true) ```

## Examples

### `A o B`:

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

## Complexity

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

`Compose`:

• Time: O(V1 V2 D1 (log D2 + M2))
• Space: O(V1 V2 D1 M2)
where Vi = # of states, Di = maximum out-degree and Mi = maximum multiplicity for the ith FST.

`ComposeFst`:

• TIme: O(v1 v2 d1 (log d2 + m2)),
• Space: O(v1 v2)
where vi = # of states visited, di = maximum out-degree, and mi = maximum multiplicity of the states visited.for the ith FST. Constant time and space to visit an input state or arc is assumed and exclusive of caching.

## Caveats

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

-- MichaelRiley - 15 Jun 2007

Topic attachments
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
Edit | Attach | Watch | Print version |  | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r20 - 2011-12-06 - 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