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:

prune1.jpg

Prune of A with threshold 3:

prune2.jpg

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)
where V = # of states and E = # of arcs.

-- CyrilAllauzen - 05 Jul 2007

Topic attachments
I Attachment History Action Size Date 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  
Edit | Attach | Watch | Print version | History: r5 < r4 < r3 < r2 < r1 | Backlinks | Raw View | WYSIWYG | More topic actions
Topic revision: r5 - 2018-04-27 - MichaelRiley
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback