TWiki> FST Web>FstQuickTour>PruneDoc (revision 1)EditAttach



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?]
fstshortestpath [--opts] in.fst out.fst
    --weight: type = string, default = ""
      Weight parameter



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

-- CyrilAllauzen - 05 Jul 2007

Edit | Attach | Watch | Print version | History: r5 | r4 < r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r1 - 2007-07-05 - CyrilAllauzen
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2023 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback