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.


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



Prune of A with threshold 3:


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



  • Time: O(V log V + E)
  • Space: O(V + E)
where V = # of states and E = # of arcs.

-- CyrilAllauzen - 05 Jul 2007

Topic attachments
I Attachment History Action Size DateSorted ascending Who Comment
JPEGjpg prune1.jpg r1 manage 9.4 K 2007-07-09 - 21:05 CyrilAllauzen prune input example
JPEGjpg prune2.jpg r1 manage 8.8 K 2007-07-09 - 21:06 CyrilAllauzen  

This topic: FST > WebHome > FstQuickTour > PruneDoc
Topic revision: r3 - 2011-12-06 - MichaelRiley
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2022 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback