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 implemenations are available.

Usage

template <class Arc> void Prune(MutableFst<Arc> *fst, typename Arc::Weight threshold);	[bad link?]
template <class Arc> void Prune(const Fst<Arc> &ifst, MutableFst<Arc> *ofst, typename Arc::Weight threshold);	[bad link?]
fstshortestpath [--opts] in.fst out.fst --weight: type = string, default = "" Weight parameter

Complexity

Prune:

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

-- CyrilAllauzen - 05 Jul 2007