Prune

Description

This operation deletes states and arcs in the input FST that do not belong to a successful path whose weight is no more (w.r.t the natural the natural semiring order) than the threshold t ⊗-times the weight of the shortest path in the input FST.

Weights need to be commutative and have the path property. Both destructive and constructive implementations are available.

Usage

template <class Arc>
void Prune(MutableFst<Arc> *fst, typename Arc::Weight threshold);

template <class Arc>
void Prune(const Fst<Arc> &ifst, MutableFst<Arc> *ofst, typename Arc::Weight threshold);

fstprune [--opts] in.fst out.fst
    --weight: type = string, default = ""
      Weight parameter

A:

Prune of A with threshold 3:

Prune(&A, 3);
Prune(A, &B, 3);
fstprune --weight=3 a.fst out.fst

Complexity

Prune:

• Time: O(V log V + E)
• Space: O(V + E)

-- CyrilAllauzen - 05 Jul 2007